코딩테스트 | (c++) 프로그래머스 : K번째수

✅문제

배열 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 함수를 작성해주세요.

❕ 제한사항

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

🎹📢입출력 예제

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

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

예제 #3
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

✍풀어보기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands);

int main() {
	vector<int> output = solution({ 1,5,2,6,3,7,4 }, { {2,5,3},{4,4,1},{1,7,3} });
	for (int i = 0; i < output.size(); i++) {
		cout << output[i] << endl;
	}

	return 0;
}

// 2차배열인 commands의 요소인 2차 배열의 데이터 구성은 i,j,k
// array의 i번째 부터 j번째 요소를 잘라내고 오름차순으로 정렬한다.
// k번째 숫자를 출력한다.(commands의 요소 개수만큼)
vector<int> solution(vector<int> array, vector<vector<int>> commands) {
	vector<int> answer;
	answer.reserve(commands.size()); // capacity 초기 설정

	int i, j, k; // commands 요소의 i, j, k

	for (int cnt = 0; cnt < commands.size(); cnt++)
	{
		i = commands[cnt][0] -1; // command의 i (index를 맞추기 위해 -1)
		j = commands[cnt][1]; // command의 j (j를 포함하기 위해 -1을 해주지 않았다)
		k = commands[cnt][2] -1; // command의 k

		// 새로 담을 배열 선언
		vector<int> newArray, sortArray;
		newArray.reserve(array.size());

		// i인덱스부터 j인덱스까지 추가
		for (int m = i; m < j; m++) {
			newArray.push_back(array[m]);
		}

		// -- vector의 멤버함수 assign를 이용한 복사 --
		// 이전에 있던 모든 원소를 삭제시키고 새로운 내용으로 덮어씌운다.
		// newArray.assign(array.begin() + i, array.begin() + j);

		// -- algorithm 라이브러리의 copy함수를 통한 복사 --
		// 복사할 사이즈가 확보되어야 하고, 이전에 데이터가 있으면 보존된다.
		// newArray.resize(j - i); // 복사할 사이즈를 확보
		// copy(array.begin() + i, array.begin() + j, newArray.begin());

		// 정렬
		sort(newArray.begin(), newArray.end());

		// 결과배열에 k인덱스 추가
		answer.push_back(newArray[k]);
	}

	return answer;
}

엄청나게 단순한 문제..

풀다보니 정렬에 대한 고민을 했었는데, 정렬이 핵심인 문제가 아니라는 판단에 algorithm 라이브러리를 사용해서 정렬해버렸다. 정렬 알고리즘을 구현해서 했다면 시간은 더 오래걸렸겠지?
다 풀고 나니 vector의 데이터를 복사하는 방법을 찾아보니, 2가지 vector의 멤버함수 assign과 algorithm 라이브러리의 copy함수가 있었다. 더 심플하고 좋잖아?!

---

참고 자료 및 사이트 (감사합니다)

• https://programmers.co.kr/learn/courses/30/lessons/42748