yeongjin2024   1년 전

안녕하세요.

queuestack문제에서 시간을 단축하는 방법이 떠오르지 않아 문의드립니다.

2번째 덱에 queue와 stack의 대한 값을 넣고 이후 for문을 통해 인덱스값을 불러와

판별하는 로직으로 설계하였는데, 단축할 수 있는 개선안 확인 부탁드리겠습니다.

amazingtt2   1년 전

N과 M의 범위가 최대 100000이기 때문에 위 코드는 시간 초과를 피할 수 없습니다.

큐와 스택의 성질을 생각해본다면, 이 문제는 각 M마다 정답을 각 자료구조를 돌지 않고 O(1)만에 바로 알 수 있습니다.

각 자료구조에는 원소가 하나 들어가있고, 지문에 설명된 연산 특성상 하나가 들어가고 하나가 나가기 때문에, 원소의 개수는 항상 한 개로 유지됩니다.

스택은 후입선출이므로, 원래 들어가있던 원소가 절대 바뀌지 않습니다. 

결국 우린 큐에 들어가 있는 수들만 보면 됩니다. 매 원소 삽입마다 가장 마지막(뒤쪽)에 배치된 큐의 원소가 답이 됩니다. 즉 큐 하나만으로도 답을 알 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.