[백준/BOJ] 2075번 : K번째 큰 수, 9658번 : 돌 게임 4, 11004번 : K번째 수

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2075번 : 'K번째 큰 수', 9658번 : '돌 게임 4', 11004번 : 'K번째 수'의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Silver ~ Gold 티어에 해당합니다.

 

 

2075번 : K번째 큰 수

 

N×N개의 수가 입력될 때 K번째로 큰 수를 출력하는 문제입니다.

문제의 난이도가 Gold 티어이므로 매번 정렬해서 K번째 수를 찾으면 시간 초과가 나도록 설계되어 있을 확률이 높습니다.

 

따라서 정렬을 사용하기보다는 우선순위 큐를 활용하여 값이 입력될 때마다 N번째 값을 top에 유지시키도록 하여 답을 구해보겠습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    priority_queue<int, vector<int>, greater<>> pQueue;

    for(int i=0; i<N*N; i++) {
        int value; cin >> value;

        if(pQueue.size() < N) pQueue.push(value);
        else if(value > pQueue.top()) {
            pQueue.pop();
            pQueue.push(value);
        }
    }

    cout << pQueue.top();
}

 

우선순위 큐와 조건문을 위와 같이 설계하면 N번째 큰 수가 항상 top에 위치하게 되면서 매번 비교를 통해 유지/교체되게 됩니다.

 

 

 

 

9658번 : 돌 게임 4

 

N개의 돌을 상근이부터 시작해서 1개, 3개, 4개 중 하나의 개수만큼씩 가져갈 수 있으며 마지막 돌을 가져가는 사람이 진다고 할 때 이기는 사람을 구하는 문제입니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    bool winner[1001] = {1, 0, 1, 0, 1}; // SK : 1 / CY : 0

    int N; cin >> N;

    for(int i=5; i<=N; i++)
        if(winner[i-1] && winner[i-3] && winner[i-4]) winner[i] = 0;
    else winner[i] = 1;

    if(winner[N]) cout << "SK";
    else cout << "CY";
}

 

돌이 N개 있는 상황에서 상근이가 1개, 3개, 4개를 가져가는 선택지 중 어떤 것을 선택해도 그 다음 상황에서 시작하는 사람이 이긴다면 상근이가 패배하게 됩니다.

따라서 winner[i]를 돌이 i개 있는 상황에서 이기는 사람을 기록하는 배열이라고 할 때, (이 문제에서는 1이면 SK, 0이면 CY라고 정의했습니다.) winner[i-1], winner[i-3], winner[i-4]가 모두 1이면 winner[i]는 0이라고 기록할 수 있습니다.

 

이러한 방식으로 N까지 기록한 뒤 답을 출력해주면 됩니다.

 

 

 

 

 

11004번 : K번째 수

 

N개의 수를 오름차순으로 정렬했을 때 앞에서부터 K번째 있는 수를 구하는 문제입니다.

다시 말하면 K번째로 작은 수를 출력해주어야 하며, 정렬 후에 K번째 수를 출력해주면 됩니다.

간단히 sort 함수를 사용하여 풀이하겠습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, K; cin >> N >> K;

    vector<int> arr(N);
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr.begin(), arr.end());

    cout << arr[K-1];
}