[백준] 2164번 : 카드2 - python

import sys 
input = sys.stdin.readline

n = int(input())
num = list(range(1,n+1))

for i in range(len(num)-1):
    del num[0]
    num.append(num[0])
    del num[0]

print(num[0])

처음 문제를 보고 작성했던 코드다.

하지만 시간 초과 오류가 나타났고, 구글링을 해본 결과 파이썬의 del 함수의 시간 복잡도가 O(n)이라는 사실을 알 수 있었다.

이후 다음과 같이 코드를 수정한 뒤 문제를 해결 할 수 있었다.

import sys 
input = sys.stdin.readline

n = int(input())
num = list(range(1,n+1))
index = 0

for i in range(len(num)-1):
    index += 1
    num.append(num[index])
    index += 1

print(num[index])

del 함수를 제거한 뒤 배열의 현재 인덱스값을 저장하는 변수를 만들어줬다.

코드는 크게 다음과 같은 순서로 동작한다.

1. n 값을 입력 받는다.
2. 배열을 만들고 1~n 까지의 정수를 저장해준다.
3. 배열에서 현재 위치를 저장해줄 변수를 만든다.
4. 제일 마지막 숫자 하나만을 남기기 위해 for 문의 범위를 0~n-1로 설정해준다.
5. 제일 위의 숫자를 버리는 동작은 index += 1로 수행한다.
6. 그 다음 숫자를 맨 밑으로 넘기는 동작은 배열 마지막에 숫자를 새로 추가해준 뒤, 5번과 마찬가지로 index +=1을 수행했다.