프로그래머스 - 숫자 게임

요즘 백준을 낮은 난이도부터 채우면서, 블로그에 남길만한 문제가 별로 없다. 이번에 스터디를 하면서, 프로그래머스 스킬 테스트를 해보게 되었는데, 마침 이번 스터디에서 스킬 테스트에서 이 문제를 풀어보게 되었고, 이문제만 풀고 두번째는 풀지 못하면서 결국 통과하지 못했다..!! 아쉬워라

 

https://school.programmers.co.kr/learn/courses/30/lessons/12987

 

문제를 이해해 보자.

A 팀에서 어떤 순서로 숫자를 출전시킬지 알고 있는 상황에서 B 팀은 자신들의 숫자를 조합해 가장 많이 이길 수 있는 경우를 찾는 것이 목적이다. a,b 는 10만개 까지 받을 수 있고, 각 값은 1000000000 이하의 자연수이다.

 

이 문제를 해결하기 위해, 정렬한 후 for 문으로 대조해 가면서 값을 빼주고자 하였는데, 이렇게 하면 시간 초과가 날 것이 너무 당연했다. 그래서 생각한 다른 방법은, 스택에 작은 값 순서대로 넣으며 a 와 대조해 pop 시키며 진행하는 것이었다.

 

바로 코드를 보자!

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = -1;
    vector<pair<int,int>> total;
    for(int i = 0; i < A.size(); i++)
    {
        total.push_back({A[i], 0});
        total.push_back({B[i], 1});
    }
    sort(total.begin(), total.end());
    deque<int> st; 
    int cnt = 0;
    for (int i = 0; i < total.size(); i++)
    {
        if (total[i].second == 1) //B팀
        {
            if (st.size() != 0)
            {
                int comp = st.back();
                if (comp != total[i].first)
                {
                    st.pop_back();
                   cnt++; 
                }  
            }
        }
        else
        {
            st.push_front(total[i].first); //A팀
        }
    }
    answer = cnt;
    cout<<cnt;
    return answer;
}

이렇게, 우선 A와 B 를 모두 하나의 배열에 담고 작은 순으로 정렬하였다.

이제 그 AB 통합배열을 순회하면서, B의 숫자일 경우에, 디큐에 집어넣지 않을것이고, A일 경우에만 무조건 디큐에 집어넣을 것이다.

그렇다면, B인 숫자를 만났을 때 디큐에 가장 최근에 들어간 값과 대소를 비교했을 때 같거나 더 큰 경우밖에 없을 것이다.

만약 더 크다면 이기는 경우이니 카운트를 증가해주고, 디큐의 back 에 있던 값을 pop 해준다. 같을 때에는 그냥 진행해준다.

 

이게 다다!!