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

 

 

 

🍄 코딩테스트

코딩테스트 문제 풀이

✍🏻 Github

문제 풀이 github 링크

 

 

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

 

제한사항

• N : 2 이상 2 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

 

입출력 예

N	A	B	answer
8	4	7	3

 

입출력 예 설명

입출력 예 #1

첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

 

 

 

문제 풀이

나의 풀이

import Foundation

func solution(_ n:Int, _ a:Int, _ b:Int) -> Int{
    var answer = 1
    var a = a, b = b, n = n
    
    while n != 1 {
        n /= 2
        a = ( a + 1 ) / 2
        b = ( b + 1 ) / 2
        
        if a == b {
            return answer
        }else {
            answer += 1
        }
    }

    return answer
}

 

처음에는 밑에서 위로 올라가면서 비교를 하는게 아닌 위에서 밑으로 내려오면서 비교를 하려고 했다.

만약 N이 8이라면 1…4 / 5…8 이런식으로 비교를해서 다른 범주에 있다면 3을 출력하고,

같은 범주에 있다면 다시 비교한다. 1..2 / 3…4 이렇게 해서 반복하여 결국 같은 범주라면 1을 출력하도록 했다.

근데 같은 범주라면 1…4 인지 5…8 인지 까지 파악을 해야하니 좀 더 복잡했던 것 같다.

 

 

그래서 다시 리프레쉬하고자 물을 먹었는데, 그 순간 “ 2로 나눈 몫?!? 이면 되겠다" 라는 생각이 번쩍 떠올랐다. 근데 문제는 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 에서 2로 나눈 몫을 구하면 0 / 1 / 1 / 2 / 2 / 3 / 3 / 4 가 되는 것이다. 12가 같은 범주에 들게끔 만들려서 1을 더하거나 빼서 1 / 1 / 2 / 2 / 3 / 3 / 4 / 4 로 만들어야 했다. 나는 더하는 쪽을 택했다.

 

 

A와 B에 각각 1을 더한 후 2로 나눈 값을 대입한다. 값이 같지 않다면 count 를 1올리고 다시 반복 결국 값이 같다면 count가 답인 것이다.

 

 

8번이면 3번만 반복하면 되고, 2의 20번이면 20번만 반복한다면 나오는 풀이였다.

그래서 시간도 정말 효율적으로 계산할 수 있고, 풀이도 간단하게 풀었던 것 같다.

 

 

 

다른 사람 풀이

import Foundation

func solution(_ n:Int, _ a:Int, _ b:Int) -> Int
{
    var answer = 0
    var nextA = a
    var nextB = b

    repeat {
        nextA = (nextA + 1) / 2
        nextB = (nextB + 1) / 2
        answer += 1
    } while nextA != nextB

    return answer
}

분명 나랑 같은 방법으로 풀었는데 코드가 어쩜이리 깔끔한지..! 코드를 깔끔하게 쓰도록 연습해야겠다.

 

 

느낀점

Lv.2 에 올라오니 많은 테크닉을 요구하면서 문제를 풀으라는 게 아니라 ‘ 너.. 이거 머리 잘써야 풀 수 있는데 풀 수 있겠어..?’ 이렇게 묻는 느낌이다. 오늘도 성공적 알고리즘 풀이..!!