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

문제

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

풀이

풀이 1 - (성공)

1. 라운드를 나타내는 변수 cnt를 초기화한다. 이 변수는 A와 B가 만난 라운드 번호를 저장할 예정이다.
2. 1부터 N까지의 참가자 번호를 가진 리스트 my_list를 만든다.
3. 대회를 진행하는 동안 무한 루프를 실행한다.
4. 각 라운드마다 my_list에서 참가자들을 짝지어 겨루게 한다. 두 참가자씩 짝을 지어서 겨루므로 for문의 step을 2로 지정한다.
5. 짝지어진 두 참가자가 A와 B인지 확인한다.
6. A와 B가 만난 경우, 현재 라운드 번호(cnt)에 1을 더하여 return한다.
7. A 또는 B가 아닌 경우, 승자를 tornament 리스트에 추가한다.
8. 모든 라운드가 끝나면 cnt를 1 증가시키고, 다음 라운드의 참가자 리스트를 tornament로 업데이트한다.

def solution(n, A, B):
    cnt = 0
    my_list = [i for i in range(1, n + 1)]

    while True:
        tornament = []  
        for i in range(0, len(my_list), 2):  
            if [min(A, B), max(A, B)] == [min(my_list[i], my_list[i + 1]), max(my_list[i], my_list[i + 1])]:
                return cnt + 1  
            elif my_list[i] == A or my_list[i] == B:
                tornament.append(my_list[i])
            elif my_list[i + 1] == A or my_list[i + 1] == B:
                tornament.append(my_list[i + 1])
            else:
                tornament.append(my_list[i])  
        cnt += 1
        my_list = tornament  
    return cnt

풀이 2 - (성공)

풀이 1은 매 라운드마다 리스트(tornament)를 새로 만들고 갱신해야 한다. 이것은 불편한 메모리 사용이 있을 수 있고, N이 클수록 효율성이 떨어지게 된다.
따라서 리스트를 새로 만들지 않고 수정하는 방식으로 문제를 해결하는 것이 좋다. 주어진 A,B의 현재 라운드에서 번호를 계산하고 다음 라운드로 넘어가면서 번호르르 업데이트하는 방식을 사용하면 된다.

def solution(n,a,b):
    counts =0
    while a!=b:
        a,b= (a//2)+(a%2), (b//2)+(b%2)
        counts +=1
    return counts