[프로그래머스 Level 1] [정렬] K번째수 (C++)

이번에는 새로운 주제로 돌아왔습니다. 

출제빈도 높음, 평균점수 높음을 자랑하는 정렬입니다.

가장 난이도가 낮기도 하고 중요하기도 한 주제이기 때문에 반드시 확실하게 알아두고 가야 할 주제라고 생각합니다.

 

출처 : 프로그래머스 코딩테스트 연습 고득점KIT, programmers.co.kr/learn/courses/30/lessons/42748

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

목차

• 0. 문제 설명
  • 0.0. 제한사항
  • 0.1. 입출력 예
  • 0.2. 입출력 예 설명
• 1. 풀이 과정
• 2. 소스 코드
• 3. 후기

---

0. 문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

0.0. 제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

 

0.1. 입출력 예

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

 

0.2. 입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

---

1. 풀이 과정

처음에는 string이랑 착각해서 substr을 사용하려고 했다가 한 15분 삽질했습니다 ㅋㅋㅋㅋㅋ

 

다시 정신 차리고 보니 vector였기때문에, 인덱싱을 사용해서 새로운 벡터에 잘라낸 벡터를 저장하기로 했습니다.

for문을 commands의 size만큼 돌립니다. for문 안에 다시 for문을 만들어서 commands[i]의 첫 번째와 두 번째 요소를 가져와 그 부분만 잘라냅니다. 컴퓨터가 아닌 사람의 번째를 이용한 문제이기 때문에 출발지에 -1을 해줍니다. (도착지에는 미만이 아니라 이하이기 때문에 -1을 해 줄 필요가 없습니다! 이해가 잘 안되시면 예시를 천천히 읽어보시면 됩니다.)

 

필요한 부분을 temp로 빼냈으면 이제 정렬합니다. sort를 사용했기 때문에 algorithm을 include해줍니다.

 

정렬이 끝나면 temp에서 commands[i][2]-1번째 수를 찾아서 answer에 넣어주면 끝입니다.

---

2. 소스 코드

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    for(int i = 0; i < commands.size(); ++i){
        vector<int> temp;
        for (int j = commands[i][0]-1; j < commands[i][1]; ++j) // 1. array에서 필요한 부분 잘라냄
            temp.push_back(array[j]);
        sort(temp.begin(), temp.end()); // 2. 정렬한다
        answer.push_back(temp[commands[i][2]-1]); // 3. 인덱싱해서 answer에 넣는다
    }
    
    return answer;
}

 

---

3. 후기

 

정말 오랜만에 보는 level1이었기 때문에 10분컷 하려고 노력했습니다만 너무 서둘렀는지 문제를 제대로 못읽고 string으로 생각하는 실수를 저질렀습니다.. 덕분에 15분 순식간에 까먹고 정신을 차렸네요.

여러분들도 쉬운 문제라고 대충 생각하면 저처럼 되니 조심하시기 바랍니다(?)