[Programmers] [C++] 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입니다.

<입출력 예>
array	commands	return
[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입니다.

---

#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 j = 0; j < commands.size(); j++) {
        for (int i = commands[j][0] - 1; i <= commands[j][1] - 1; i++) {
            temp.push_back(array[i]);
        }
    
        int number = commands[j][2] - 1;     	 //n번째 숫자

        sort(temp.begin(), temp.end());     	 //자른 후 정렬
        answer.push_back(temp[number]);          //해당 n번째 숫자 삽입
        temp.erase(temp.begin(), temp.end());    //자르고 정렬한 배열 초기화
    }
    
    return answer;
}

 

알고리즘 고득점 항목이 있길래 풀어보았다.

commands가 이차원 배열이기에 자칫 어디까지 자르고 몇번째를 골라서 넣는지 복잡해질 수 있다

 

1) 범위를 잘라서 넣을 새 배열을 temp로 정의한다

2) commands의 첫번째 요소부터 시작해서 두번째까지 원본 배열의 원소를 temp에 삽입한다

3) 한편, n번째 숫자를 고를 number 정수를 commands의 세번째 요소로 정한다.

4) 2번에서 삽입한 배열을 오름차순으로 정리한다.

5) 3번에서 정한 변수를 temp의 요소에서 인덱스로 넣고, 해당하는 수를 답안 배열에 삽입한다.

6) 여지껏 사용했던 임시 temp 배열을 초기화한다.

7) 이것을 commands 배열의 크기만큼 반복한다.

 

어쩌다보니 for문의 i와 j 문자를 거꾸로 사용했다. (보통은 i를 먼저 사용한다...)

규칙을 찾아 1~6번을 먼저 int i로 구현하고 마지막에 j로 덮어주어서 그런것 같다.

정렬 문제는 풀다보면 은근 재밌는 것 같다!

 

---

 

<문제 설명>
수포자는 수학을 포기한 사람의 준말입니다.
수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다.
수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때,
가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

<제한 조건>
시험은 최대 10,000 문제로 구성되어있습니다.
문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

<입출력 예>
answers		return
[1,2,3,4,5]	[1]
[1,3,2,4,2]	[1,2,3]

<입출력 예 설명>
-입출력 예 #1
수포자 1은 모든 문제를 맞혔습니다.
수포자 2는 모든 문제를 틀렸습니다.
수포자 3은 모든 문제를 틀렸습니다.
따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

-입출력 예 #2
모든 사람이 2문제씩을 맞췄습니다.

---

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

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    
    //각 수포자의 찍는 방식
    vector<int> num1 = {1, 2, 3, 4, 5};
    vector<int> num2 = {2, 1, 2, 3, 2, 4, 2, 5};
    vector<int> num3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
    
    //각 수포자가 맞은 문제 수
    int correct_1 = 0; 
    int correct_2 = 0;
    int correct_3 = 0;
    
    for (int i = 0; i < answers.size(); i++) {
        if (answers[i] == num1[i % num1.size()]) { correct_1++; }
        if (answers[i] == num2[i % num2.size()]) { correct_2++; }
        if (answers[i] == num3[i % num3.size()]) { correct_3++; }
    }
    
    int max_score = max({correct_1, correct_2, correct_3});   //세명 중 최다 점수
    
    if (max_score == correct_1) { answer.push_back(1); }
    if (max_score == correct_2) { answer.push_back(2); }
    if (max_score == correct_3) { answer.push_back(3); }
    
    return answer;
}

 

 

[C++] 여러 값 중 max, min을 찾을 때 아직도 이렇게 쓰시나요?

 

max, min 함수가 여러개도 가능함을 꼭 알아두자!! 이때 안을 { } 으로 묶어두기!

그리고 모든 경우의 수를 찾아보는 방법 = 브루트 포스 방법임을 알게 되었다.

코테를 풀며 노가다로 푸는 게 이미 일상이 되어서 따로 해당하는 명칭이 있는 줄 몰랐다....

 

그리고 for문에서 정답과 각 수포자의 정답을 비교할 때 왜 나머지로 요소 인덱스를 정했냐면, 각 수포자의 패턴이 반복되기 때문이다. 이전에 자료구조 큐에서 원형 패턴을 반복할 때도 이 식을 활용해서 요소를 삽입했던 것 같다