[C++] Programmers Lv. 2 "예상 대진표"

🔵 문제 링크

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

프로그래머스

 

🔵 접근법

정수 x가 짝수, 홀수일 때를 나누어서 생각해 보았다.

 

x가 짝수일 경우

• 현재 참가자 번호 x가 짝수라면 x는 (x - 1, x) 쌍의 두 번째 번호이다.
• 승자는 x / 2 번을 받게 된다.
• 예) x = 2일 때, 다음 번호는 1

 

x가 홀수일 경우

• 현재 참가자 번호 x가 홀수라면 x는 (x, x + 1) 쌍의 첫 번째 번호이다.
• 승자는 (x + 1) / 2 번을 받게 된다.
• 예) x = 3일 때, 다음 번호는 2

위 두 사례를 정수 나눗셈의 특징을 이용하여 한번에 처리할 수 있다.

int a = 2;
a = (a + 1) / 2;

 

a가 홀수일 때는 당연히 답을 구할 수 있는 식이고,

a가 짝수일 때는 정수 나눗셈의 특징으로 나머지를 버리게 되어 답을 구할 수 있게 된다.

 

🔵 전체 코드

#include <iostream>

using namespace std;

// a와 b가 몇 번째 라운드에서 만나는지 -> 번호를 다시 배부받았을 때 2n과 2n + 1인지
// (1, 2), (3, 4) (5, 6) (7, 8)... 
// 1 (2) //  3 (4)

int solution(int n, int a, int b)
{
    int answer = 0;

    // 두 숫자가 같다는 것은 이미 한판 떴다는 의미
    while (a != b)
    {
        // 만약 a가 1이라면, (1 + 1) / 2 ==> 1
        // 만약 b가 4라면, (4 + 1) / 2 ==> 2
        a = (a + 1) / 2;
        b = (b + 1) / 2;

        answer++;
    }

    return answer;
}

 

🔵 시간 복잡도

참가한 인원 수를 N이라 할 때, 각 라운드마다 a, b의 값이 절반으로 줄어들고 있다.

두 참가자가 만날 때까지 걸릴 때까지 반복하는 횟수는 전체 참가자 수 N에 대해 로그 스케일로 증가한다.

따라서 시간 복잡도는 O(logN)이다.