[BOJ/11968] High Card Wins, c++

🔗 링크

https://www.acmicpc.net/problem/11968

11968번: High Card Wins

🤯 한줄 후기

누가 카드 순서를 미리 알고 .. 불법 아님 ?

🤷 문제

👩‍💻 풀이

엄청 예전에 틀렸다가 오늘 개발하기 싫어서 다시 풀어보았다.

문제가 영어지만 간단히 해석해보면

elsie 와 bessie 가 1~2*round 가 적힌 카드를 가지고 둘이 반씩 나눠서 카드게임을 진행한다.

주어진 round 마다 더 큰 값이 적힌 카드를 내는 사람이 Point를 얻게 된다. 이때 elsie는 bessie의 카드 순서를 알고 있다.

elsie가 얻을 수 있는 점수를 계산하면 되는 문제이다.

이걸 머릿속으로 생각하면 진짜 너무 빠르게 된다. 그냥 bessie가 가지지 못한 카드중 bessie가 가진 카드보다 값이 더 큰 개수를 출력하면 된다. 그런데 ㄱ- 너무 오랜만에 (약 두달) PS 문제를 푸니까 진심 머리가 돌이 된 것 같음!!!!

무튼 나는 좀 거의 brute force 느낌으로 풀어서 8ms가 걸렸는데 나중에 4ms의 풀이를 보니까 훨씬 효율적이고 깔끔하게 풀었더라...

나는 bessie의 카드를 모두 vector에 넣어 놓고, sorting 해줬다. 이후에 bessie가 가지지 못한 카드를 elsie vector에 넣어 놓고 똑같이 sorting 해줬다. 이제 elsie의 카드를 돌면서 bessie 보다 큰 카드를 가졌으면 point를 늘려주었다. 

중간에 bessie의 card index가 round 를 넘어가면 바로 끝내 주었다. (out of bounds 예외처리)

💻 코드

//AC
//BOJ 11968 High Card Wins
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> card;
vector<int> elsie;
int visit[101010];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int round, num;
    cin >> round;
    for(int i=0; i<round; i++) {
        cin >> num;
        card.push_back(num);
        visit[num] = 1;
    }
    sort(card.begin(), card.end()); // bessie 카드 sorting
    for(int i=1; i<=round*2; i++) {
        if(!visit[i]){
            elsie.push_back(i);  // bessie가 가지지 못한 카드를 elsie 에게 넣어준다.
        }
    }
    sort(elsie.begin(), elsie.end());  // elsie 카드 sorting
    int index = 0, point = 0;
    for(int elsie_card : elsie) {
        if (index >= round)  break;  // index 예외처리
        if (elsie_card > card[index]) {
            index++;
            point++;  // elsie 카드가 bessie 카드보다 크다면 bessie index를 늘려주고 elsie의 point를 1점 늘려준다.
        }
           
    } 
    cout << point;
    return 0;
}