정렬 알고리즘의 실습.
코딩 테스트를 준비하기에 프로그래머스가 가장 적합하다고 생각하여 프로그래머스에 있는 연습문제들을 풀어보려 한다. 이해하기 어렵지 않게, 익숙지 않은 라이브러리를 가져와 구현하는 방법은 최소화하려 한다. 기본에 충실해 최대한 이해를 하고 넘어가도록 설명을 하려 한다.
해당 문제는 프로그래머스의 K번째수 라는 연습문제입니다.
============================================================================
문제 설명
배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
- array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
- 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
- 2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- array의 길이는 1 이상 100 이하입니다.
- array의 각 원소는 1 이상 100 이하입니다.
- commands의 길이는 1 이상 50 이하입니다.
- commands의 각 원소는 길이가 3입니다.
입출력 예
arraycommandsreturn
| [1, 5, 2, 6, 3, 7, 4] | [[2, 5, 3], [4, 4, 1], [1, 7, 3]] | [5, 6, 3] |
입출력 예 설명
[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입니다.
============================================================================
항상 C++ 코딩테스트들을 준비하면서 배열의 길이를 변경해도 지장이 없는 문제를 접근할 시에는 array를 택하기보다는 vector를 택하는 편이다. vector는 선언 시 배열의 길이를 지정하지 않아도 되며 길이 변경이 용이하고, 배열 안의 값을 삭제하는 동시에 배열 전체의 길이를 줄일 수 있기 때문이다. 배열 문제를 푸는 경우 vector의 개념을 잘 몰라 겁이 날 수 있다. 물론 꼭 array를 사용을 해야 하는 경우도 있겠지만, 그러한 특별한 경우가 아니라면 array에 집착하여 쉬운 문제도 어렵게 가는 일을 최대한 없도록 하자(경험담).
문제 분석
배열을 주어주고, 배열 중 i번째부터 j 번째 까지만 볼 때, 그 부분 중 k 번째로 작은 값을 answer에 삽입하길 원한다. -> 해당 과정을 3번 반복하는 문제.
1. i번째부터 j 번째까지만 본다
-> c++에서 배열의 인덱스(몇 번째인지 위치를 나타내는 정수)는 0부터 시작한다. 우리는 가장 앞을 첫 번째라고 하지만, c++에서는 가장 앞을 0 번째라고 한다. 따라서 원하는 위치를 참조하고 싶다면 -1을 해줘야 한다.
ex) 배열에서 3번째 위치의 값을 알고 싶다면 array[2] 를 해야 한다. 0,1,2 번째 인덱스로 취급을 하기 때문이다.
2. k 번째가 아닌 k 번째로 작은 값
-> 위치를 원하는 것이 아니므로, 정렬을 한 후 정렬된 상태에서 몇 번째인지 파악하면 된다. 배열을 정렬을 하려고 우리는 for문을 여러 번 돌리는 대참사를 가져오지는 말자. 배열의 오름차순 정렬을 하는 방법은 #include <algorithm>으로 algorithm이라는 라이브러리를 가져와, 그곳에서 sort라는 구현된 함수를 바로 사용하면 된다.
ex) sort(arr.begin(), arr.end()); // 시작점부터 끝부분까지 정렬을 하겠다 라는 함수
3. answer에 삽입하길 원한다
-> 과정을 3 번 반복하는데 그 값들을 차례로 answer이라는 벡터에 삽입을 하는 과정. array로 한다면 미리 길이를 지정하고, 그 길이만큼만 값을 저장할 수 있지만, vector 에는 길이를 정하지 않아도 되며 동적으로 길이가 변화할 수 있다는 장점이 있다. vector에는 push_back이라는 기능이 있다. 해당 기능은 벡터의 맨 뒤에 값을 삽입하며 길이를 그만큼 늘려주는 기능이다.
ex) v.push_back(값); // 벡터의 마지막에 값을 삽입하며 길이가 증가.
#include <string>
#include <vector>
#include <algorithm>
// sort 라는 정렬함수를 사용하려 algorithm 이라는 라이브러리를 가져옴
// algorithm 은 코딩 테스트에 유용하게 사용되니 기억하도록하자.
using namespace std;
vector<int> solution(vector<int> array, vector<vector<int>> commands) {
vector<int> answer; // 문제에서 주어진 answer 라는 벡터
for(int i = 0; i < commands.size(); i++ )
{
vector<int> v;
// 새로운 v 라는 벡터를 만들었다.
// 매번 다시 사용하려고 계속 answer을 수정하고 싶지 않아서
for(int j = commands[i][0]-1; j < commands[i][1]; j++)
// 배열의 index는 0부터 시작하므로 -1을 하여 참조하는 것이다.
{
v.push_back(array[j]);
// 생성한 v라는 벡터에 기존 배열을 자르는 시작과 끝의 위치를 넣어
// 배열의 해당 부분을 넣는다.
}
sort(v.begin(),v.end());
// 값이 삽입된 벡터 v를 정렬한다(오름차순)
answer.push_back(v[commands[i][2]-1]);
// 잘라서 정렬된 배열 중 k번째 값을 answer에 차례로 삽입한다.
}
return answer;
}
