[백준 2504번] 괄호의 값
최근 업데이트 날짜:
문제 설명
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을 출력해야 한다.
알고리즘
스택(Stack)
접근 방식 및 풀이
출력 부분에서 올바르지 못한 괄호열이 입력되었을 시에 0을 출력해야 한다고 명시되어있다. 올바르지 않은 괄호열에 경우 계산을 할 필요가 없다. 그렇기 때문에 계산에 들어가기 전에 괄호열의 올바른지 확인하는 작업을 먼저 하는 것이 좋다.
올바른 괄호열 검사
올바른 괄호열은 모든 괄호가 자신의 짝이 존재해야하고 괄호의 순서가 뒤섞이지 않아야한다. ‘())’ 같은 괄호열은 마지막 ‘)’ 괄호의 짝이 존재하지 않기 때문에 올바르지 못한 괄호열이다. 또한 ‘([)]’ 같은 괄호열은 괄호의 순서가 뒤섞여있으므로 올바르지 못한 괄호열이다.
어떤 괄호열이 올바르지 못한 괄호열인지 말로는 알았다. 그렇다면 이 과정을 코드로는 어떻게 구현할 수 있을까? 바로 스택을 사용하면 된다.
괄호의 짝이 존재하는지 확인
우선 괄호열을 앞에서부터 괄호 하나씩 확인한다. ‘(‘ 괄호와 ‘[’ 괄호 같은 여는 괄호가 나왔을 경우 해당 괄호를 스택에 쌓아둔다. 그리고 ‘)’ 괄호와 ‘]’ 괄호 같은 닫는 괄호가 나온다면 스택에서 괄호 하나를 빼서 짝이 되는 괄호인지 확인한다. 이때 스택에서 괄호를 빼려고 봤는데 스택이 텅 빈 상태라면 해당 닫는 괄호와 짝이 되는 여는 괄호가 존재하지 않는 것이다.
이런 상황을 아까 위에서 언급한 ‘())’ 괄호열로 예를 들어 보자. 먼저 ‘(‘ 괄호가 나왔기 때문에 스택에 넣는다. 다음이 ‘)’ 괄호이기 때문에 스택에서 괄호를 빼와야한다. 빼서 확인해보니 ‘)’ 괄호와 짝이 되는 ‘(‘ 괄호가 나왔다. 그럼 이제 짝을 맞췄으니 다음으로 넘어가면 된다. 또 ‘)’ 괄호가 나왔다. 그래서 스택에서 괄호를 하나 빼와야하는데 스택이 비어있다. 이 경우 ‘)’ 괄호가 짝이 없는 괄호라는 것을 알 수 있다.
또한 같은 이유로 괄호열을 끝까지 확인했는데 아직 스택에 남아있는 여는 괄호가 있다면 해당 여는 괄호도 짝이 없다는 것을 알 수 있다. 해당 여는 괄호가 짝이되는 닫는 괄호를 만나지 못하여 스택에서 빠져나가지 못했기 때문이다.
예를 들어 ‘(()’ 괄호열이 있다. 괄호열을 끝까지 확인을 했을 때 ‘()’은 짝이 되어 빠져나가고 처음 넣었던 ‘(‘ 괄호만 스택에 남아있을 것이다. 이 경우 ‘(‘ 괄호가 짝이 없는 괄호라는 것을 알 수 있다.
괄호의 순서가 올바른지 확인
위에서 닫는 괄호가 나왔을 때 괄호 하나를 빼서 짝이 되는 괄호인지 확인한다고 했다. 이 때 만약 짝이 아닌 괄호가 나온다면 괄호의 순서가 잘못된 것이다.
예를 들어 ‘[(])’ 괄호열을 생각해보자. ‘[’ 괄호와 ‘(‘ 괄호는 여는 괄호이기 때문에 스택에 차례대로 스택에 들어갈 것이다. 이제 ‘]’ 괄호를 만나 스택에서 괄호를 하나 빼서 확인해본다. 그런데 우리가 기대하는 ‘[’ 괄호가 아니고 ‘(‘ 괄호가 나왔다. 이런 경우 괄호의 순서가 잘못되었다는 것을 알 수 있다.
괄호열의 값 계산
괄호열의 값을 계산하는 것도 스택을 활용한다. 괄호열이 올바른지 검사하는 과정과 비슷하다. 하지만 스택에 괄호만 들어가는 것이 아니라 숫자도 들어간다는 것이 다르다. 올바른 괄호열 검사 과정에선 괄호가 짝이 맞으면 빼기만 하면 되었지만 이번에는 짝이 맞은 괄호 쌍을 숫자로 변환해서 다시 넣어야한다.
숫자로 변환해서 다시 넣는다는 게 어떤 말일까? 예를 들어 ‘[()()]’ 괄호열이 있다고 생각하자. ‘[()’까지 확인했을 때, 안에 있는 ‘()’ 괄호쌍이 짝이 맞춰질 것이다. 이때 문제 설명에 나와있는 ‘1. ‘()’ 인 괄호열의 값은 2이다.’ 규칙에 따라 스택에 2를 넣으면 스택이 ‘[2’가 된다. 이 과정이 바로 괄호쌍을 숫자로 변환해서 다시 스택에 넣는 것이다.
괄호쌍을 숫자로 변환하는 과정에서 괄호쌍 사이에 숫자가 나올 수도 있다. 이 때 숫자가 두개 이상이라면 숫자들을 전부 더해서 하나의 숫자로 만든다. 이는 ‘5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.’ 규칙 때문이다. 모두 더해 만든 하나의 숫자(혹은 원래부터 숫자가 하나 나왔을 수도 있다.)를 X라고 치면 숫자 바깥에 싸여진 괄호 종류에 따라 ‘(X)’ 혹은 ‘[X]’의 형태가 될 것이다. 이 형태는 ‘3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.’ 규칙과 ‘4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.’ 규칙에 따라 X에 2 또는 3을 곱하면 변환 과정이 끝난다.
예를 들어 위에 나온 ‘[()()]’ 괄호열에서 마지막 괄호를 확인할 때 스택이 ‘[22’가 된다. 마지막 괄호인 ‘]’ 괄호와 짝이 되는 ‘[’ 괄호가 나올 때까지 스택에서 빼면서 숫자를 더한다. 숫자의 합이 2+2=4이므로 ‘[4]’ 형태가 된다. ‘[4]’는 3x4으로 생각할 수 있으므로 최종 결과값은 3x4=12가 된다. 현재 예시에선 12가 최종 결과값이 되지만 만약 뒤에 괄호열이 더 이어진다면 스택에 해당 숫자를 넣고 계산을 이어나가면 된다.
위와 같이 짝이 맞는 괄호쌍을 발견할 때마다 숫자로 변환해주는 과정을 반복하면 결국 주어진 괄호열의 최종 결과값을 구할 수 있다.
코드
문제 풀이에 사용한 언어: C
#include <stdio.h>
#include <string.h>
int isCorrectFormat();
int calculate();
// 스택 정의
typedef struct {
int elements[31];
int top;
} Stack;
// 스택에 새로운 element를 넣는 함수
void push(Stack *stack, int bracket) {
stack->elements[++(stack->top)] = bracket;
}
// 스택에서 제일 위에 위치한 element를 빼는 함수
int pop(Stack *stack) {
return stack->elements[(stack->top)--];
}
Stack stack; // 계산을 위해 사용할 스택
char input[31];
int length; // 괄호열의 길이
#define ROUND -1 // 둥근 괄호 ()
#define ANGLED -2 // 각진 괄호 []
int
main(){
stack.top = -1; // 스택을 초기화
scanf("%s", input);
length = strlen(input);
if(isCorrectFormat(input, length) == 0){ // 입력 받은 괄호열이 올바른 형식이 아니면
printf("0\n"); // 0를 출력
}
else{ // 입력 받은 괄호열이 올바른 형식이라면
printf("%d\n", calculate()); // 계산한 값을 출력
}
return 0;
}
// 괄호열이 올바른 형식인지 검사하는 함수
int isCorrectFormat(){
for(int i = 0; i < length; i++){ // 괄호열 길이 만큼 반복
switch (input[i]) {
case '(': // 여는 둥근 괄호
push(&stack, ROUND); // 스택에 넣는다
break;
case '[': // 여는 각진 괄호
push(&stack, ANGLED); // 스택에 넣는다
break;
case ')': // 닫는 등근 괄호
if(stack.top == -1) // 스택이 비었다면 ')' 괄호와 짝인 '(' 괄호가 없다는 것이기 때문에
return 0; // 올바르지 않은 괄호열로 판단하고 검사 종료
if(pop(&stack) != ROUND)
return 0;
break;
case ']': // 닫는 각진 괄호
if(stack.top == -1) // 스택이 비었다면 ']' 괄호와 짝인 '[' 괄호가 없다는 것이기 때문에
return 0; // 올바르지 않은 괄호열로 판단하고 검사 종료
if(pop(&stack) != ANGLED)
return 0;
break;
}
}
if(stack.top != -1) // 아직 남아있는 괄호열이 있다면 짝없는 괄호가 존재하는 것이기 때문에
return 0; // 올바르지 않은 괄호열로 판단하고 검사 종료
return 1; // 올바른 괄호열로 판단하고 검사 종료
}
// 괄호열의 값을 계산하는 함수
int calculate(){
int sum, tem;
for(int i = 0; i < length; i++){ // 괄호열 길이 만큼 반복
sum = 0;
switch (input[i]) {
case '(': // 여는 둥근 괄호
push(&stack, ROUND); // 스택에 넣는다
break;
case '[': // 여는 각진 괄호
push(&stack, ANGLED); // 스택에 넣는다
break;
case ')': // 닫는 등근 괄호
while((tem = pop(&stack)) != ROUND){ // '(' 괄호가 나올 때까지 element를 빼서
sum += tem; // 전부 더한다
}
if(sum == 0) // 숫자가 하나도 없었고 바로 '(' 괄호가 나왔다면
push(&stack, 2); // 스택에 2를 넣는다
else // 숫자가 있었다면
push(&stack, sum * 2); // 숫자들의 합에 2을 곱한 값을 스택에 넣는다.
break;
case ']': // 닫는 각진 괄호
while((tem = pop(&stack)) != ANGLED){ // '[' 괄호가 나올 때까지 element를 빼서
sum += tem; // 전부 더한다
}
if(sum == 0) // 숫자가 하나도 없었고 바로 '[' 괄호가 나왔다면
push(&stack, 3); // 스택에 3를 넣는다
else
push(&stack, sum * 3); // 숫자들의 합에 3을 곱한 값을 스택에 넣는다.
break;
}
}
sum = 0;
while(stack.top != -1){ // 스택에 모든 숫자들을
sum += pop(&stack); // 더한다
}
return sum;
}
댓글남기기