Algorithm

[ Python ] 정렬 (2) - list 예시

jogaknabi_1023 2024. 4. 5. 04:48

문제)

배열 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 함수를 작성해주세요.

 

 

코드)

def solution(array, commands):
    answer = []
    for a,b,c in commands:
        arr = array [a-1:b]
        arr.sort()
        answer.append(arr[c-1])
    return answer

 

commands 에서는 리스트 안에 3개의 리스트가 들어가 있는 개념이다.

for a,b,c in commands: 로 리스트들에 대한 처리를 순회하면서, 각 리스트에서 a, b, c에 해당하는 값을 가져와 사용한다.

입출력 예를 보면 2,4,1 이 a 에 해당되는 꼴이다. (a, b, c 말고 i, j ,k로 해도 됨.)

그리고 주의할 점은 리스트의 '몇 번째'를 기준으로 리스트를 슬라이싱하기 때문에 인덱스 개념을 함께 생각하며 문제를 풀어야한다.

 

 

문제)

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

 

제한사항

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


코드)

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

 

  • str_numbers = list(map(str,numbers))
    map 함수를 이용하여 숫자를 문자로 변경.
  • str_numbers.sort(key=lambda x: x*3, reverse=True)
    문자열 비교를 통해 큰 순서대로 정렬.
  • answer = str(int(''.join(str_numbers)))
    정렬된 문자를 합쳐 하나의 문자열로 만듦.

 

여기서 이해하는데 시간을 오래 잡아먹었던 이유가 바로 (key=lambda x: x*3, reverse=True) 이 부분이었다.

먼저 sort 함수에서 특정한 범위를 기준으로 정렬되게끔 하는 key=lambda 식을 사용하였는데, 반복할 단위의 각 원소를 x라고 가정한다면 x*3 의 값을 기준으로 내림차순하는 코드이다. 여기서 문자를 3번 반복하는 이유는 numbers의 원소는 0 이상 1,000 이하이기 때문에 리스트 안의 각각의 문자를 3자리수로 맞춘 후 비교를 통해 정렬을 시도한다.

 

하지만 입출력 예시를 봤을 때 666, 101010, 222 인데 어떻게 내림차순을 했을 때 666, 222, 101010 이 되는지 이해가 가지 않았다. 여기서는 숫자가 아닌 문자에서의 사전순 비교 결과로 내림차순하기 때문에 내가 생각했던 큰값이 냅다 앞으로 오는 정렬 기준이 아니었다. 사전순 비교 결과란 앞에서부터 차례대로 각 문자를 비교하는 것으로 101010 에서는 '1', 666 에서는 '6', 222에서는 '2'로 6>2>1 이기 때문에 6,2,10 으로 정렬되어 return값이 6210 이 나오게 된다.

 

 

문제)

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.
어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

코드)

def solution(citations):
    citations.sort(reverse=True)  # 인용 횟수를 내림차순으로 정렬
    n = len(citations)  # 논문의 총 개수
    answer = 0
    for i in range(n):
        if citations[i] >= i+1:  # citations[i]가 리스트 안에서 citations[i]보다 크거나 같은 수들의 개수와 같은 경우
            answer = i+1
        else:
            break
    return answer

 

맨 처음에는 else :break 적어주지 않고 코드 실행하니 하나의 테스트 케이스에서 런타임 에러가 걸렸다.