프로그래머스 고득점 kit 풀기 #정렬

1. K번째 수

i,j,k가 입력되면, 전체 배열에서 i~j까지의 수를 정렬한 뒤 k번째 수를 구하면 된다.

 

내 코드

def solution(array, commands):
    answer = []
    for i,j,k in commands:
        answer.append(list(sorted(array[i-1:j]))[k-1])
    return answer

이게 조금 더 정석적인 코드라고 생각하지만 추천순 1위에는 lambda 함수를 이용한 한 줄 짜리 코드가 있었다.

그래서 나도 한 줄로 짜봤다.

 

한 줄 짜리

def solution(array, commands):
    return [sorted(array[i-1:j])[n-1] for i, j, n in commands]

하지만 이 전에도 말했든 별로 직관적이지 않아 그닥 선호하지 않는다.

 

이 문제는 내가 20살 때 풀었던 문제이다. 그 당시에는 정말 기진맥진하면서 겨우 풀어냈던 기억이 난다. 하지만 지금은.. 너무나 쉽게 풀린다. 지나쳐온 시간이 무의미하지만은 않은 것 같아 너무 뿌듯했다.

 

2. 가장 큰 수 (실패)

이거 좀 어려웠다. 주어지는 수 들을, 문자열로 더했을 때 가장 큰 수가 되도록 하면 된다.

처음에는 sorted 함수의 key를 이용하려고 했다. 하지만 잘 되지 않아서 서러웠다.

검색을 통해 알아낸 방법이지만, 문자열을 비교할 때에는 각 자릿수 (인덱스 0부터)의 ascii 코드 값을 기준으로 비교한다. 같을 경우에 다음 인덱스로 넘어간다 (인덱스 1 끼리 비교)

 

나도 얼핏 눈치는 챘었는데, 자릿 수가 다른 (문자열의 길이가 다른) 경우를 처리하지 못했다.

 

여기에는 한 가지 아이디어가 추가되면 좋은데 숫자의 최댓값이 1000이다.

때문에, 모든 수를 세자리 수로 바꿔준 뒤 진행하면 된다.

-> lambda x : x*3 [x가 문자일 경우에]

이를 정렬 기준으로 사용할 경우 다음과 같은 계산이 가능해진다.

문제의 요구사항을 만족하기 위해서는 6, 62를 비교할 때 6이 62 보다 앞에 가야한다.

문자열로 비교하면, 인덱스 0은 6,6,으로 동일하다.

그럼 인덱스 1로 넘어가게 되는데, 6은 1번 인덱스가 없다. 때문에 62가 앞으로 가게된다.

하지만 위 람다함수를 적용한다면, 666, 626262가 되기 때문에

0번 인덱스는 동일, 1번 인덱스에서 666이 더 크기 때문에

6, 62 순으로 정렬된다.

 

문제의 조건을 만족할 수 있다.

 

정답코드

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers))

아슬아슬하게 정답을 놓쳤다는 점에서 킹받은 나는 다음과 같은 악랄한 코드를 짰다.

def solution(numbers):
    return str(int("".join(sorted(list(map(str, numbers)), key=lambda x:x*3, reverse=True))))

 

마지막 부분에서 str(int(answer))을 진행하는 이유는, 문자열 형태로 저장되는 수 이다 보니 "000" 같은 케이스가 생기기 때문이다 (문제 채점시 테스트 11). int를 통해 정상적인 수로 바꿔준 뒤, 데이터 타입만 문자열로 바꿔준다.

 

나는 위 아이디어가 제대로 구현되지 않자 다른 아이디어를 떠올렸다.

숫자 두개만 가지고 비교하는 방식이다.

두 수를 이어붙인 경우 중 가장 큰 수가 나오는 경우를 return하는 함수를 기준으로 정렬하는 방식이다.

하지만 이 또한 실패했다 ... ㅠㅠㅠㅠ (아직 많이 부족하다)

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

functools.cmp_to_key라는 함수는, comparator (비교기)를 정렬 기준으로 삼는다.

비교기는 두 인자를 받는데, 첫 번째 인자가 더 큰 경우에 1, 작은 경우에 -1, 같으면 0을 리턴하도록 구현한다.

이를 정렬 기준으로 삼을 수 있다.

 

이렇게 진행하면 내가 두 번째로 떠올린 아이디어를 구현할 수 있다.

 

[ 핵심 ]

문자열의 대소비교 기준 : 인덱스 0부터 ascii값 비교

functools.cmp_to_key(comparator), comparator(비교기) : 두 개의 전압이나 전류를 비교하고 더 큰 쪽을 가리키는 디지털 신호를 출력하는 장치.

 

3. H-index

처음엔 굉장히 쉬울거라 생각했는데, 간과한 사실이 있었다. 주어진 피 인용수가 아닌 수가 H인덱스가 될 수 있다는 점.

 

그 점을 고려하면서 다시 코드를 짰다.

 

내 코드

def solution(citations):
    result = []
    # h를 0부터 1씩 증가시키면서 0이 나올 때까지 모든 h를 구함
    cnt = len(citations)
    result.append(cnt)
    idx = 0
    while cnt:
        idx += 1
        cnt = 0
        for c in citations:
            if idx <=c:
                cnt += 1
        result.append(cnt)
    # 구한 h (result의 인덱스) 중 조건에 부합하는 최댓값 찾기
    # 조건 1. index <= value
    # print(result)
    answer = 0
    for idx, v in enumerate(result):
        if idx <= v:
            answer = idx
    return answer

확실히 저렇게 주석을 달아주면서 짜는게 집중력이 떨어지는 환경에서는 좋은 결과를 내는 듯 하다.

 

베스트 코드 (내가 생각한)

def solution(citations):
    citations = sorted(citations)
    l = len(citations)
    for i in range(l):
        if citations[i] >= l-i:
            return l-i
    return 0

이렇게 짜야지.. 하고 생각은 했었는데 뭔가 프로그래머스의 IDE에서는 막히는 부분이 좀 생긴다.

적응도의 탓인가..?