문제 설명
n개의 팀이 참가하는 대회를 생각해 봅시다. 경기를 최대한 흥미롭게 만들기 위해 이 대회에서는 항상 상대적으로 강한 팀과 상대적으로 약한 팀을 서로 맞대결시킵니다. 예컨대 1위 팀과 n위 팀을 붙이는 방식입니다. 우리가 해야 할 일은 이러한 전략에 따라 완성되는 최종 대진표를 문자열 형태로 구하는 것입니다.
각 팀은 1부터 n까지의 양의 정수로 주어지며, 이 값은 초기 순위를 의미합니다. 즉, 1위가 가장 강한 팀이고 n위가 가장 약한 팀입니다. 대진표는 괄호 '(' , ')' 로 매치를 묶고 쉼표 ',' 로 구분하여 표현합니다. 매 라운드마다 짝을 지을 때에는 반드시 '강한 팀 ↔ 약한 팀' 매칭 전략을 따라야 합니다.
예를 들어 입력이 4라면 출력은 ((1,4),(2,3))이 됩니다.
접근 방법
재귀 함수를 이용해 배열의 양쪽 끝에서부터 차례로 팀을 묶어 나가면 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- create() 함수 정의: low, high, 배열 v2, 배열 v1을 매개변수로 받습니다.
- low >= high이면 그대로 종료(return)합니다.
- "(" + v1[low] + "," + v1[high] + ")" 형태의 문자열을 v2의 끝에 삽입합니다.
- create(low + 1, high - 1, v2, v1)을 재귀 호출하여 안쪽에 남은 팀들을 계속 짝지어 줍니다.
메인 메서드에서는 다음 순서로 처리합니다.
- 배열 v1과 v2를 선언합니다.
- i := 1부터 n까지 반복하면서 i를 문자열로 변환해 v1의 끝에 추가합니다.
- v1의 크기가 1보다 큰 동안 다음을 반복합니다.
- create(0, v1.size() - 1, v2, v1) 호출
- v1 := v2로 교체
- v2 배열 비우기(clear)
- 반복이 끝나면 v1의 마지막 원소, 즉 최종 대진표 문자열을 반환합니다.
구현 예제
아래 C++ 코드를 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void create(int low, int high, vector<string>& v2, vector<string>& v1){
if (low >= high)
return;
v2.push_back("(" + v1[low] + "," + v1[high] + ")");
create(low + 1, high - 1, v2, v1);
}
string findContestMatch(int n) {
vector<string> v1, v2;
for (int i = 1; i <= n; i++) {
v1.push_back(to_string(i));
}
while (v1.size() > 1) {
create(0, v1.size() - 1, v2, v1);
v1 = v2;
v2.clear();
}
return v1.back();
}
};
main(){
Solution ob;
cout << (ob.findContestMatch(4));
}
실행 결과
입력
4
출력
((1,4),(2,3))
동작 원리와 복잡도
n = 4일 때의 동작을 추적해 보면, 첫 번째 라운드에서 (1,4)와 (2,3) 두 개의 매치가 만들어지고, 두 번째 라운드에서 이 두 결과가 다시 하나의 매치로 묶이면서 ((1,4),(2,3))이라는 최종 문자열이 완성됩니다. 매 라운드마다 매치의 개수가 절반으로 줄어들기 때문에 총 라운드 수는 log₂n이며, 전체 시간 복잡도는 대략 O(n log n)입니다. 재귀 호출이 양쪽 끝에서 중앙으로 좁혀져 나가는 구조이기 때문에 코드가 간결하면서도 직관적으로 대진 규칙을 표현할 수 있다는 점이 이 풀이의 장점입니다.