△△ 게임대회가 개최되었습니다. 이 대회는 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 | A | B | result |
---|---|---|---|
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 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참가자의 다음 번호를 구하는 식에서 차이가 있다. 제일 중요한 점은 글쓴이는 해당 라운드에서 같은 그룹에서 만나는 순간 루프는 종료되어야 한다는 생각을 고정시키고 코드를 구현하였는 데 위 코드는 같은 그룹에서 만났다면 두 참가자의 다음 번호는 같아진다는 원리를 이용하였다. 조금의 생각 차이가 코드의 훨씬 짧게 만드는 것을 확인할 수 있는 문제였다.