[Python] 프로그래머스 코딩테스트 고득점 Kit - 정렬

chatGPT가 생각한 정렬

 

 

1. K번째 수 (Lv. 1)

https://school.programmers.co.kr/learn/courses/30/lessons/42748

# 이해
# 1. 슬라이싱
# 2. 정렬
# 3. 인덱스 return

def solution(array, commands):
    answer = []
    
    for command in commands:
        i, j, k = command[0], command[1], command[2]
        new_arr = array[i-1 : j]
        new_arr.sort()
        answer.append(new_arr[k - 1])
    
    return answer

 

 

 

2. 가장 큰 수 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42746

# 이해
# 문자열로 된 숫자를 조합해서, 생성 가능한 숫자 중 가장 큰 수 return

# 풀이
# numbers를 문자열의 배열로 변환
# 내림차순 정렬
# 배열 내의 원소를 하나로 합침

# 문제
# 문제의 조건에 따르면 우선순위가 다음과 같아야 함. 3 > 30
# 그러나 일반적인 정렬은 다음과 같이 정렬됨. 30 > 3
# 문제의 의도대로 정렬이 되려면, 3은 33으로 취급해야 함.

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

 

아래 방법은 주목할 만하다.

`str_numbers.sort(key=lambda x: x*3, reverse=True)`

 

문자열로 바꿔서 내림차순으로 정렬하면, 예컨대 3이 30보다 작은 수로 인식된다.

그러나 실제로는 3이 더 큰 수로 인식되어야 한다.

 

이것을 해결하기 위해 lambda로 같은 문자열을 반복한 후에 정렬을 한다.

`x*2`이 아니라 `x*3`을 하는 이유는, 입력된 숫자의 범위가 1 <= x <= 1000이기 때문이다.

 

예컨대 `x*2` 조건으로 9와 991을 정렬하는 경우, 99와 991991로 3번째 문자열 비교 때 991991이 우선 순위가 높아지게 된다.

이런 문제를 방지하고자 `x*3`을 사용해야 한다.

 

 

3. H-Index (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42747

# 이해
# 주어진 배열을 h를 기준으로 둘로 나눈다.
# 이때 h 이상인 배열의 길이가 h 이상이 된다. h 이하인 배열의 길이가 h 이하가 된다. 이것이 h-index.
# 이분탐색처럼 느껴지기도 한다.
# 그러나 n의 크기가 1000 이하 이므로 O(N ** 2)으로 완전탐색해도 되겠다.

# 풀이
# 배열을 정렬한다.
# 피봇 h를 정한다. 대략 길이의 절반쯤 위치의 인덱스로
# 피봇을 기준으로 큰 값과 작은 값을 계산한다.
# 피봇을 적당히 옮겨서 h의 최댓값을 구한다.


def solution(citations):
    citations.sort()
    n = len(citations)
    h_index = 0
    
    for i, citation in enumerate(citations):
        h = min(citation, n - i)
        h_index = max(h_index, h)
    
    return h_index

 

이 문제도 꽤 오래 고민했다.

`h = min(citation, n - i)` 부분이 직관적으로 와닿지 않았다.

---

h-index의 정의에 따르면,

"논문 중 h번 이상 인용된 논문이 h편 이상이고, 나머지 논문이 h번 이하 인용되었을 때, h의 최대값이 h-index"이다.

 

이를 효과적으로 계산하기 위해 다음 두 값을 고려하자.

1. citation: 현재 논문의 인용 횟수
2. n - i: 현재 논문을 포함해서 그 이상 인용된 논문의 수. (여기서 n은 논문의 총 수, i는 현재 논문의 인덱스(0부터 시작))

예를 들어, 논문이 인용 횟수에 따라 오름차순으로 정렬된 상태에서, 특정 위치 i에서의 논문 인용 횟수가 10회라고 가정하자.

그리고 이 논문이 전체 논문 중에서 상위 15번째에 위치한다면 (n - i = 15), 다음 두 가지를 고려해야 한다.

• 현재 논문은 10회 인용됨.
• 현재 논문을 포함하여 15편의 논문이 10회 이상 인용.

여기서 h-index의 조건을 만족시키기 위해 두 값 중 작은 값을 선택하자.

즉, min(10, 15) = 10이다.

이는 이 논문이 적어도 10번 이상 인용된 10편의 논문 중 하나임을 보장한다.

 

그러나 만약 이 논문의 인용 횟수가 20회이고, 같은 조건에서 n - i = 15라면,
min(20, 15) = 15가 된다.

이는 15편의 논문이 최소 15회 이상 인용되었음을 보여주며, h-index가 될 수 있는 후보이다.