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

예상 대진표

문제 링크

예상 대진표

분석

부전승은 없습니다.

A와 B가 만나게 되는 라운드 회차를 반환해야합니다.

참가자 번호가 짝수라면 다음 라운드에서 절반 값의 번호를 받게됩니다.
참가자 번호가 홀수라면 다음 라운드에서 $+ 1$한 후 절반 값의 번호를 받게됩니다.

풀이

int solution(int n, int a, int b)
{
    int answer = 0;
    
    // 두 참가자가 만나는 라운드를 구할 때까지 반복
    while (true)
    {
        // 두 참가자가 만나는 경우 반복문 탈출
        if (a == b)
        {
            break;
        }
        
        // 다음 라운드에 대한 번호
        a = (a % 2 == 0) ? a / 2 : (a + 1) / 2;
        b = (b % 2 == 0) ? b / 2 : (b + 1) / 2;
        
        // 라운드 증가
        ++answer;
    }

    return answer;
}

성능 요약

시간 복잡도는 $O(log n)$입니다.

• a와 b는 절반씩 줄어드므로 반복문 $O(log n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 3.68MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.15MB)
테스트 4 〉 통과 (0.01ms, 4.14MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 4.16MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.17MB)
테스트 9 〉 통과 (0.01ms, 3.67MB)
테스트 10 〉 통과 (0.01ms, 4.2MB)
테스트 11 〉 통과 (0.01ms, 4.13MB)
테스트 12 〉 통과 (0.01ms, 4.2MB)
테스트 13 〉 통과 (0.01ms, 4.16MB)
테스트 14 〉 통과 (0.01ms, 4.21MB)
테스트 15 〉 통과 (0.01ms, 4.21MB)
테스트 16 〉 통과 (0.01ms, 3.66MB)
테스트 17 〉 통과 (0.01ms, 4.21MB)
테스트 18 〉 통과 (0.01ms, 4.19MB)
테스트 19 〉 통과 (0.01ms, 3.75MB)
테스트 20 〉 통과 (0.01ms, 3.67MB)
테스트 21 〉 통과 (0.01ms, 4.14MB)
테스트 22 〉 통과 (0.01ms, 4.21MB)
테스트 23 〉 통과 (0.01ms, 4.2MB)
테스트 24 〉 통과 (0.01ms, 3.68MB)
테스트 25 〉 통과 (0.01ms, 4.14MB)
테스트 26 〉 통과 (0.01ms, 4.14MB)
테스트 27 〉 통과 (0.01ms, 4.21MB)
테스트 28 〉 통과 (0.01ms, 3.66MB)
테스트 29 〉 통과 (0.01ms, 3.67MB)
테스트 30 〉 통과 (0.01ms, 4.21MB)
테스트 31 〉 통과 (0.01ms, 3.71MB)
테스트 32 〉 통과 (0.01ms, 4.14MB)
테스트 33 〉 통과 (0.01ms, 4.21MB)
테스트 34 〉 통과 (0.01ms, 4.17MB)