[ 프로그래머스 숫자게임 (Lv3) ] (C++)

프로그래머스의 숫자게임(Lv3) 문제이다.

 

[ 문제풀이 ]

정해진 순서대로 출전하는 A팀을 상대로 가장 높은 승점으로 승리하기 위한 B팀의 승점을 구해야 하는 문제이다.

 

#1. 승리를 위한 규칙

본인은 가장 먼저, A팀이 뽑을 숫자들과 B팀이 뽑을 숫자들이 주어지면 이를 정렬을 하였다.

문제에서 주어진 첫번째 케이스를 예시로 가지고 진행해보자.

A = [ 5 , 1 , 3 , 7 ]  ,  B = [ 2 , 2 , 6 , 8 ]

이를 오름차순으로 정렬하게 되면 다음과 같다.

A = [ 1 , 3 , 5 , 7 ]  ,  B = [ 2 , 2 , 6 , 8 ]

그리고 정렬을 하는 이유에 대해서는 밑에서 조금 더 구체적으로 알아보도록 하자.

이 상태에서 B가 A를 이기기 위해서는 어떻게 내는것이 가장 좋을까 ??

정렬해놓은 2개의 순서 그대로 비교해보면서 이기는 만큼 Count를 해주면 될까 ?? 이렇게 계산을 한다면 제대로 답이 나오지 않을 것이다. 반례가 되는 예시를 한번 보자.

 

A = [ 4 , 6 , 8 , 9 ] , B = [ 1 , 2 , 7 , 10 ]

위의 상황에서 순서대로 비교를 하게 된다면 가장 마지막 '10'이 '9'를 이기는 경우 한 가지 밖에 발생을 하지 않는다.

하지만, B가 [ 1 , 7 , 2 , 10 ] 으로 내게 된다면 '7'과 '10'이 이겨서 2번을 이길 수 있게 된다.

따라서 오름차순으로 정렬 후 순서대로 내는 것은 별로 좋은 방법 같지는 않다.

그렇다면 어떻게 비교를 해줘야 가장 많은 승점을 챙길 수 있을까 ?!

바로 다음과 같이 2가지 규칙을 이용하면 가장 많은 승점을 챙길 수 있다.

1. A의 숫자를 이길 수 있는 큰 숫자가 있다면 해당 숫자로 승점을 챙기기

2. A의 숫자를 이길 수 없다면, 상대적으로 더 작은 숫자를 내버림으로써 큰 숫자를 살려두기

 

A = [ 4 , 6 , 8 , 9 ] , B = [ 1 , 2 , 7 , 10 ]

이 상황을 위의 말에 대입해보자.

A의 가장 큰 숫자인 '9'를 B에서 가장 큰 숫자인 '10' 으로 이길 수 있다.

A의 두번째 큰 숫자인 '8'을 B에서 두번째 큰 숫자인 '7'로 이길 수 없다. 그러므로 여기서는 '7'을 굳이 낼 필요가 없다. B에서는 '7'이 상대적으로 큰 편에 속하는 숫자인데, '8'을 이길 수 없다면 차라리 훨씬 더 작은 숫자인 '1'과 '2'를 내버림으로써 '7'을 살려두는 것이 승점을 챙기는 것에 더 유리하다는 것이다.

A의 세번째 숫자인 '6'을 B에서 세번째 큰 숫자인 '2'와 비교를 하는 것이 아닌, 아직 살아있는 '7'을 냄으로써 승점을 챙긴다.

이런식으로 진행을 한다면 가장 많은 승점을 챙길 수 있다.

 

#2. 정렬의 이유

우리는 #1에서 A와 B의 숫자들을 모두 정렬한 후에 진행을 하였다. 그런데 이렇게 마음대로 정렬을 해도 될까 ??

A는 분명히 순서가 이미 정해져있다고 했는데 우리 마음대로 정렬을 해버려도 될지에 대해서 이야기를 해보자.

정답부터 이야기하자면 정렬을 하더라도 무관하다. 왜 그럴까 ?? 다시 문제에 첫번째 케이스를 가져와보자.

A = [ 5 , 1 , 3 , 7 ]  ,  B = [ 2 , 2 , 6 , 8 ]

우리는 이 상태를 다음과 같이 정렬해 주었다.

A = [ 1 , 3 , 5 , 7 ]  ,  B = [ 2 , 2 , 6 , 8 ]

그리고 이 경우에는 위에 보이는 순서대로 B가 숫자를 낸다면, 총 승점 '3'점을 딸 수가 있다.

그런데 A는 원래의 순서가 아니니까 제대로된 계산이 아닐까 ??

그럼 원래 A의 순서에 맞게 다시 고쳐보자.

A = [ 5 , 1 , 3 , 7 ] 이 있고, 이 상태에서 B가 [ 6 , 2 , 2 , 8 ] 로 낸다고 생각을 해보자.

똑같이 승점을 3점을 얻을 수가 있다. 그리고 A의 순서 또한 고정되어 있기 때문에 문제가 되질 않는다.

즉 ! A의 순서는 고정되어 있지만 B의 순서는 고정되어 있지 않고, 또한 ! 어떤 순서로 어떻게 비교를 하더라도 얻을 수 있는 최대 승점은 동일하기 때문에 정렬을 하고 계산을 하더라도 상관이 없다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> A, vector<int> B) 
{
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    int answer = 0;
    int A_Idx = A.size() - 1;
    int B_Idx = B.size() - 1;
    while (A_Idx >= 0)
    {
        int A_Score = A[A_Idx];
        int B_Score = B[B_Idx];
        if (A_Score < B_Score)
        {
            B_Idx--;
            answer++;
        }
        A_Idx--;
    }
    return answer;
}