프로그래머스 문제 풀이 K번째 수

문제 URL K번째 수

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이번에도, 입력을 통해서 문제를 파악해보도록 하겠습니다. 문제의 입력은 이렇습니다.

 

입력 :
array = [1, 5, 2, 6, 3, 7, 4]
commands = [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

 

이제 commands에서 하나씩 꺼내서, 시작점, 끝점, 반환할 인덱스를 가져오겠습니다.

 

command = [2, 5, 3] //commands[0]
start = 2
end = 5
idx = 3

 

문제에 따르면, 인덱스가 0부터가 아닌 1로 되어 있습니다. 이를 조정해주어야 합니다.

 

command = [2, 5, 3]
start = 1 //인덱스 조정
end = 5
idx = 2 //인덱스 조정

 

즉, 인덱스가 0부터 시작하도록 start, idx를 1씩 줄여주어야 합니다. end는 안줄여도 됩니다. 왜냐하면, 보통 언어에서 vector, slice등을 잘라낼 때 start <= x < end 의 범위로 잘라내게 됩니다. 계속 진행해보도록 하죠. 이제 start 부터 end까지 array에서 잘라냅니다.

 

command = [2, 5, 3]
start = 1
end = 5
idx = 2
sub = [5, 2, 6, 3] // array[1:5] (1 <= x <5 범위를 자름)

 

이 sub를 오름차순으로 정렬합니다.

 

command = [2, 5, 3]
start = 1
end = 5
idx = 2
sub = [2, 3, 5, 6] //오름차순 정렬

 

여기서 idx에 해당하는 5를 answer에 넣어주면 됩니다.

 

command = [2, 5, 3]
start = 1
end = 5
idx = 2
sub = [2, 3, 5, 6]
answer = [5] //sub[idx]

 

이것을 commands를 모두 순회할 때까지 반복하면 됩니다. 다음은 이후 상황에서 벌어질 데이터들의 상황입니다.

 

두 번째:
command = [4, 4, 1]
start = 3
end = 4
idx = 0
sub = [6]
answer = [5, 6]

세 번째:
command = [1, 7, 3]
start = 0
end = 7
idx = 2
sub = [1, 2, 3, 4, 5, 6, 7]
answer = [5, 6, 3]

 

이렇게 해서 만들어진 answer를 반환하면 됩니다. 이 문제에서 따로, 우리가 프로그래밍적으로 생각할 필요는 없습니다. 그냥 풀면 되지요.

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

 

1. commands를 다음과 같이 순회합니다.
   1. command에서 첫 원소(sub 배열의 시작점)를 start, 두 번째 원소(sub 배열의 끝점)를 end, 세번째 원소(sub 배열의 반환 원소의 위치)를 idx를 꺼내옵니다.
   2. array에서 start-1 부터 end까지 잘라서 배열 sub를 만듭니다.
   3. sub를 정렬합니다.
   4. sub[idx-1]에 해당하는 원소를 answer에 넣습니다.
2. 이렇게 초기화된 answer를 반환합니다.

이를 코드로 표현하면 다음과 같습니다. 다음은 PYTHON 코드입니다.

 

PYTHON 코드

def solution(array, commands):
    answer = []
    # 1. commands를 순회합니다.
    for command in commands:
        # 1. start, end, idx를 command 에서 꺼내옵니다.
        (start, end, idx) = command
        # 2. array에서 start-1 ~ end 까지 잘라 배열 sub를 만듭니다. 이 sub를 정렬합니다.
        sub = sorted(array[start-1:end])
        # 3. sub[idx-1]을 answer에 반환합니다.
        answer.append(sub[idx-1])
    
    return answer

 

이번엔 CPP 코드입니다. 알고리즘은 동일하고, 언어만 바뀐 것입니다.

 

CPP 코드

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    for (const auto & command : commands) {
        auto start = command[0];
        auto end = command[1];
        auto idx = command[2];
        auto sub = vector<int>(array.begin() + start - 1, array.begin() + end);
        sort(sub.begin(), sub.end());
        answer.push_back(sub[idx - 1]);
    }
    
    return answer;
}

 

참고적으로 파이썬의 "리스트 컴프리헨션"을 이용하면, 한 줄로 풀 수도 있습니다. 다음은 한 줄로 파이썬 코드입니다.

 

PYTHON 코드

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