두 명의 플레이어가 참여하는 n라운드 게임이 있다고 가정해 보겠습니다. 각 라운드의 점수는 'scores' 배열에 담겨 있으며, 각 요소는 {P1 점수, P2 점수} 형태로 구성됩니다. 매 라운드마다 더 높은 점수를 기록한 플레이어가 해당 라운드에서 승리하고, 더 많은 라운드를 이긴 플레이어가 최종적으로 게임에서 승리합니다. 만약 두 플레이어가 이긴 라운드 수가 같다면 무승부(Draw)로 처리됩니다.
따라서 우리에게 주어진 과제는 라운드별 점수 데이터를 바탕으로 최종적으로 누가 게임에서 승리했는지 판별하는 것입니다.
예를 들어 입력이 다음과 같다고 해봅시다.
- n = 4
- scores = {{4, 3}, {3, 2}, {5, 6}, {2, 5}}
이 경우 P1은 1·2라운드에서, P2는 3·4라운드에서 각각 승리하므로 출력 결과는 Draw(무승부)가 됩니다.
풀이 접근 방법
이 문제는 각 라운드의 점수 차이를 누적하는 방식으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- P1이 라운드에서 이기면 +1을 더합니다.
- P2가 라운드에서 이기면 -1을 더합니다.
- 무승부 라운드라면 0을 더합니다.
모든 라운드를 순회한 후 누적값(res)의 부호에 따라 최종 승자를 결정합니다. 양수면 P1 승리, 음수면 P2 승리, 0이면 무승부입니다.
알고리즘 단계
res := 0
while n is non-zero, do:
a := first value of scores[n]
b := second value of scores[n]
res := res + ((if a > b, then 1, otherwise (if a < b, then -1, otherwise 0)))
n := n - 1
return (if res > 0, then "P1", otherwise (if res < 0, then "P2", otherwise "Draw"))C++ 구현 예제
아래 코드를 통해 실제 구현 과정을 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100
string solve(int n, vector<pair<int, int>> scores) {
int res = 0;
while(n--){
int a = scores[n].first;
int b = scores[n].second;
res += (a > b ? 1 : (a < b ? -1 : 0));
}
return res > 0 ? "P1" : (res < 0 ? "P2" : "Draw");
}
int main() {
int n = 4;
vector<pair<int, int>> scores = {{4, 3}, {3, 2}, {5, 6}, {2,5}};
cout<< solve(n, scores);
return 0;
}코드 설명
solve()함수는 라운드 수 n과 점수 벡터를 입력받습니다.- while 루프를 통해 각 라운드의 P1 점수(first)와 P2 점수(second)를 비교하여 삼항 연산자로 +1, -1, 0 중 하나를 누적합니다.
- 모든 라운드 처리 후 res 값의 부호에 따라 "P1", "P2", "Draw" 문자열을 반환합니다.
입력
4, {{4, 3}, {3, 2}, {5, 6}, {2, 5}}출력
Draw
복잡도 분석
모든 라운드를 한 번씩만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간 없이 단일 변수만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 라운드 수가 많아져도 효율적으로 동작하는 최적화된 솔루션입니다.