[정렬] 프로그래머스 3문제

1. K번째 수

링크 - K번째 수

코드

def solution(array, commands):
    answer = []
    for comm in commands:
        start=comm[0]-1
        end=comm[1]
        arr = array[start:end]
        arr.sort()
        answer.append(arr[comm[2]-1])
    return answer

간단한 문제!
commands에서 주어진 범위를 잡고, 내장함수를 이용해 정렬을 해주면 되는 문제였다.

2. H-index

링크 - H-index

코드

def solution(citations):
    answer = 0
    citations.sort(reverse=True)
    start= citations[0]
    
    for h in range(start,0,-1):
        count=0;
        for j in range(len(citations)):
            if h<=citations[j]:
                count+=1
            else:
                break
    
        if count>=h and len(citations)-count<=h:
            return h
    return answer

문제를 이해하는 데 시간이 꽤 걸렸다.
질문 게시판과 사이트에서 제공했던 위키백과 자료를 잘 읽어봐야했었다.

주의해야 할 점은
1. h-index는 배열에 있는 값이 아닐 수도 있다.
2. count와 h-index를 헷갈리면 안된다.
-> 질문 게시판에 있던 테스트케이스가 도움이 됐었다.(input - [2,2,2,2,2] output-2)

3. 가장 큰 수

링크 - 가장 큰 수

코드

import functools

def cmp(num1,num2):
    str1 = num1+num2
    str2 = num2+num1
    if str1>=str2:
        return 1
    else:
        return -1
def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(cmp),reverse=True)
    answer = str(int(''.join(n)))
    return answer

전에 C++로 푼 적이 있어 python으로 바꿔주었다.
sorted함수의 key 매개변수를 이용하려고 했는데 cmp함수의 매개변수가 2개 이상인 경우에는
functools의 cmp_to_key()함수를 사용해야 한다고 한다.

python 문서 - https://docs.python.org/ko/3/library/functools.html#functools.cmp_to_key

include <string>
include <vector>
include <algorithm>

using namespace std;

bool cmp(int num1, int num2){
    string s1 = to_string(num1) + to_string(num2);
    string s2 = to_string(num2) + to_string(num1);
    return s1 > s2;
}
string solution(vector<int> numbers) {
    string answer = "";
    sort(numbers.begin(), numbers.end(), cmp);
    for(auto i : numbers) answer += to_string(i);
    
    return answer[0] == '0' ? "0" : answer;
}

참고로 예전에 풀었던 c++코드는 이렇다.

아이디어는 먼저, 배열에 있는 값들을 문자열의 형태로 바꾸어준다.
그 후 문자열 2개를 번갈아 더해보며 비교를 하면서 배열에 넣어주는 방식이다.

다른 코드

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

후덜덜....

2번째 줄을 이해하기 위해서는 문자열의 대소비교 방법을 알아야 한다.

<문자열 비교 연산 과정>
예를 들어 33과 34가 있을 때, 문자열은

33 [0]인 3과 34 [0]인 3을 비교한다. 둘 다 값이 같기 때문에
그 다음 인덱스로 비교해서 3과 4를 비교하게 된다.
=>34가 33보다 크다라고 출력을 하게 된다.

실행	결과

각 원소의 값은 1000이하이므로 문자열을 3번 붙여서 3번째 자리까지 비교를 할 수 있게 했다.

ex - [2,203,234]가 input으로 들어오면

문자열을 3번 이어붙여서
[222, 203203203, 234234234]이렇게 되고

비교를 할 때
22와 20까지만 비교를 하게 된다.

이런 방식으로 연산을 하면 numbers 정렬에서 reverse=True로 했기 때문에 내림차순으로 정렬되어 정답이 나오게 된다.