[고득점Kit][정렬] K 번째 수 ⭐

[정렬] K 번째 수

난이도 ⭐

문제

내 풀이 ⭕

제출 한 후 다른 분의 풀이를 봤는데 내 풀이와 너무 똑같아서 놀랐다.

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    vector<int> temp;
    
    for (auto & elem : commands)
    {
        temp = array;
        sort(temp.begin() + elem[0] - 1, temp.begin() + elem[1] - 1 + 1);
        answer.push_back(temp[elem[0] - 1 + elem[2] - 1]);
    }
    
    return answer;
}

• temp 벡터를 또 선언하여서 for문 내에서 매 반복마다 array벡터로부터 복사 대입 받았다.
  • 그냥 매 반복마다 array를 정렬하면 이전에 i,j 값으로 일부분만 정렬한 array로 연산하는 것이기 때문에 결과가 달라질 수 있다. 인수로 넘겨받은 처음 array 그 모습을 가지고 정렬하기 위해서 매 반복마다 처음 array 그 모습을 대입받기 위한 temp 벡터를 선언.
    • vector 컨테이너는 = 연산자가 오버로딩 되어 있기 때문에 서로 다른 두 벡터끼리 = 연산을 하면 벡터 원소들을 전부 복사 대입받을 수 있다.
• i 번째, j 번째, k 번째 이런식이므로 1 빼주어야 한다.
• sort(a, b) a 반복자를 포함하고 b 반복자는 포함하지 않는다. b 반복자 이전까지만! [a, b) 범위를 정렬시킨다.
  • 따라서 두번째 인수엔 1 을 더해주었다.
    • sort(temp.begin() + elem[0] - 1, temp.begin() + elem[1] - 1 + 1);
      • 예를 들어 5 번째 ~ 7 번째를 정렬해야 한다면
        • sort([4]원소를 가리키는 반복자, [7]원소를 가리키는 반복자) 가 되어 인덱스 4 ~ 6 이 부분만 정렬이 된다.
• answer에 넣을땐 i - 1 (정렬 시작 인덱스)에서 k - 1 (k 번째)만큼을 더한 결과가 되는 인덱스에 위치한 원소를 삽입하면 된다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기