BOJ | 파이썬 | Sliver | 2164번 카드2 (feat. 2161번 카드1)

BOJ | Sliver | 2164번 카드2

문제

https://www.acmicpc.net/problem/2164

2164번: 카드2

코드

import sys

n = int(sys.stdin.readline())
card = [_ for _ in range(1, n+1)]

while True:
    if len(card) == 1:
        break
    
    if len(card) % 2 == 0:
        del card[0:len(card):2]
    else:
        del card[0:len(card):2]
        temp = card.pop(0)
        card.append(temp)

print(card[0])

풀이

총 카드의 개수가 최대 50만개까지 주어지기 때문에 문제에서 주어진 동작에 따라 움직이도록 pop 메서드를 이용하여 문제를 풀면 시간초과로 걸리게 된다. 본 문제를 해결하기 위해 문제에서 주어진 동작은 어떤 규칙이 있는지 발견하였고, 그 방법을 구현함으로써 문제를 해결하였다.

왼) 카드가 홀수개일 때, 오) 카드가 짝수개일 때

위 이미지는 문제에서 주어진 방법에 따라 카드가 어떻게 움직이는지 표현한 것이다. 우선 카드 개수가 홀수일 떄와 짝수일 때 모두 발견할 수 있는 규칙은, 홀수 카드가 모두 사라진다는 것이다. (버리고 넘기고를 반복하니 당연한 결과이다.) 따라서 첫 번째 규칙은 주어진 카드에서 홀수 카드는 모두 버리는 것이다.

다음으로 확인할 것은 홀수 카드를 모두 버렸을 경우이다. 홀수 카드를 모두 버리고 나면 짝수 카드만 남게 되는데, 이때 다음 수행되어야 하는 동작은 무엇인지 확인하야 한다. 카드 개수가 홀수였다면, 홀수 카드를 모두 버리고 난 후 다음으로 수행되어야 하는 동작은 첫 번째 카드를 뒤로 보내는 동작이다. (위 이미지 왼쪽에서 6번째 줄을 확인하면 된다.) 카드 개수가 짝수였다면, 짝수 카드를 모두 버리고 난 후 다음으로 수행되어야 하는 동작은 카드를 버리는 동작이다. (위 이미지 오른쪽에서 7번째 줄을 확인하면 된다.) 즉, 카드 개수가 홀수인지 짝수인지에 따라 수행되어야 하는 동작이 다른 것이다. 이 것을 구현하기 위해 while 반복문을 반복하는 동안 남은 카드의 개수가 홀수인지 짝수인지에 따라 서로 다르게 동작하도록 코드를 구현하였다. 이를 정리하면 아래와 같다.

• while 반복문을 이용하여 구현
• 반복문을 수행하는 동안, 남은 카드의 개수가 홀수인지 짝수인지에 따라 다르게 동작하도록 if 조건문을 이용 (하나의 루프를 모두 마치면 이후 단계가 카드를 버리는 단계가 될 수 있도록 구현)
  • 남은 카드의 개수가 홀수라면, 카드에서 짝수 인덱스를 모두 제거한 후 남은 카드에서 첫 번째 카드를 맨 뒤로 보내는 동작까지 진행
  • 남은 카드의 개수가 짝수라면, 카드에서 짝수 인덱스를 모두 제거하는 동작까지 진행
• 카드를 버리는 것은 del 함수를 이용하여 구현 (del list_name[frist_index:last_index+1:step])

---

유사 문제

BOJ | Sliver | 2161번 카드1

문제

https://www.acmicpc.net/problem/2161

2161번: 카드1

코드

import sys

n = int(sys.stdin.readline())
card = [_ for _ in range(1, n+1)]

rm_card = []

while True:
    if len(card) == 1:
        break
    
    rm_card.append(card.pop(0))
    temp = card.pop(0)
    card.append(temp)

res = rm_card + card
print(*res)