[백준] 2164번 카드2 - 시간초과, 짝수 홀수 인덱스만 추출하기

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

2164번: 카드2

 

처음에는 문제 그대로 구현하였다.

num = n
square = 0
while num >= 1:
    square += 1
    num /= 2
square = square - 1
print(2 ** square)

그리고 짝수 홀수로 나뉘네

# 카드 구성 설정
cards = []
if n >= 8:
    n // 8
    for i in range(1, n + 1):
        cards.append(i)


# 규칙 그대로 구현해본다.
delete = True
while len(cards) > 1:
    # 맨앞 카드 삭제
    if delete == True:
        del cards[0]
        delete = False
    # 맨앞 카드 위로 보내기
    else: # delete == False
        back = cards[0]
        del cards[0]
        cards.append(back)
        delete = True
print(cards[0])

 

하지만 시간 초과가 떴다.

역시 O(N^2)으로 이렇게 쉽게 풀릴리가 없지..

 

각각의 카드의 경우를 써보면서 분석해보았다.

분석한 결과

삭제 패턴
짝수번 / 홀수번 인덱스 삭제

삭제 될 인덱스: 0 2 4 6 8 ..   
이전이 짝수개: 0 2 4 6 ... (삭제 패턴 유지되네)
이전이 홀수개: 1 3 5 7 ... (삭제 패턴 바뀜)

이전 패턴 bool값 - even_index_delete = True
계속 cards 리스트 갯수로 홀/짝 구분
홀: 유지
짝: 바뀜

카드는 0 1 2 3 4  ... 이렇게

인덱스가 부여되는데

짝수번 인덱스를 삭제할 지

홀수번 인덱스를 삭제할 지

삭제할 패턴을 한바퀴 돌기 전에 매번 결정해주어야 한다.

 

가지고 있는 카드 갯수가 짝수개이면 

이전 패턴을 그대로 진행하면 된다.

 

반면,

가지고 있는 카드 갯수가 홀수개이면

이전 패턴을 반대로 진행하여야 한다.

즉, 이전에 짝수 인덱스만 삭제했다면 이번엔 홀수 인덱스만 삭제하는 걸로 바꿔야 하고

이전에 홀수 인덱스만 삭제했다면 이번엔 홀수 인덱스만 삭제하는 걸로 바꿔야 한다.

 

return cards[1::2]

위의 슬라이싱 방식으로 홀수 / 짝수 인덱스를 추출하였다.

 

구현한 결과 코드

# BOJ_2164
import sys
# 입력
n = int(sys.stdin.readline())
# 카드 구성 설정
cards = []
for i in range(1, n + 1):
    cards.append(i)

def even_index_delete(cards):
    return cards[1::2]
def odd_index_delete(cards):
    return cards[0::2]


delete_even = True
while len(cards) > 1:
    # print(cards)
    # cards의 원소의 갯수가 짝수개가 있으면 삭제할 인덱스 패턴 유지
    if len(cards) % 2 == 0:
        if delete_even == True:
            cards = even_index_delete(cards)
        else:
            cards = odd_index_delete(cards)
    # 홀수개가 있으면 삭제할 인덱스 패턴 뒤집기(홀>짝, 짝>홀)
    else:
        if delete_even == True:
            cards = even_index_delete(cards)
        else:
            cards = odd_index_delete(cards)
        delete_even = not delete_even
print(cards[0])

 

코드로 구현하면 위와 같고

채점 결과 맞게 나온다.