[프로그래머스/Level1] K번째 수 (C++)(Python)

ziwon.k·2021년 5월 2일

C vector 백준 알고리즘 코딩테스트 코테 프로그래머스

[프로그래머스] 연습문제

목록 보기

8/10

프로그래머스 - Lv1.K번째 수

1.문제

2. 접근/체크 포인트

배열을 잘라서 복사할 임시 벡터가 필요.
(벡터를 복사하는 방법을 알아야 함.)

answer 벡터에 답을 하나씩 추가 해서 최종 결과로 벡터를 return 함.

commands의 0열은 벡터 복사 시작점, 1열은 벡터 복사 종료점, 2열은 K. (answer 벡터에 추가할 값.)

3. 해결 방법

정해진 범위의 array 벡터를 임시 벡터인 new_arr에 복사.

이때, 각 케이스 별로 (commands의 한 행 마다)
벡터의 시작점 + commands의[i][0] - 1 인덱스에서 복사를 시작해서
벡터의 시작점 + commands[i][2]까지 복사.

k는 정렬 후 new_arr의 k번째 인덱스를 찾아야하기 때문에 commands[i][2]에서 1을 빼줌.
혹은 answer.push_back(new_arr[k-1])도 가능.

 for(int i =0; i<commands.size(); i++){
        int s = commands[i][0]-1;
        int e = commands[i][1];
        int k = commands[i][2]-1;
        vector<int> new_arr(array.begin()+s, array.begin()+e); }

복사한 임시 벡터를 오름차순으로 정렬.

sort(new_arr.begin(), new_arr.end());

3.오름차순 정렬된 new_arr에서 k번째 원소를 answer 벡터에 추가.

answer.push_back(new_arr[k]);

임시 벡터 new_arr 초기화.
1-4번까지 과정을 commands의 원소 수 만큼 반복.

new_arr.clear();

4. 전체 코드

1. C++ 코드

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    for(int i =0; i<commands.size(); i++){
        
        int s = commands[i][0]-1;
        int e = commands[i][1];
        int k = commands[i][2]-1;
            
        vector<int> new_arr(array.begin()+s, array.begin()+e);
        sort(new_arr.begin(), new_arr.end());
        answer.push_back(new_arr[k]);
        new_arr.clear();

    }
        return answer;
}

2. Python 코드

def solution(array, commands):
    answer = []
    
    tmp = []
    l = len(commands)
    
    # i, j, k 추출하기
    for x in range (l):
        i = commands[x][0] - 1
        j = commands[x][1] - 1
        k = commands[x][2]
        
        
        # i부터 j까지 추출해서 tmp에 추가하기
        for i in range (i, j+1):
            tmp.append(array[i])
            
        # tmp 정렬
        tmp.sort() 

        # k번째 수 answer[]에 추가
        answer.append(tmp[k-1])
        
        # tmp 리스트 초기화
        tmp.clear()

    
    return answer

5. 참고 사항

👉 vector를 복사하는 방법.

1. = 연산자 이용.
v1 = v2; //v2를 v1에 복사 
생성자 이용.
 vector<int> v1(v2);  //v2와 똑같은 요소를 가지는 v1 생성

👉벡터를 또 다른 벡터로 복사 vs 배열을 벡터로 복사.

1. 벡터 > 벡터 복사

begin() : 벡터의 첫 번째 요소를 가리킴.

back() : 벡터의 마지막 원소를 가리킴.

end() : 벡터의 마지막 원소의 다음 위치를 가리킴.
vector<int> v
vector<int> new_v(v.begin(), v.end());  //시작점과 종료점 입력
배열 > 벡터 복사
int data[] = {1,2,3,4,5,6,7,8,9}
//시작점과 종료점 입력, data 배열의 첫 번째 원소부터 5개 복사됨.
vector<int> v(data, data+5); 
이 부분을 책에서 보고 K번째 수 문제를 풀 때 위의 방식대로 했다가 계속 틀렸다. 배열을 벡터로 복사할 경우 begin() 함수를 안쓰고 그냥 배열 이름과 숫자로 범위를 지정해줄 수 있는데(배열의 이름은 포인터로, 배열의 첫 주소랑 마찬가지!) 벡터를 벡터로 복사할 때는 이렇게하면 오류가 난다.

👉vector 원소 정렬하기.
1. C++ 에서 정렬함수인 sort()를 이용하려면 algorithm 헤더파일을 include 해야한다.
#incldue<algorithm>
sort(정렬 범위의 시작 위치, 정렬 범위 종료 위치)
sort(v.begin(), v.end());  // 오름차순, default
sort(v.begin(), v.end(), less<>());  // 오름차순
sort(v.begin(), v.end(), greater<>());  // 내림차순

👉 vector 끼리 비교할 때, == 나 != 사용 가능, 벡터의 요소의 개수와 값이 모두 일치하면 true 반환.

6. 다른 방법으로 풀어보기

array 전체를 temp에 복사해서 필요한 구간만 정렬해서 사용하는 방식.

#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(int i = 0; i < commands.size(); i++) {
        temp = array;
        sort(temp.begin() + commands[i][0] - 1, temp.begin() + commands[i][1]);
        answer.push_back(temp[commands[i][0] + commands[i][2]-2]);
    }

    return answer;
}