백준 2164 파이썬 풀이

안녕하세요 호박감자입니다.

오늘 풀어볼 문제는 백준의 2164번 카드 2 문제입니다.

이 문제에서는 보통 많은 분들이 큐를 사용해서 푸는 것 같습니다.

저는 큐를 사용해서 풀지 않았는데요, 제가 찾은 규칙을 사용한 코드와, 다른 사람의 코드 중에서 정말 좋았던 코드를 리뷰해보겠습니다.

---

1. 내코드

코드를 짜면서 생각한 규칙을 먼저 설명하겠습니다.

카드 덱의 맨 윗장, 즉, 1번 카드를 버리게 됩니다. 그리고 2번 카드는 맨 아래로 가게됩니다. 3번 카드는 버려집니다. 4번 카드는 맨 아래로 가게됩니다.

이런식으로 반복이 된다면, 만일 10장의 카드가 있었다고 할 때, 생존할 카드는 다음과 같을 것입니다.

1 2 3 4 5 6 7 8 9 10

그리고 2번 부터 차례로 밑으로 이동되었으니, 9번 카드를 버리고 10번 카드를 옮기면 카드 배치는 위 순서 그대로일 것입니다.

그리고 그 다음 카드를 또 버리겠죠. 10번 카드를 옮겼으니 2번 카드가 버려질 차례입니다.

2 4 6 8 10

자아, 이번 차례의 카드들도 역시 첫번째 카드부터 버려지기 시작했습니다. 그렇다면 다음 차례의 카드들도 첫번째 카드를 버리게 될까요? 위에 카드들 중 남아있는 카드 4와 8에서 버려지게 될 카드는 8번입니다.

무언가 바꼈습니다. 알아차리셨나요? 분명 첫번째 부터 버려져서 4가 버려져야 할 것 같은데, 8번이 버려지게 됩니다.

왜그런가요? 바로 10번 카드가 버려졌기 때문에 그 다음인 4번 카드는 밑으로 옮겨지고, 8번 카드가 버려지게 되는 것입니다.

저는 이 규칙을 사용해서 코드를 짜봤습니다. 카드 리스트의 개수가 짝수개라면 그 다음 리스트의 규칙은 바뀌지 않지만, 위의 2 4 6 8 10 카드 일때의 경우처럼 카드 리스트의 개수가 홀수개라면 그 다음 리스트의 규칙은 바뀝니다.

규칙은 두가지, 첫번째 카드부터 버려지느냐, 두번째 카드부터 버려지느냐 입니다.

---

알고리즘을 설명했으니, 코드를 보여드리겠습니다.

def jump_num(n_list, flag, r):
    if flag is True:
        if r == 0:
            r = 1
        else:
            r = 0
    new_list = []
    for i in range(r, len(n_list), 2):
        new_list.append(n_list[i])
    return new_list, r


N = int(input())

num_list = range(1, N + 1)
rule = 1
now_change_flag = False

while len(num_list) > 1:
    length = len(num_list)

    if length % 2 == 0:  # 짝수, 변하지 않음.
        have_to_change_next_time = False
    else:  # 홀수, 변함.
        have_to_change_next_time = True
    num_list, rule = jump_num(num_list, now_change_flag, rule)
    now_change_flag = have_to_change_next_time

print(num_list[0])

전체 코드입니다.

이 코드에서는 규칙을 바꾸기 위해 두 개의 flag를 사용합니다.

현재 플래그 - now_change_flag, 다음 차례 플래그 - have_to_change_next_time

만약에 리스트의 길이가 짝수라면 have_to_change_next_time가 False, 홀수라면 True가 되어서 다음 차례 규칙을 바꿀지 말지 결정합니다.

jump_num() 함수에서는 숫자 리스트 - n_list, 플래그 - flag, 규칙 - r을 입력받습니다.

r은 0 또는 1로, 첫번째부터 버린다면 1, 두번째부터 버린다면 0이 저장되어 이 값이 for 문의 시작값이 됩니다. for 문은 시작값으로 부터 2의 간격으로 늘어나며, 해당하는 인덱스의 카드들을 보존합니다. (해당 인덱스 카드를 버리는게 아니라 보존하는 것입니다. 그럼 나머지는 버려지겠죠?)

참고로 규칙(r)을 굳이 메인 흐름에서 jump_num() 함수로 넘겨주는 이유는 제가 아직 파이썬에서 전역 변수를 쓰는게 서툴기 때문입니다.

어쨌든 이런식으로 해서 마지막으로 남는 카드를 출력하게됩니다.

---

이 코드는 큐를 사용한 코드보다 더 빠르게 동작합니다. 그런데 코드를 살펴보던 중 다른 사람의 더욱 좋은 알고리즘이 있어 소개하려고 합니다.

---

2. 다른 알고리즘

먼저 코드를 공개하겠습니다. 제 코드가 아니라 다른 사람의 코드인데, 아이디를 적어야 할지 말아야 할지, 저작권이 있는건지 잘 모르겠습니다. 문제가 될시 수정하겠습니다.

input = int(input())
square = 2
while True:
	if input == 1 or input == 2:
    	print(input)
        break
    square *= 2
    if square >= input:
    	print((input - (square // 2)) * 2)
        break

와우.. 굉장히 깔끔하고 간결하죠? 처음 보고 깜짝 놀랐습니다.

큐나 뭐 다른 규칙을 사용하지 않고 수식 하나만으로 계산할 수 있도록 코딩했다는 것이 대단한 것 같습니다.

이 코드를 보고 어떤 규칙이 있어서 이 수식이 가능한 것인지 한번 찾아봤습니다.

카드의 개수에 따른 마지막 생존 카드

제가 짠 코드를 돌려가며 3에서 10까지 카드의 개수에 따라 어떤 카드가 남게 되는지 살펴보았습니다.

저 숫자의 규칙이 보이시나요? 2 4 다음엔 2 4 6 8, 그 다음에 또 2 4 ... 이런식으로 늘어나고 있습니다.

이 규칙을 사용해 수식을 만들 수 있을 것으로 보입니다.

---

처음에 규칙을 찾으려 할 때, 잘못 접근해서 돌아가느라고 저 규칙을 못본게 아쉬운 것 같습니다.

아무튼 2164번의 리뷰를 여기까지 하겠습니다.