[C++] 프로그래머스 K번째수

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

코딩테스트 연습 - K번째수

1. 서론

 

level 1짜리 간단한 문제이다. 정렬로 푸는 문제이다. 자잘한 실수만 안 한다면 신속하게 풀 수 있다.

 

2. 문제 풀이

 

배열이 있고 배열에서 잘라내고 싶은 index 범위와 알고 싶은 index를 알려준다.

 

예를 들어

 

1 5 2 6 3 7 4

 

라는 배열이 있다. 그리고 2, 5, 3이 입력된다.

 

이것은 2번째부터 5번째까지 배열을 자르고 정렬 후 3번째 값이 무엇인 지를 묻는 문제이다.

 

5 2 6 3 ->(정렬) 2 3 5 6 -> 5

 

이 예시의 경우 5가 답이다.

 

입력은 2차원 배열로 주어지며 그 안에 시작 index, 끝 index, 알고 싶은 index 세 항으로 여러 개의 값이 주어진다.

그럼 그 수만큼 값을 return 하는 문제이다. 

 

3. 코드 설명

 

#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    vector<int> tmp;
    int i, j, k, x, y, c = 0;
    
    for (i = 0; i < array.size(); i++)
        tmp.push_back(0);
    
    for (i = 0; i < commands.size(); i++)
    {
        c = 0;
        x = commands[i][0];
        y = commands[i][1];
        k = commands[i][2];
        
        for (j = x - 1; j < y; j++)
            tmp[c++] = array[j];
        
        sort(tmp.begin(), tmp.begin() + c);
        answer.push_back(tmp[k - 1]);
    }
    
    return answer;
}

 

array는 문제에서 주는 배열, commands는 입력값들이 담긴 값이다. answer에 답들을 담아 return 해야 한다.

tmp는 잘라놓은 배열 값을 임시로 담아두는 배열이다. c는 tmp의 길이를 count 해준다.

x는 시작 index를 y는 끝 index를 k는 n번째 값을 뜻한다.

for문을 x부터 y까지 돌리면서 tmp에 배열 값을 넣어준다. 정렬 후 답을 골라내 answer 배열에 넣어준다.