[Swift] 프로그래머스 연습 문제(Level 2) : 예상 대진표

실제 코딩테스트의 문제를 통하여 알고리즘 분석과 코딩 능력을 향상시킵니다.

 

 

#. 구독 대상

• 기본 알고리즘을 코딩 테스트 문제를 통하여 학습하고 싶으신 분
• 취업 및 이직을 준비하고 계신 개발자
• Swift를 통하여 코딩 테스트 문제를 살펴보고 이해를 하고 싶으신 분
• 코딩 테스트에 대한 거부감을 없애기 위하여 기초부터 하나씩 공부해보고 싶으신 분
• 기타 알고리즘과 문제 해결 능력에 대해서 관심이 있는 모든 개발자분

참고 사항

본 코딩 테스트 문제에 대한 설명 및 해결 방안은 최적의 답이 아닐 수 있습니다.

본 강의에서 지향하는 목표는 바로 특정 문제에 대한 최적의 해결 방법을 찾기보다는 특정한 문제에 대해서 충분히 이해할 수 있고 다양한 방법을 통하여 해결하는 방법을 찾고 향상시키는데 그 목적이 있습니다.

좀 더 좋은 알고리즘 및 코드가 있으시다면 언제든지 본 게시물의 댓글을 통해서 제시해주시면 감사하겠습니다.

 

 

 

---

 

 

 

코딩 테스트 문제

 

먼저 오늘 살펴볼 문제에 대해서 먼저 살펴보겠습니다.

 

https://programmers.co.kr/learn/courses/30/lessons/12985?language=swift 

코딩테스트 연습 - 예상 대진표

 

 

 

---

 

 

 

문제 설명

 

△△ 게임대회가 개최되었습니다. 이 대회는 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 입니다.)

 

 

 

 

 

---

 

 

 

 

입출력 예

N	A	B	answer
8	4	7	3

 

 

 

 

---

 

 

문제 분석

 

오늘 문제는 조금 독특한 문제로서 토너먼트 게임에서 두 명의 참가자가 서로 만날 최소한의 라운드를 구하는 문제입니다.

기본 조건은 두 명씩 한 조로 토너먼트 상대로 상대를 하며 무조건 이긴다는 전제 조건하에 가장 빠르게 만나는 라운드를 리턴하면 됩니다.

 

 

 

 

 

---

 

 

 

알고리즘

 

그렇다면 본 문제를 해결하기 위한 알고리즘을 하나씩 살펴보면 아래와 같습니다.

 

 

기본 알고리즘 공식

 

• 2명이 한 조로 경기를 하며 배정된 번호 순으로 무조건 조가 편성이 됩니다.
• 따라서 1번이든 2번이든 1조로 편성되며 3번 이든 4번 이든 2조, 이런식으로 생각하면 내 번호가 짝수일 경우는 그냥 2로 나누면 내가 속한 조가 되며 홀수일 경우 +1을 하고 2로 나누면 내가 속한 조가 됨을 알 수 있습니다.
• 또한 다음 라운드에는 이전 라운드 참가자보다 절반이 줄어든 조건하에 위의 공식으로 조를 평가할 수 있습니다.
• 만약 두 선수가 있다면 최종 같은 조에 속하게 될 경우 만나게 된 경우이니 해당 라운드 수를 최종 반환하면 됩니다.

 

 

코딩 절차

 

• 현재 라운드 및 2명의 참가자 조를 계산할 변수를 선언합니다.
• 2명의 참가자 순번에 따라 속할 조를 구분합니다.(짝수 : 2로 나눔, 홀수 : 번호 + 1 / 2)
• 라운드 카운트를 증가합니다.
• 2명의 현재 조 번호를 비교하여 같으면 반복문을 탈출합니다.
• 다음 라운드를 위해 처음과 똑같이 다시 연산하여 현재 조를 다시 구합니다.
• 최종 두 선수의 조 번호가 같아지면 최종 라운드 값을 반환합니다.

 

 

 

 

---

 

 

 

코드 설명

 

그렇다면 위의 알고리즘에 대해서 하나씩 살펴보면서 코드로 작성을 해보도록 하겠습니다.

 

 

• 현재 라운드 및 2명의 참가자 조를 계산할 변수를 선언합니다.

var A = a
var B = b
var round = 0

 

• 2명의 참가자 순번에 따라 속할 조를 구분합니다.(짝수 : 2로 나눔, 홀수 : 번호 + 1 / 2)

while true { 
    if A % 2 == 0 {
        A /= 2
    } else {
        A = (A + 1) / 2
    }

    if B % 2 == 0 {
        B /= 2
    } else {
        B = (B + 1) / 2
    }
}

 

 

• 라운드 카운트를 증가합니다.

round += 1

 

 

• 2명의 현재 조 번호를 비교하여 같으면 반복문을 탈출합니다.

while true {
    

    if (A == B) {
        break
    }
}

 

 

• 다음 라운드를 위해 처음과 똑같이 다시 연산하여 현재 조를 다시 구합니다.
• 최종 두 선수의 조 번호가 같아지면 최종 라운드 값을 반환합니다.

 

 

while true {
        if A % 2 == 0 {
            A /= 2
        } else {
            A = (A + 1) / 2
        }
        
        if B % 2 == 0 {
            B /= 2
        } else {
            B = (B + 1) / 2
        }
        
        round += 1
        
        if (A == B) {
            break
        }
    }
    
    return round
}

 

 

 

 

 

 

 

 

위의 코드들을 모두 조합하여 최종 코드를 완성하면 아래와 같습니다.

 

 

최종 코드

import Foundation

func solution(_ n:Int, _ a:Int, _ b:Int) -> Int
{    
    var A = a
    var B = b
    var round = 0
    
    while true {
        if A % 2 == 0 {
            A /= 2
        } else {
            A = (A + 1) / 2
        }
        
        if B % 2 == 0 {
            B /= 2
        } else {
            B = (B + 1) / 2
        }
        
        round += 1
        
        if (A == B) {
            break
        }
    }
    
    return round
}

 

 

 

 

 

---

 

 

 

이상으로 오늘 제시한 문제에 대해서 분석 및 코드를 작성해 보았습니다.

 

감사합니다.

 

 

 

 

---

[참고 자료(References)]

 

[1] 프로그래머스 - 예상 대진표 : https://programmers.co.kr/learn/courses/30/lessons/12985?language=swift