[BOJ][Python]백준 2164번 풀이

그냥 듀크입니다. 이번 문제는 시간복잡도와 공간복잡도의 압박을 강하게 걸어오는 문제라서 저에겐 상당히 힘들었습니다. 바로 한 번 가볼까요.

 

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

2164번: 카드2

코드 :

import sys
ssr = sys.stdin.readline

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

처음엔 뭐 많은 분들이 바로 떠올렸듯이 문제에서 시키는 대로 맨 앞에 거는 지우고 그다음 거는 뒤로 넘기는 식으로 풀었습니다. 문제 자체는 쉽게 풀리지만 바로 시간 초과가 나더군요. 그래서 그다음에는 재귀 형태로 구현을 해보자 싶어서 재귀로 풀었습니다. 당연하게도 바로 시간 초과가 났었고요. 제가 찾았던 규칙성은 0과 짝수 인덱스들의 숫자들은 모조리 지워진다는 점이었는데, 저는 여기서 생각이 멈춰버리는 바람에 O(1) 짜리 알고리즘은 생각해내지 못했습니다. 너무 시간을 많이 할애할 수 없어서 다른 분의 풀이를 봤는데 입력 숫자보다 작은 2의 승수와 입력과의 차이에 2를 곱한 것이 그 규칙이라고 하더군요. 이 방법을 이용해서 시간 복잡도를 O(1)로 줄일 수 있었습니다.

 

이런 규칙성을 빨리 찾아내는 시각을 길러야 하는데 아직 한참 멀었나 봅니다.

 

그냥 듀크였습니다.