[프로그래머스] 예상 대진표 (C++)

풀이

문제가 길지만 결국 요약하면 A라는 사람과 B라는 사람이 만나게 되는 대진표가 몇 번째 라운드인지만 출력하면 된다.

N명의 사람만큼 배열을 채워 넣고, 대진을 비교하면 된다.

언제까지 비교하면 될까?

8 -> 4 -> 2 -> 1

8명이라면 총 3번의 토너먼트만 돌리면 된다.

매칭 비교는

A라는 사람 혹은 B라는 사람이 다른 사람과 매칭 하게 되면 반드시 A 혹은 B가 이기고,

그 외에는 왼쪽 사람이 이긴다고 가정하면 된다. (왼쪽이나 오른쪽이나 누가 올라와도 결국 A와 B가 이기게 되므로)

 

#include <iostream>
#include <vector>
using namespace std;

int solution(int n, int a, int b)
{
    vector<int> v(n, 0);
    for(int i = 0; i < n; i++) v[i] = i + 1;
    int round = 0;
    while(n != 1) {
        vector<int> win;
        round++;
        for(int i = 1; i <= n; i+=2) {
            if((v[i-1] == a && v[i] == b) || (v[i-1] == b && v[i] == a)) return round;
            else if(v[i-1] == a || v[i-1] == b) win.push_back(v[i-1]);
            else if(v[i] == a || v[i] == b) win.push_back(v[i]);
            else win.push_back(v[i-1]);
        }
        v = win;
        n /= 2;
    }
    return -1;
}