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

문제

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

프로그래머스

 

개요

이전에 풀어본 듯한 유형인 것 같기도 했고, 굉장히 쉬울 거라고 느꼈다.

머릿속으로 대략적인 풀이 방법이 떠오르긴 했으나, 가장 최적의 방법을 생각해내느라 시간이 좀 걸렸다.

 

제출 코드

#include <iostream>

using namespace std;

int solution(int n, int a, int b)
{
    int cnt = 1;
    int num = 2;
    while(num != n){
        if (((a - 1) / num + 1) == ((b - 1) / num + 1)) break;
        cnt++;
        num *= 2;
    }
    return cnt;
}

생각보다 코드가 지저분해보인다.

 

생각한 방식은 다음과 같다.

예를 들어, 8명의 참가자가 있고, a = 4, b = 7이라고 해보자. 

 

(1) 2명씩 묶는다. (1라운드)

cnt = 1 인 상황이다.

처음에는 2명씩 그룹으로 묶는다. (num = 2) 즉, 1라운드라고 생각하면 된다.

그러면 8개의 그룹으로 구분될 것이다.

이 때 그룹 번호가 같다면 1라운드에서 만나게 되는 것이다. 

a의 그룹 번호는 (4 - 1) / 2 + 1 = 2 이고, b의 그룹 번호는 (7 - 1) / 2 + 1 = 4이다.

그룹 번호가 다르다는 것은 즉 1라운드에서는 만나지 않음을 의미한다.

 

(2) 4명씩 묶는다. (2라운드)

cnt = 2 인 상황이다.

그렇다면 4명씩 그룹으로 묶는다. (num *= 2 → num = 4) 즉, 2라운드라고 생각하면 된다.

그러면, 4개의 그룹으로 구분될 것이다.

이 때 그룹 번호가 같다면 결국 2라운드에서 만나게 되는 것이다.

a의 그룹 번호는 (4 - 1) / 4 + 1 = 1이고, b의 그룹 번호는 (7 - 1) / 4 + 1 = 2이다.

그룹 번호가 다르다는 것은 즉 2라운드에서는 만나지 않음을 의미한다.

 

(3) 8명씩 묶는다. (3라운드)

cnt = 3 인 상황이다.

그렇다면, 8명씩 그룹으로 묶는다. (num *= 2 →  num = 8) 즉, 3라운드라고 생각하면 된다.

num = 16이고, n = 16인 상황 → while문의 조건에 위반되어 while문을 탈출하게 된다.

즉, cnt = 3을 답으로 반환하게 된다.

이는 a와 b가 결국 3라운드에서 만나게 되는 것을 의미한다.

 

다른 정답 코드

#include <iostream>

using namespace std;

int solution(int n, int a, int b)
{
    int ans = 0;
    while(a != b){
        a = (a + 1) / 2;
        b = (b + 1) / 2;
        ans++;
    }
    return ans;
}

조금 더 간결하게 구현한 코드이다.

참가자 수에 해당하는 n을 사용할 필요가 없었다.

→ 왜냐하면 A와 B가 무조건 붙게 된다는 가정이 존재하기 때문에 n의 값을 굳이 사용할 필요가 없다.

 

a와 b를 2로 나눠가면서 a와 b의 값이 같아질 때를 구하면 된다는 방식이다.

2로 나눈다는 것은 한 라운드씩 위로 진출하는 것을 의미한다.

 

여기서 주의할 점은 a와 b를 2로 나눌 때,

a /= 2; b /= 2; 로 구현하면 안 된다는 점이다.

예를 들어, 맨 처음 7번인 사람은 다음 라운드에 4번이 되는데, 단순히 7 / 2 를 하면 3번이 된다.

그래서 a = (a + 1) / 2; b = (b + 1) / 2; 와 같이 작성해주어야 한다.

 

깨달은 점

어제부터 다시 PS를 시작했다.

거의 한 달 가까이 PS를 하지 않았던 탓인지 확실히 뇌가 굳은 느낌이 들었다.

이 문제는 정답률 68%의 문제로, 정답률이 굉장히 높은 문제임에도 불구하고 곧바로 풀어내지 못해 약간 자괴감이 들기도 했다.

Lv.2 문제들을 정답률 높은 순으로 꾸준히 풀면서 계속 감을 유지해야겠다.