(프로그래머스 정렬 문제 풀이) K번째 수, 가장 큰 수, H-Index

정렬

K번째 수

문제 설명
배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항
array의 길이는 1 이상 100 이하입니다.array의 각 원소는 1 이상 100 이하입니다. commands의 길이는 1 이상 50 이하입니다. commands의 각 원소는 길이가 3입니다.

입출력 예
array: [1, 5, 2, 6, 3, 7, 4]
commands: [[2, 5, 3], [4, 4, 1], [1, 7, 3]]
return: [5, 6, 3]

입출력 예 설명
[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

# 내가 짠 코드
def solution(array, commands):
    answer = []
    for command in commands: # commands 길이가 1~50이라는 점에서 원소 자체로 접근
        answer.append(sorted(array[command[0]-1:command[1]])[command[2]-1])
    
    return answer

매우 간단한 정렬 문제로, 인덱스를 활용하면 쉽게 해결할 수 있다. 

가장 좋아요를 많이 받은 코드는 아래와 같다. map() 함수와 lambda를 사용하여 리스트에 append하지 않고 한줄로 끝냈다. 

# 모범 참고 코드
def solution(array, commands):
    return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands))

---

가장 큰 수

문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항
numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예
numbers:                 return:
[6, 10, 2]                 "6210"
[3, 30, 34, 5, 9]         "9534330"

# 내가 짠 코드
def solution(numbers):
    convert_str = []
    for number in numbers:
        convert_str.append(str(number))
    
    answer = sorted(convert_str, key=lambda x: x*4, reverse=True)
    return str(int(''.join(answer))) # [0, 0, 0, 0] -> '0'을 위해 int 추가

(참고) sorted(object, key=lambda x: (x*4, x-2)) 처럼 정렬 조건을 여러 개 선언할 수 있다. 첫 번째로 선언한  조건대로 정렬하고, 그 뒤에는 두 번째 선언한 조건대로 정렬한다.

이 문제는 처음 봤을 때 stuck 되었는데, 그 이유는 모든 경우의 수를 구해서 정렬해야 하나? 라고 생각했기 때문이다. 하지만 이는 불가능하다 생각했고, 그럼 어떤 "편법"을 써야 풀 수 있을지 고민했다. 코딩이 아니라 수학 문제라 나올 법한 문제처럼 보이니 점점 첫 번째 자리에 위치한 숫자가 큰 것이 맨 앞에 위치해야 한다는 느낌이 스물스물...

[3, 30, 34, 5, 9]에서 9가 당연히 맨 앞에 나와야 하고, 그다음 5일 것이다. 여기서 문제! [3, 30, 34]는 어떻게 비교할 것인가? 출력을 보면 "9534330"이고, 34 -> 3 -> 30 순서임을 알 수 있다. 어떤 기준일까 계속 고민했다. 두 번째 자리 비교? 세 번째 자리 비교?...

아! 문제에서 원소는 1 이상 1,000 이하라 했다. 즉 1,000자리로 모두 변환한 후(3434, 3333, 3030처럼 말이다) 비교해보면 34 -> 3 -> 30 순서가 나온다는 것을 발견했다. 이렇게 생각한 후 sorted의 key를 사용하고 reverse=True로 역정렬했다. 

아래를 참고하며 느낀 것은 map() 함수 잘 사용하면 편리하다! 는 것 ㅎㅎ

# 모범 참고 코드
def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

---

H-Index 

문제 설명
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다.
어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.
어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항
과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다. 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예
citations: [3, 0, 6, 1, 5]
return: 3

입출력 예 설명
이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다.
그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

def solution(citations):
    answer = 0
    sor_cite = sorted(citations, reverse=True)
    for ele in sor_cite:
        answer += 1
        if ele == answer: # 인용 수와 논문 수가 같을 때가 있을 경우
            return answer
        elif ele < answer: # 인용 수와 논문 수가 다르고, 논문 수보다 작을 때
            return answer - 1
    return answer

이 문제를 풀기 위해 아래 H-지수를 계산하는 방법을 설명한 자료를 참고했다. h번 이상 인용된 논문이 h편 이상이라는 말은 바꿔 말해 적어도 h번 이상 인용된 논문이 h편 있다는 것이다.  

<출처: BRIC>

아래는 sorted()를 reverse 없이 그대로 정렬했고, 따라서 l-i 를 통해 비교했다. 위의 표를 뒤집은 것이라 생각하면 쉽다. if 문을 한 번만 돌려도 되기 때문에 더 깔끔하다. 

# 모범 참고 코드 1
def solution(citations):
    citations = sorted(citations)
    l = len(citations)
    for i in range(l):
        if citations[i] >= l-i:
            return l-i
    return 0

아래는 사람들이 가장 신기해한 코드이다. 파이썬의 내장 함수를 최대한 활용한 것인데, 이해가 안 되었기 때문에 하나하나 뜯어고쳐 봤다. 

# 모범 참고 코드 2
def solution(citations):
    citations.sort(reverse=True)
    answer = max(map(min, enumerate(citations, start=1)))
    return answer

먼저, enumerate() 함수는 리스트 원소에 인덱스를 붙이고 이터레이션 객체를 반환한다. 아래와 같은 결과가 나온다.

test = [31, 66, 12, 3, 5, 20]
for i in enumerate(test): # 객체이기 때문에 for문을 써서 출력
    print(i)

이후 map() 함수를 사용하고, enumerate 내부 각 원소에서 min 값을 찾는다. map 결과값 역시 이터레이션 객체다. 

for i in map(min, enumerate(test)):
    print(i)

(0, 31)에서는 0이, (1, 66)에선 1이, (2, 12)에선 2가 최솟값이다

자, 이제 위의 코드를 다시 살펴보면 왼쪽 인덱스(=논문 수)가 오른쪽 인덱스(=인용 수)보다 작은 원소 중에서 최댓값을 찾는다는 것을 알 수 있다. 결국 위 그림에서 살펴본 것과 똑같은 방식으로 문제를 푸는 것이지만, 내장 함수를 얼마나 활용하냐에 따라 다른 코드가 나온 것이다.