예상 대진표

LEEHAKJIN-VV·2022년 6월 10일
0

프로그래머스

목록 보기
21/37

출처: 프로그래머스 코딩 테스트 연습

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 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 : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
  • A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

입출력 예

NABresult
8473

입출력 예 설명

입출력 예 #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 gameCount = 1 // 게임 횟수
    var playerCount: Int = n // 게임에 참가하는 참가자의 수를 의미
    var aNumber: Int = a // A 참가자 번호
    var bNumber: Int = b // B 참가자 번호
    
    while playerCount > 1 { // teamC
        // 같은 그룹이면 게임 바로 종료
        if checkSameGroup(aNumber,bNumber,playerCount) {
            break
        }
        aNumber = (aNumber%2 == 0) ? aNumber/2 : aNumber/2 + 1 // 번호가 짝수이면 다음 라운드 번호는 /2
        bNumber = (bNumber%2 == 0) ? bNumber/2 : bNumber/2 + 1 // 번호가 홀수이면 다음 라운ㄷ 번호는 /2 + 1
        playerCount /= 2 // 게임의 참가자 수
        gameCount += 1 // 게임 횟수
    }
    return gameCount
}

// true -> 같은 그룹, false -> 다른 그룹
func checkSameGroup(_ a: Int, _ b: Int, _ teamCount: Int) -> Bool{
    // n == 8일때 [1:1,2:1] [3:2,4:2] [5:3,6:3] [7:4,8:4]
    var groupNumber = 1 // 그룹 넘버
    var index = 1
    var teamDict: [Int:Int] = [:] // value가 같으면 같은 그룹
    
    for i in 1...teamCount { // teamGroup을 만듬
        teamDict[i] = groupNumber
        if index%2 == 0 { // 1개 그룹의 참가자는 무조건 2명
            groupNumber += 1
        }
        index += 1
    }
 
    guard let aGroup = teamDict[a], let bGroup = teamDict[b] else { // 딕셔너리의 key가 같다 -> 같은 그룹
        print("error")
        return false
    }
    return (aGroup == bGroup) ? true : false
}

코드 설명

게임에 참가하는 참가자의 수는 2의 지수승(2^n)이다. 여기에선 1가지 규칙이 존재한다. 한사람 당 게임의 최대 진행 횟수는 n 번이다(8명 참가 -> 최대 3번, 32명 참가 -> 최대 5번). 문제 풀이는 a와b가 몇 번째 라운드에서 만나는지 알아야 하므로 a와 b가 같은 그룹에 속하면 해당 라운드에서 만난다고 간주한다. 여기서 그룹이란 (1번 2번, 3번과 4번..)등을 의미한다. 8명이 참가하면 처음에는 4개의 그룹, 두 번째 경기에서는 2개의 그룹으로 줄어든다. 즉 1번의 경기를 치를 때마다 절반씩 줄어든다.

그러면 코드를 세부적으로 살펴본다.

게임을 진행하는 루프다.

while playerCount > 1 { // teamC
        // 같은 그룹이면 게임 바로 종료
        if checkSameGroup(aNumber,bNumber,playerCount) {
            break
        }
        aNumber = (aNumber%2 == 0) ? aNumber/2 : aNumber/2 + 1 // 번호가 짝수이면 다음 라운드 번호는 /2
        bNumber = (bNumber%2 == 0) ? bNumber/2 : bNumber/2 + 1 // 번호가 홀수이면 다음 라운ㄷ 번호는 /2 + 1
        playerCount /= 2 // 게임의 참가자 수
        gameCount += 1 // 게임 횟수
    }

게임을 진행하는 플레이어의 수가 1명이 남을 때까지 루프를 진행한다. 루프의 조건을 게임의 진행 횟수로 변경하여도 무방하다. 루프를 진행하는 동안 a와b가 같은 그룹에 속하면 해당 라운드에서 종료되고 몇 번째 만에 만났는지 알 수 있다. checkSameGroup 함수를 통해 같은 그룹에 속하는지 확인한다.

a참가자와 b참가자는 서로 만날 때까지 게임에서 계속 이긴다. 그래서 다음에 부여받는 번호를 알아야 한다. 다음에 부여받는 번호는 현재 번호(number)이 짝수인 경우 (number/2), 홀수인 경우 (number/2+1) 번호를 부여 받는다.

다음으로 같은 그룹인지 확인하는 함수를 살펴본다.

// true -> 같은 그룹, false -> 다른 그룹
func checkSameGroup(_ a: Int, _ b: Int, _ teamCount: Int) -> Bool{
    // n == 8일때 [1:1,2:1] [3:2,4:2] [5:3,6:3] [7:4,8:4]
    var groupNumber = 1 // 그룹 넘버
    var index = 1
    var teamDict: [Int:Int] = [:] // value가 같으면 같은 그룹
    
    for i in 1...teamCount { // teamGroup을 만듬
        teamDict[i] = groupNumber
        if index%2 == 0 { // 1개 그룹의 참가자는 무조건 2명
            groupNumber += 1
        }
        index += 1
    }
 
    guard let aGroup = teamDict[a], let bGroup = teamDict[b] else { // 딕셔너리의 key가 같다 -> 같은 그룹
        print("error")
        return false
    }
    return (aGroup == bGroup) ? true : false
}

우선 앞에서 설명했듯이 8명의 참가자가 게임을 진행할 경우 4개의 그룹 -> 2개의 그룹 -> 1개의 그룹 순으로 그룹의 수는 절반씩 줄어든다. 이를 이용하여 게임을 진행할 때마다 현재 존재하는 그룹을 업데이트한다. 우선 그룹의 정보를 담는 딕셔너리 teamDict를 선언한다. key는 참가자 번호, value는 그룹의 번호이다. 같은 value를 가지는 참가자는 같은 그룹에 속한다. 만약 a참가자나 b참가자가 어떤 그룹에도 속하지 않을 시 이는 어떠한 논리적 에러 또는 입력 에러라고 판단한다. 마지막으로 그룹이 같을 시 true를 반환하고 같지 않을 시 false를 반환한다.

다른 사람의 풀이

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
}

풀이를 보면 되게 간단하게 푼 것을 확인할 수 있다. 우선 a와b참가자의 다음 번호를 구하는 식에서 차이가 있다. 제일 중요한 점은 글쓴이는 해당 라운드에서 같은 그룹에서 만나는 순간 루프는 종료되어야 한다는 생각을 고정시키고 코드를 구현하였는 데 위 코드는 같은 그룹에서 만났다면 두 참가자의 다음 번호는 같아진다는 원리를 이용하였다. 조금의 생각 차이가 코드의 훨씬 짧게 만드는 것을 확인할 수 있는 문제였다.

0개의 댓글