bobonobo   3년 전

기존 코드에서 최대한 간략화해 짜봤는데 이마저도 시간초과가 나왔습니다..

k550706   3년 전

힌트를 좀 드리자면

예를 들어서 예제와 같이 입력이 들어온다고 치면

4
0 1 1 0
1 2 3 4
3
2 4 7


2번째 줄에서 1인경우(즉 자료구조가 스택인경우)는 모두 무시하시고 처리하셔도 답은 같습니다.

왜냐하면 스택은 선입후출이므로, 1번째 자료구조를 보시면 기존 스택에 [1]이 있는 상태이고 새로운 데이터가 2로 들어오잖습니까(5번째줄 첫번재 항).

[1,2]로 데이터를 넣자마자 바로 2가 빠지면서 [1]으로 다시 변해서 굳이 스택에 있는 데이터는 처리할 필요가 없습니다.

즉 굳이 데이터를 넣고 빼는 행위를 하는것 자체가 시간낭비입니다.

그렇다라면 예시의 [1,2,3,4]는 결국 스택인 데이터를 모두 제외하고 [1,4]만 있는 상태라고 보셔도 답이 같습니다.

참고로 이 데이터는 가장 뒤의 데이터인 4부터 차례대로 출력이 될 예정입니다.

즉 5번째 줄의 데이터가 뭐가 되었든지 간에, 출력되는 데이터는 차례대로 4,1이 될거고

그 이상의 경우 5번쨰 줄에서 push하는 데이터가 될거에요.


설명이 조금 난잡한데, 잘 고민해보시고 스택과 큐의 특성을 생각해보셔서 처리하시면 답이 보이실거에요.

zenith82114   3년 전

O(N+M)에 해결 가능한 문제입니다. 힌트 1. 11번 줄 if문을 봤을 때, 이 문제에서 스택들이 의미가 있을까요? 힌트 2. 스택들을 다 없애면 큐들만 남는데, 큐들을 여러 개 이어붙이면 무엇이 될까요?

bobonobo   3년 전

헐 두분 다 이해하기 쉽게 말해주셨습니다. 감사합니다!

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