jh05013   1년 전

먼저, 10828번 (스택) 문제와 똑같은 실수를 할 수 있는 문제이므로 그 문제의 FAQ 글을 링크하겠습니다.

https://www.acmicpc.net/board/...

  1. 주어진 명령의 수는 최대 2,000,000개입니다.
  2. 모든 출력에 대해 개행문자를 출력하세요.
  3. pop, front, back을 부르기 전에 인덱스 검사를 하세요.
  4. C, C++의 char형 배열에 명령을 입력받고자 하면 그 배열의 크기는 6 이상이어야 합니다. 널 문자까지 받아야 하기 때문입니다.
  5. 입력되는 정수는 최대 100,000입니다. 한 자리만 입력받으면 안 됩니다.

위의 조건을 만족하도록 코드를 짰는지 눈으로만 보지 말고 입력을 직접 만들어서 넣으세요. 예를 들어 5번을 검사하려면 push 100000을 한 다음 pop을 해 보면 됩니다.

그리고 이 문제는 10845번 문제와 달리 N이 최대 2,000,000이기 때문에, 연산을 비효율적으로 구현하면 시간 초과입니다. 예를 들어,

  1. push, pop 등을 할 때마다 큐의 길이 만큼 for문을 돌리면 안 됩니다.
  2. C++ vector에서 특정 위치에 있는 원소를 제거하면 안 됩니다. 그 뒤에 있는 원소들을 일일이 왼쪽으로 미느라 시간이 낭비되기 때문입니다.
  3. Python list에서 특정 위치에 있는 원소를 제거하면 안 됩니다. 위와 같은 이유입니다. 특히 pop(0)는 절대로, 절대로, 절대로, 절대로 하면 안 됩니다!!!
  4. 나머지는 보이는 대로 추가하겠습니다.

그리고 입출력이 느리면 그것 때문에 시간 초과가 날 수 있습니다. 의외로 이 문제에는 입출력 때문에 시간 초과가 나는 제출이 가장 많습니다. https://www.acmicpc.net/problem/15552 를 풀어 보세요.

jh05013   10달 전

추가 내용:

시간 초과가 난다면 Python 말고 Pypy로 제출해 보세요.

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