[프로그래머스-코딩테스트 연습] 정렬 - K번째 수 (20.01.29)

2020년 1월 29일 알고리즘 스터디 시작!

 

프로그래머스 코딩 테스트 연습 카테고리에서 정렬 선택

 

가장 첫 번째 문제인 K번째 수

 

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42748

코딩테스트 연습 - K번째수 | 프로그래머스

- Vector를 사용하여 코드를 작성하는 문제

- 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구해라

- commands는 array와 i, j, k로 이루어짐

- return값은 array별로 k번째 수를 저장

 

입출력 예

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

commands [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

return [5, 6, 3]

 

 

---

 

직접 작성해본 소스코드 및 간단한 설명

 

#include <string>
#include <vector>
#define SWAP(x,y,t) ((t)=(x), (x)= (y), (y)=(t))
using namespace std;
 
vector<int> editArray(vector<int>array, int min, int max) {
    vector<int> editted;
    for (int i = min; i <= max; i++)
        editted.push_back(array.at(i));
    return editted;
}
 
vector<int> sorting(vector<int> array) {
    int tmp;
    for (int i = 0; i < array.size() - 1; i++) {
        int min = i;
        for (int j = i + 1; j < array.size(); j++)
            if (array.at(min) > array.at(j))
                min = j;
        SWAP(array.at(i), array.at(min), tmp);
    }
 
    return array;
}
 
vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    int i, j, k;
    for (int m = 0; m < commands.size(); m++) {
        vector<int> tmp;
        i = commands[m].at(0) - 1;
        j = commands[m].at(1) - 1;
        k = commands[m].at(2) - 1;
        tmp = editArray(array, i, j);
        tmp = sorting(tmp);
        answer.push_back(tmp.at(k));
    }
    return answer;
}

 

 

● 배열 array의 i번째 숫자부터 j번째 숫자까지 자르는 editArray(vector<int>array, int min, int max) 함수

● 선택 정렬을 사용한 sorting(vector<int> array) 함수

● 기존에 제시되는 solution(vector<int> array, vector<vector<int>> commands) 함수에 코드 추가

 

 

 

---

 

코드 채점하고 제출한 결과

 

1003점

 

---

제출 후 다른 사람 풀이와 비교해본 소감

 

- vector를 좀 더 공부해보고 활용해보자

  vector 설명 사이트 : http://www.cplusplus.com/reference/vector/vector/

vector - C++ Reference

- 기존에 제공해주는 'algorithm.h'를 활용해보자

  algorithm.h의 sort 함수 

  'algorithm.h' 설명 사이트 : http://www.cplusplus.com/reference/algorithm/

- C++ Reference