[프로그래머스/C++] 숫자 게임

 

문제

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

 

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 한다.

 

이때 규칙은 아래와 같다.

1. 모든 사원이 무작위로 자연수를 하나씩 부여받는다.
2. 각 사원은 딱 한 번씩 경기를 합니다.
3. 각 경기당 A팀, B팀에서 한 사원씩 나와 서로의 수를 공개하고, 그때 숫자가 큰 쪽이 승리하며 승리한 사원이 속한 팀은 승점을 1점 얻게 된다.
4. 만약 숫자가 같다면 누구도 승점을 얻지 않습니다.

이 때, 전체 사원이 숫자를 부여받았으며, A팀은 자신들의 출전 순서를 전부 공개했다. B팀이 A팀의 출전순서를 보고 최대 승점을 얻는다면 얼마를 얻게 되는지 결과를 return하면 되는 문제다.

 

 

입출력 예

 

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

 

 

제한

 

• A와 B의 길이는 같습니다.
• A와 B의 길이는 1 이상 100,000 이하입니다.
• A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.

 

풀이

 

A팀의 순서를 B팀에서 알고 있기 때문에 B팀에서 A팀을 최대한 많은 횟수로 이기면 된다.

 

그렇기 때문에 정렬을 해 그리디적으로 A팀과 B팀의 수를 비교하면 Nlog(N)으로 풀 수 있는 문제다. 

 

B가 정렬된 A팀의 수들을 보고 자신의 팀에서 사용하지 않은 수 중 가장 작은 수로 A를 이기면 되기 때문이다.

 

그림을 보면 더 쉽게 이해할 수 있다.

 

그림에서 B의 2로 A팀의 1을 이길 수 있다. 이후 A팀의 3을 이기기 위해서는 B팀에서 6이 필요하다.

 

이 때, B팀의 남은 2는 더 이상 사용하지 않는데, 왜냐하면 정렬을 했기 때문에 A팀에서 3보다 더 작은 수는 뒤에 없기 때문이다.

 

이런식으로 순차적으로 문제를 풀면 쉽게 풀 수 있다.

 

[풀이 요약]

1. A팀과 B팀의 숫자를 정렬한다.
2. A팀의 수를 이길 수 있는 B팀의 숫자 중 가장 작은 것을 찾는다. (이미 정렬을 했기 때문에 index를 1씩 늘려가면서 비교하면 됨)
3. A팀이나 B팀의 모든 index를 비교하면 그 때 B팀이 승리한 횟수를 return한다.

 

 

Code

 

 

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

 

코드는 큰 수 부터 비교했지만 똑같다.

---

 

[후기]

 

처음에 문제를 어렵게 생각할 뻔 했지만, 다시 보니 정렬만 해도 쉽게 풀 수 있는 문제여서 빨리 풀 수 있었다.

 

설명은 작은 수를 비교한다고 했지만, 문제를 풀 때는 큰 수를 이기도록 코드를 짰었네;

 

프로그래머스