[파이썬] 코딩테스트 문제 풀이 - 정렬 문제 (프로그래머스)

Writer: Harim Kang

정렬 문제 - 프로그래머스

다양한 정렬을 사용하여 해결하는 알고리즘 문제들입니다.
해당 포스팅에서 푸는 문제는 아래의 3문제 입니다.

1. K번째수
2. 가장 큰 수
3. H-Index

해당 문제들은 프로그래머스의 코딩테스트 연습 > 코딩테스트 고득점 kit > 정렬에 모여있는 3문제 입니다.

https://programmers.co.kr/learn/courses/30/parts/12198

프로그래머스

1. K번째수(Level 1)

문제

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

문제 요약

• 배열 array가 주어지고, [i, j, k]를 원소로 가지는 2차원 배열 commands가 주어집니다.
• 주어진 배열을 먼저 i부터 j까지 자릅니다.
• 자른 배열을 오름차순으로 정렬하여 k번째의 수를 answer에 추가합니다.
• 위의 방법을 commands의 주어진 수만큼 반복하여 answer를 채워서 리턴합니다.

제한 사항

• 배열 index를 고려하여 풀면 됩니다.

테스트 케이스

해결

• 간단하게 내부 함수로 하여 배열을 자르고, 정렬하는 것까지 만들었습니다.
• command 별로 각 함수를 수행하고 answer 배열에 담았습니다.

코드

def solution(array, commands):

    def com(arr, a, b, c):
        arr = arr[a-1:b]
        arr.sort()
        return arr[c-1]

    answer = []
    for x, y, z in commands:
        answer.append(com(array, x, y, z))

    return answer

2. 가장 큰 수(Level 2)

문제

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

문제 요약

• 여러 양의 정수들이 담긴 배열 numbers가 주어집니다.
• 이 numbers들을 이어붙여서 만들 수 있는 가장 큰 수를 구하면 됩니다.
• 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

제한 사항

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

테스트 케이스

• 추가 테스트 케이스

    test_case = [[0, 0, 0, 0, 0], [40, 403], [40, 405],
                 [40, 404], [12, 121], [2, 22, 223],
                 [21, 212], [41, 415], [2, 22], [70, 0, 0, 0],
                 [0, 0, 0, 1000], [12, 1213], [0, 0, 1000, 0],
                 [0, 1000, 0, 0], [121, 12], []]
    for tc in test_case:
        print(solution(tc))
    """
    0
    40403
    40540
    40440
    12121
    223222
    21221
    41541
    222
    70000
    1000000
    121312
    1000000
    1000000
    12121
    """

해결

• 해당 문제는 일반적인 정렬로는 풀리지 않거나 시간초과가 나게 됩니다.
• 우선, numbers의 정수들은 1000이하입니다. 1자리부터, 4자리까지 있다는 의미입니다.
• 그래서 저는 1, 2, 3, 4자리의 수들을 비교하기 위해서 이 수들을 모두 1, 2, 3, 4의 최소공배수인 12로 수들을 반복하여 자리수를 통일 시켜주었습니다.
• 예를 들어, 34, 3, 312이 있다면, 343434343434, 333333333333, 312312312312 로 반복하여 12자리의 수가 되도록 하여 비교하였습니다.
• 위의 예제를 사용하면 34 > 3 > 312 순서로 나와야 큰 수 임을 알 수 있습니다.
• so라는 배열에 [12자리로 늘린 수, 원래의 수] 배열을 다 담아서 이를 정렬하였습니다. (12자리로 늘린 수를 기준으로 정렬)
• 그 후, 하나씩 꺼내서 정답에 추가하는 방식으로 사용하였습니다.
• 이때, 0000과 같은 수는 '0'으로 통일 시켜주어야 모든 테스트 케이스를 통과합니다. (이것때문에 고생했습니다..!)

코드

def solution(numbers):

    answer = ''
    so = []
    for o in numbers:
        o = str(o)
        sz = 12//len(o)
        so.append([o*sz, o])
    so.sort(reverse=True)
    for _, s in so:
        answer += s
    if answer and int(answer) == 0:
        answer = '0'

    return answer

3. H-Index(Level 2)

문제

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

문제 요약

• 과학자의 생산성과 영향력을 나타내는 H-Index는 아래와 같이 구합니다.
• 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
• citations는 어떤 과학자의 논문들 인용 횟수를 담은 배열입니다.
• 해당 과학자의 H-Index를 찾는 문제입니다.

제한 사항

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

테스트 케이스

• 추가 테스트 케이스

    tc = [[3, 0, 6, 1, 5], [0, 6, 6, 4, 5], [5, 5, 5, 5]]
    for c in tc:
        print(solution(c))
    # 3, 4, 4가 나와야 정상입니다.

해결

• citations의 가장 큰 수까지 반복문을 돌면서 체크하는 방법입니다.
• x 배열에는 현재의 h값보다 큰 값의 수만큼 1을 채우고, h는 현재 답이상, x의 총 길이 이하일 때, answer에 h를 전달합니다.
• [5, 5, 5, 0]과 같은 경우에는 3이란 정답이 나와야 정상입니다. 3번 이상의 인용된 논문이 3편있고, 나머지는 3보다 작기 때문입니다.
• 현재(20.04.23) 문제가 완벽한 정답이 아니라도 모든 케이스가 통과되는 경우가 있습니다. (range안의 값을 citations[-1] + 1이라고 해도 통과됩니다..//이건 답이 안될텐데...)

코드

def solution(citations):
    answer = 0
    for h in range(max(citations) + 1):
        x = [1 for _ in citations if _ >= h]
        if answer <= h <= len(x):
            answer = h

    return answer