문제
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.
한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.
- ‘()’ 인 괄호열의 값은 2이다.
- ‘[]’ 인 괄호열의 값은 3이다.
- ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
- ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
- 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.
입력
첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.
출력
첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.
예제입력1
입력
(()[[]])([])
출력
28
예제입력2
입력
[][]((])
출력
0
📝로직
이 문제는 스택(stack)이라는 자료구조를 연습하는 문제이다. 옛날에 괄호 찾기 문제를 풀었던 기억이 나서 스택을 써야 함을 바로 생각할 수 있었다.
스택을 쓸 때는 학교에서 배운 linked list를 이용해서 구현해도 되고 많은 방법이 있지만, 나는 c++의 표준 라이브러리인 stack을 사용했다.
stack은 LIFO (Last In First Out) 구조의 Container Adapter 이다. 내부적으로는 vector, deque, list conatiner의 구조로 구현되어 있다.
stack 헤더파일을 추가하면 stack 생성자와 함수들을 사용할 수 있다.
기본적으로 'stack <자료형> 변수이름' 과 같은 형태로 선언한다.
stack을 위해 제공되는 함수들로는 push, pop, top, empty, size 등이 있다.
로직 설명
전체적인 로직은 아래와 같고, 중간중간에 예외처리를 해줘야 한다.
1. 입력 받은 문자열을 하나씩 보면서 닫는 괄호, 여는 괄호, 그 외 문자를 구분한다.
1-1. 닫는 괄호라면,
1-1-1. 해당 괄호와 스택의 top이 올바른 쌍이 될 때까지 pop하며 스택에 있는 값을 더한다.
1-1-2. 올바른 쌍이 됐다면 1-1.에서 계산한값에 해당 쌍에 맞는 값을 곱한 뒤 그 값을 push한다.
1-2. 여는 괄호라면 스택에 push한다. (편의를 위해 '('는 0, '['는 1로 바꿔서 넣는다.)
1-3. 그 외 문자라면 무조건 잘못된 괄호열이라고 판단한다.
2. 입력 받은 문자열을 모두 확인하면 스택에 남아있는 값을 더한다.코드
comp()함수에 return 0을 하는 부분이 예외처리 한 부분이다.
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
char paren[31];
int comp()
{
stack<int> st;
int temp = 0;
int result = 0;
for (int i = 0; i < strlen(paren); i++)
{
temp = 0;
if (paren[i] == ')' || paren[i] == ']')
{
while (!st.empty()) {
if ((paren[i] == ')' && st.top() == 0) || (paren[i] == ']' && st.top() == 1)) {
st.pop();
if (temp == 0) temp = 1;
if (paren[i] == ')') temp *= 2;
else if (paren[i] == ']') temp *= 3;
st.push(temp);
break;
}
else if ((paren[i] == ')' && st.top() == 1) || (paren[i] == ']' && st.top() == 0)) return 0;
else {
temp += st.top();
st.pop();
}
}
if (st.empty()) return 0;
}
else if (paren[i] == '(') st.push(0);
else if (paren[i] == '[') st.push(1);
else {
return 0;
}
}
while (!st.empty()) {
if (st.top() == 1 || st.top() == 0) {
return 0;
}
result += st.top();
st.pop();
}
return result;
}
int main()
{
scanf("%s", paren);
printf("%d", comp());
}❌코드 짜면서 한 실수❌
-
stack에 접근할 때 empty인지 체크하지 않았다. (segmentation fault 원인)
하,,, 이 실수는 정말 울고 싶은 실수였다,,,,😰
이 문제를 풀면서 정말 많이 (진짜진짜 많이,,) 채점 시도를 했는데 거의 95%가 이 에러였다.
stack에 접근할 때는 (즉, top() 혹은 pop()을 할 때) stack이 비었는지 확인을 꼭꼭 해줘야한다.
그러지 않으면 빈 스택에 접근하게 되어 올바르지 않은 메모리를 참조하게 된다. 고로 segmentation fault가 뜬다,,,,,,
근데 여기서 끝이 아니다!🤬 (지금부터가 내가 한 최대 삽질임)
이까지만 읽으면,
아~ 오키~ 그럼 empty 체크하고 top하면 되는거잖아~ if(!st.empty() && st.top()=='(') 뭐 이런식으로 짜면 되겠넹ㅎㅋ
하겠지만 이렇게 스택이 비었는지 체크하는 구문과 나머지 비교 구문을 if문에 몽땅 때려넣으면 안 된다.
다시 말해서 중첩 if문으로 '스택이 비었는가'를 먼저 확인하고 그 다음 if문에서 나머지 조건문을 써야한다.
if(!st.empty()){ if(st.top()=='(')}
이런 식으로 써야한다.
그 이유는 만약에 if문에 몽땅 때려넣으면!st.empty()가 false이고 그 뒤에&&연산이 오기 때문에 바로 if문을 빠져나올 것 같지만, 그 뒤에 있는 모든 조건을 싹 다 확인하고 결과를 내기 때문에 스택이 빈 것을 확인하고도 스택에 접근하게 된다.
(적고 나니 너무 바보 같은 실수인 것 같네,,,,,) -
예외 케이스를 꼼꼼하게 처리하지 못했다.
많은 문제에서도 해당이 될텐데, 해당 문제에서 얘기한 것만 입력으로 들어온다는 보장이 없다.
이 문제에서는 () 와 []만을 다뤘기 때문에 저 두 괄호만이 나올 것 같지만 {} 괄호가 나올 수도 있기 때문에 이를 고려해서 로직을 짜야한다.
외에도 골치아팠던 반례?등이 많았다. 위 코드를 짜면서 놓친 반례로는
([)
())))))
가 있다.
어떻게 코드를 짜느냐에 따라 반례는 달라지는게 당연하기 때문에 반례가 도저히 생각나지 않을 때는 해당 문제의 '질문 검색' 게시판을 잘 이용해보도록 하자!
⭐정리
- stack, vector, deque를 쓸 때는 비었는지 확인 한 후 접근하기
- 잘못된 메모리 참조하지 않도록 코드 짜기 (ex. 반복문이나 자료구조 쓸 때 등등)
- 까불지 말고 디버깅하기
- 예외 케이스도 꼼꼼하게 생각하기
