사용자 도구

사이트 도구


ps:problems:boj:1021

회전하는 큐

ps
링크acmicpc.net/…
출처BOJ
문제 번호1021
문제명회전하는 큐
레벨실버 4
분류

기초

시간복잡도O(n^2)
인풋사이즈n<=50
사용한 언어Python
제출기록29200KB / 84ms
최고기록52ms
해결날짜2021/08/12
태그

[라이] 리스트/배열/연결 리스트

풀이

  • 현재 원소를 뽑은 다음, 다음 원소를 뽑기 위해서 다음 원소를 맨 앞으로 옮길때, 2번 연산을 이용하는 방법과 3번 연산을 이용하는 방법중 더 짧은 방법을 고르면 된다.
  • 덱을 이용해서 실제로 똑같이 시뮬레이션 한다고 생각하면, 다음 원소의 인덱스를 구하면 왼쪽으로 로테이션 시키는것과 오른족으로 로테이션시키는 것중 어느쪽이 빠른지 계산할 수 있다. O(n)에 다음 원소의 인덱스를 구하고, O(n)에 로테이션, O(1)에 삭제를 할수 있다. 이 작업을 n번 하므로 총 시간복잡도는 O(n^2) 이 된다.
  • 실제로 덱을 갖고서 로테이션을 시키면서 시뮬레이션 할 필요 없이, 그냥 리스트를 이용하면서 시작 위치가 리스트의 몇번째 인덱스에 있는지를 유지할수도 있다. 첫번째 원소의 인덱스와 지울 원소의 인덱스의 차이를 갖고 역시 왼쪽으로 로테이션 시키는것과 오른족으로 로테이션시키는 것중 어느쪽이 빠른지 계산할 수 있다. O(n)에 다음 원소의 인덱스를 구하고, 로테이션 대신에 시작 위치를 업데이트 해주면 되므로 O(1), 대신 삭제를 리스트 중간에서 해야하므로 O(n)이 걸린다. 역시 총 시간복잡도는 O(n^2)이 된다. 이쪽이 상수값이 더 작을것 같긴 하지만, 이 문제에서는 n이 작아서 차이가 안날것 같다. 실제로 구현한 버전은 이쪽.
  • 세그먼트 트리를 이용한다면, 특정 원소의 인덱스를 구하는 것(rank 쿼리)와 삭제를 O(logn)에 할수 있으므로, 총 O(nlogn)으로 시간복잡도를 줄일수 있을것으로 생각되지만.. n<50인 이 문제에서는 더 느려질것이 확실하다보니 구현도 안해봤다.

코드

토론

댓글을 입력하세요:
Y O​ E B R
 
ps/problems/boj/1021.txt · 마지막으로 수정됨: 2022/05/03 06:45 저자 teferi