문제 개요
세 개의 숫자 x, y, z가 주어진 상황을 가정해 봅시다. 어떤 리뷰 사이트에서 x명은 추천(upvote)을 할 예정이고, y명은 비추천(downvote)을 할 예정입니다. 그리고 추가로 z명이 투표를 하긴 하지만, 이들이 추천을 할지 비추천을 할지는 알 수 없습니다. 각 사람은 최대 한 번만 투표할 수 있습니다.
투표 결과는 다음과 같이 결정됩니다.
- 추천 수가 비추천 수보다 많으면 '+'
- 비추천 수가 더 많으면 '-'
- 두 수가 같으면 '0'
그런데 z명의 투표 성향을 알 수 없기 때문에 결과가 불확실할 수 있습니다. 즉, z명이 어떻게 투표하느냐에 따라 서로 다른 결과가 나올 가능성이 둘 이상 존재한다면, 결과는 '?'로 표시됩니다. 우리가 해야 할 일은 확정된 결과를 구하거나, 결과가 불확실한 경우 '?'를 출력하는 것입니다.
예시
예를 들어 x = 2, y = 0, z = 2라고 입력이 주어졌다고 해봅시다. 현재 추천이 2표 있으므로, 나머지 두 명이 모두 비추천하면 결과는 '0'이 되고, 반대로 두 명이 모두 추천하면 결과는 '+'가 됩니다. 즉, 가능한 결과가 여러 개이므로 정답은 불확실하며, 출력은 '?'가 됩니다.
해결 접근 방법
이 문제는 단순한 조건 분기만으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- x가 y + z보다 크다면, 미확정 투표자 z명이 전부 비추천해도 추천이 더 많으므로 결과는 확정적으로 '+'입니다.
- 반대로 x + z가 y보다 작다면, z명이 전부 추천해도 비추천이 더 많으므로 결과는 확정적으로 '-'입니다.
- z가 0이라면 미확정 투표가 없으므로, 위 두 조건에 해당하지 않는 한 추천과 비추천 수가 같아 결과는 '0'입니다.
- 그 외의 경우에는 z명의 선택에 따라 결과가 달라질 수 있으므로 '?'를 반환합니다.
이를 의사 코드로 표현하면 다음과 같습니다.
if x > y + z, then:
return "+"
otherwise when x + z < y, then:
return "-"
otherwise when not z is non-zero, then:
return "0"
Otherwise
return "?"
C++ 구현 예제
위 로직을 C++ 코드로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
string solve(int x, int y, int z){
if (x > y + z)
return "+";
else if (x + z < y)
return "-";
else if (!z)
return "0";
else
return "?";
}
int main(){
int x = 2;
int y = 0;
int z = 2;
cout << solve(x, y, z) << endl;
}
입력
2, 0, 2
출력
?
코드 설명 및 시간 복잡도
solve 함수는 네 개의 조건문으로 구성되어 있습니다. 첫 번째 조건(x > y + z)은 비추천이 최악의 경우에도 추천을 앞지르지 못하는 상황을, 두 번째 조건(x + z < y)은 추천이 최선의 경우에도 비추천을 따라잡지 못하는 상황을 검사합니다. 세 번째 조건(!z)은 미확정 투표자가 없는 경우를 처리하고, 마지막 else 분기가 바로 결과가 불확실한 '?' 케이스입니다.
이 알고리즘은 단순 비교 연산만 수행하므로 시간 복잡도는 O(1)이며, 추가 메모리 사용 없이 상수 공간에서 동작합니다. 입력 값의 범위와 무관하게 항상 일정한 시간에 결과를 계산할 수 있다는 점이 이 풀이의 장점입니다.