")("가 입력으로 주어진다면 답은 $1$입니다. 말씀하신 대로 첫 날에 "X" 하나만 놓으면 가능하기 때문입니다.
올바른 괄호 문자열을 판별하는 스택 문제는 "("와 ")"를 짝짓는데, 항상 "("가 먼저 오고 ")"가 나중에 오는 경우만을 짝지었잖아요? 하지만 이 문제는 조금 다르죠. "()" 와 같은 형태로 짝을 지을 수 있지만, ")("와 같은 형태로 짝을 짓는 경우도 가능할 것입니다.
"()"와 마찬가지로 ")("도 올바른 쌍으로 생각해 주신다면 접근법이 조금 달라질 수 있을 거에요. 괄호들이 나오면 종류 불문 stack에 push하다가, stack의 맨 위에 있는 괄호와 지금 주어지는 괄호가 서로 반대 방향이면 pop한다면 어떨까요?

koreauniv 1년 전
‘)(’와 같은 input이 주어지는 경우는
-1이 출력되어야 하나요?
첫날에 X 하나만 놓으면 가능한 게 아닌가요?
스택으로 풀려 했는데 의문이 들어 여쭤봅니다.