[백준] 1158 - 요세푸스 문제 - (python 파이썬)

 

문제링크 : https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

풀이과정:

몇일전 자료구조 수업을 다시들으면서 큐와 요세푸스 개념을 들었기 때문에, 쉽게 해결될 것이라

생각하였는데, 시간초과 때문에 생각보다 꽤나 고전했다. 처음에 풀었던 풀이다.

 

#처음 시도(시간초과)
def josephus(N, K):
    answer = []
    current = 0
    lst = [i for i in range(1, N+1)]
    while len(lst[current:]) != 1:
        if (current+1)%K == 0:
            answer.append(str(lst[current]))
        else:
            lst.append(str(lst[current]))
        current += 1
    answer.append(str(lst[current]))
    return answer

N, K = map(int, input().split())
print("<", ", ".join(josephus(N, K)), ">", sep='')

 

틀린 풀이는 아니다. 계속해서 인큐 디큐를 하기때문에 리스트의 길이가 계속해서 길어지고,

반복문이 오래돌다보니 시간초과가 뜬 모양이다. 다른 사람들의 코드를 참고했고, 핵심은 

K번째 항들만 뽑아서 정답지에 옮겨놓는것이다. 또 반복문도 N번 밖에 돌지않는다.

그 과정속에서 current 즉 pop 대상이 되는 index를 찾아주는것이 쉽지않았다.

 

#효울적인 코드(시간초과X)
def josephus(N, K):
    answer = []
    current = 0
    lst = [i for i in range(1, N+1)]
    while len(lst):
        current += K-1
        current %= len(lst)
        answer.append(str(lst.pop(current)))
    return answer

N, K = map(int, input().split())
print(josephus(N, K))
print("<", ", ".join(josephus(N, K)), ">")

 

후기:

자료구조는 끝이없다... 그리고 맨날 시간초과..... 빠르고 효율적인 코드를 짜야한다..