백준: 1158 요세푸스 문제

문제

1158번: 요세푸스 문제

 

문제 풀이

 해당 문제를 보고 처음에 드는 생각은 원형 큐 문제인가? 생각이 들었다. 하지만 순회하면서 pop을 하고자 하는 index에 위치하는 값을 제거하는 것은 다소 비효율적이다. 

 

from collections import deque


def solution(k, n):
    mans = deque([num + 1 for num in range(k)])
    answer = []
    cnt = n
    while mans:
        if cnt:
            mans.append(mans.popleft())
            cnt -= 1
        else:
            answer.append(str(mans.popleft()))
            cnt = n

    return answer

 위의 코드 처럼 원형 큐를 순회 한다고 생각하고 코드를 작성하는 방식을 구현하여 정답을 제출하면 어떨까? deque를 이용해 list의 pop을 사용하는 것보다 오버헤드가 줄겠지... 하고 제출해보았다.😮

결과는 좋지 않다...😓 문제는 맞출 수 있지만 시간이 무려 3284ms가 걸린다. 다시 가만히 생각해보면 list의 원소들을 rotation시킬 경우, %를 통해 처리하는데 이것도 그 문제인가? 생각이 들었다.

 

즉, 문제 풀이는 다음과 같이 접근하면 된다.

• 원형 큐와 같이 생각하고 접근하여도 문제를 해결 할 수 있다.
  • 파이썬이 아닌 다른 언어라면 시간이 더 짧게 나올 수도 있다고 생각한다.
• list의 원소를 rotation하는 문제들 처럼, % 연산을 활용하여 index의 값을 바로바로 도출하면 된다.

 

코드

import sys


def solution(k, n):
    mans = [num + 1 for num in range(k)]
    answer = []
    pop_idx = 0

    while mans:
        pop_idx = (pop_idx + n) % len(mans)
        answer.append(str(mans.pop(pop_idx)))

    return answer

if __name__ == "__main__":
    k, n = map(int, sys.stdin.readline().split())
    print("<%s>" %(", ".join(solution(k, n - 1))))

원형 큐를 통해 전체를 순회하는 방식과 달리 훨씬 효율적으로 문제를 풀 수 있는 것을 알 수 있다.