Q. 출력 초과가 뜹니다. 왜 그럴까요?

A. 출력 초과는 정답에 비해서 너무 많은 출력을 할 때 발생합니다. 이 문제에서 특히 그런 일이 많은 건, "불가능한 경우"에 NO만 출력해야 하는데 수많은 +와 -들을 출력하는 코드가 많아서 그렇습니다.

우선 "불가능한 경우"가 무엇인지 잘 생각해 보고, 중간 과정이 가능하다고 해서 바로바로 +나 -를 출력하지 말고 모아만 뒀다가, 불가능하다고 판단되는 상황이 오면 오로지 NO만 출력하고 다른 건 출력하지 않고 종료하도록 해야 합니다. 오로지 NO만 출력하도록 했는데도 출력 초과가 뜬다면 불가능한 경우를 잘못 판단한 것입니다.

Q. 런타임 에러가 납니다. 이유가 무엇일까요?

A. 여러 가지 원인이 있을 수 있지만, 우선적으로 고려해 볼 건 다음이 있습니다.

1. N이 10만까지 가능하므로, 스택의 크기도 최소 10만이 되어야 하고, 답은 개행 문자를 제외하고 20만자까지 나올 수 있습니다. 배열 크기를 충분하게 잡았는지 확인해보세요.

2. 스택이 비어있는데 스택의 top에 접근하는 연산을 해서는 안 됩니다. 보통의 배열에 대해서 [-1]에 접근해서도 안 되고, C++의 STL에 있는 stack이나 vector 등을 쓰더라도 top() 이나 back() 을 함부로 해서는 안 됩니다. 반드시 스택이 비어있는 상태인지에 대한 여부를 먼저 확인한 후 접근해야 합니다.

Q. 계속 틀리는데, 혹시 반례를 알 수 있을까요?

A. 이미 질문 게시판 https://www.acmicpc.net/board/...에 질문이 4페이지나 올라와 있습니다. 틀리는 코드에 대한 반례는 거의 다 있으리라 생각합니다.

Q. 시간 초과가 납니다...

A. 혹시 자신의 코드가 수열의 각 원소에 대해 지금까지 쌓아온 스택 전체를 순회해야 한다면 시간 복잡도가 O(N^2)이 되어 시간 초과가 될 가능성이 높습니다. 이 문제는 기본적으로 O(N)에 풀기를 원하는 문제입니다.

특히 자바를 쓰시는 분들 중에 이런 경우가 자주 보이는데, ArrayList나 LinkedList 등의 contains() 연산은 리스트를 전체 순회해야 하기 때문에 같은 문제가 발생합니다. 다른 언어들에서도 평범한 배열에 값이 있는지 없는지를 판단해주는 함수가 있다면 거의 이러한 시간 복잡도가 나올 것이므로, 주의해서 사용해야 합니다.

그리고 C++의 경우 endl 대신에 '\n'을 사용하면 시간을 획기적으로 단축할 수 있습니다.

*** Java의 경우, Integer 객체끼리의 비교를 == 또는 != 으로 하는 경우가 종종 보이는데, 이는 두 객체의 주소값이 같은지를 보는 것으로 절대로 해서는 안 되는 연산입니다. Java에서 미리 만들어 둔 객체들 범위인 127을 넘어가는 순간 더 이상 원하는 대로 동작하지 않습니다. intValue() 를 꼭 써서 비교하시기 바랍니다.