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

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

프로그래머스

풀이 :

1. N의 제한사항이 2의 20승 이하인 자연수였기 때문에 일반적인 배열을 사용할 경우 시간초과가 날 것 같다고 생각

2. deque를 사용하여 참가자를 2명씩 비교하는 함수(win)를 만들기로 함

3. 4가지의 조건문을 만들어서 해결

첫번째 조건문 : 만약 두 참가자 모두 chk_list에 있는 참가자라면 정답이므로 chk = True를 통해 반복문 탈출

두번째 조건문 : 비교하는 첫번째 참가자가 chk_list에 있는 참가자라면 이 참가자가 이겨야하므로 기존 번호 / 2번호를 부여 후 queue에 다시 추가 후 첫번째, 두번째 참가자 queue에서 제거

세번째 조건문 :  비교하는 두번째 참가자가 chk_list에 있는 참가자라면 이 참가자가 이겨야하므로 기존 번호 / 2번호를 부여 후 queue에 다시 추가 후 첫번째, 두번째 참가자 queue에서 제거

네번째 조건문 : 위 3가지 조건에 해당하지 않을경우 일반적인 참가자이므로 첫번째 참가자가 이기는 것으로 하여 두번째 조건문과 동일하게 진행

 

코드 :

from collections import deque
def solution(n,a,b):
    answer = 0
    queue = deque()
    for i in range(n):
        queue.append([i+1,i//2+1])

    chk_list = [a,b]
    def win():
        chk = False
        if queue[0][0] in chk_list and queue[1][0] in chk_list:
            chk = True
        elif queue[0][0] in chk_list:
            queue[0][1] = (queue[0][1]-1) // 2 + 1
            queue.append([queue[0][0],queue[0][1]])
            queue.popleft()
            queue.popleft()
        elif queue[1][0] in chk_list:
            queue[1][1] = (queue[1][1]-1) // 2 + 1
            queue.append([queue[1][0],queue[1][1]])
            queue.popleft()
            queue.popleft()
        else:
            queue[0][1] = (queue[0][1]-1) // 2 + 1
            queue.append([queue[0][0],queue[0][1]])
            queue.popleft()
            queue.popleft()
        return chk

    count = 0
    while True:
        chk2 = False
        count += 1
        for j in range(n//2):
            chk3 = win()
            if chk3 == True:
                answer = count
                chk2 = True
                break
        sorted(queue,key=lambda x : x[1])
        n = n//2
        if chk2 == True:
            break
    return answer