[TIL] 파이썬 sort()와 sorted() 차이 / 프로그래머스 - K번째수, 가장 큰 수

[Today I Learned]

프로그래머스 고득점 Kit 정렬 문제가 레벨도 낮고 3문제 밖에 안되길래, 쭉 풀어봤다.
그에 앞서 파이썬 sort()와 sorted() 차이를 잘 모르겠어서, 간단히 공부했다.

#  sort() / sorted()

- sorted()는 새롭게 정렬된 리스트를 return, 원래 리스트에는 영향을 주지 않음
-하지만 sort()는 리턴이 따로 없고 입력을 출력으로 덮어씀 

- sorted()는 문자열에도 사용가능한것과 달리 sort()는 리스트에만 사용할 수 있음

- 어떤 기준으로 정렬할 것인지 아래와 같이 key 옵션을 지정할 수 있다

# 데이터의 길이를 기준으로 정렬
sorted(data, key=len)

 

#  프로그래머스 - 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 함수를 작성해주세요.

 

@solution.py

def solution(array, commands):
    
    answer = []
    
    for start, end, idx in commands:
        arr = sorted(array[start-1:end])
        answer.append(arr[idx-1])
        
    return answer

 

#  프로그래머스 - 가장 큰 수

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

 

@solution.py

이 정도는... 쉽겠군... 하고 접근했다가 결국 구글링했다

처음에는 무작정 첫번째 자리수만 비교하면 되겠다고 생각했다가, 첫번째 자리수는 같고 두번째 자리수가 다른 수들의 예외처리를 어떻게 해줄 것인지 단계에서 막혔다.

1. 자리수 기반 룰 베이스로 규칙 생성
: 가장 처음 생각한 건 일단 첫번째 자리 수 기준으로 sort하고 첫번째 자리 수가 같은 애들만 다시 데려와서 다른 기준으로 sort하고... 이런 방법을 떠올렸었다. 인풋으로 주어지는 수가 1000 이하의 숫자라 불가능하진 않았겠지만... 첫번째 자리 수가 같은 숫자를 찾기 위해 반복문 돌고, 또 어디부터 어디였는지 index도 알고 있어야 재정렬후 다시 삽입해줄 수 있고 등등 문제가 유도하는 방향이 아니라는 생각이 들었다.

2. Sort 용 데이터 전처리?
: 1번 생각 과정을 거치는 중에... [3, 30, 34]가 자리수는 다르지만 같이 비교를 해야하는 상황이 생겼다. 이를 어떻게 처리해줄 수 있을까 생각하다, 3을 33으로 바꾸고 비교해도 괜찮다! 라는 생각을 하게 되었다.근데 그럼 [30, 34, 321] < 이렇게 숫자가 있을 때는 30과 34를 어떻게 전처리해야 321과 잘 비교할 수 있지? 일반화할 수 있는 아이디어를 떠올리는게 어려웠다.

 

구글링 결과,,,
다음과 같이 문자열을 3번 반복해 비교하면 된다고 한다. 이런걸 도대체 어떻게 생각하는지...? ㅠ_ㅠ

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

 

사람들 반응도 경이롭다 뭐 놀랍다 이런 식이어서... 내가 이걸 지금 본다고 다음에 적용할 수 있겠다는 생각은 전혀 들지 않았다,,ㅎㅎ 대신 두번째 풀이가 처음 보는 function을 사용하고 있어서 어떤 함수인지 공부해보기로 했다. (이 풀이가 더 낫다는 사람들도 일부 있었음)

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()
- sorted와 같은 정렬 함수의 key 매개변수에 함수를 전달할 때 쓰는 함수

- 음수를 return 하면 먼저 들어온 요소가 앞으로 정렬 되고, 양수를 return하면 나중에 들어온 요소가 앞으로 정렬, 즉 먼저 들어온 요소보다 앞 쪽에 배치된다고 한다. (0일 경우 바뀌지 않음)

 

#  프로그래머스 - H-Index

문제 설명

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

 

@solution.py

처음 딱 떠오른 아이디어대로 러프하게 구현했을 때는 통과하지 못한 케이스가 일부 있었다.
질문하기를 뒤지다보니 h_index 값이 꼭 citations 안에 있는 값은 아닐 수 있다는 사실을 알게 되었고, 접근 방법을 다시 생각해보게 되었다. 
(연산을 최소화하기 위해 citations 값 중 가장 최적화 된 값에서 출발해 1씩 줄여가도록 설계했었음)

입출력 예가 너무 적어요 ㅡㅡ

def solution(citations):
    
    citations.sort(reverse=True)
    
    answer = 0
    
    for i in range(len(citations)):
        if citations[i] >= i+1:
            answer = i+1
        else:
            break
    
    return answer

최종적으로 작성한 코드. 

정렬을 해놓고 비교 연산을 하다보니 모든 케이스를 다 셀 필요가 없다는 걸 알게 되었서 위와 같이 구현했다. 모든 citation 값이 0 인 경우에는 반복문이 돌지 않아서, initialize 하는 코드를 추가해줬다. 다만 반복문이 돌지 않은 경우~ 라는 느낌(?)이 나지는 않아서... 아래와 같이 작성하는 것이 더 좋을 것 같다!

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