[백준 10799번] 쇠막대기 (C++, Python)

이번 포스트에서는 백준 알고리즘 문제인 쇠막대기 를 리뷰하겠습니다.

 

해당 문제는 solved.ac 기준 실버 2에 위치한 문제입니다.

 

먼저 문제입니다.

쇠막대기와 레이저의 배치를 나타내는 String이 입력으로 주어집니다.

 

이때, 레이저는 여는괄호와 닫는괄호의 쌍으로 표현되고, 쇠막대기는 왼쪽 끝이 여는괄호, 오른쪽 끝이 닫는괄호로 표현됩니다.

 

그 결과, 잘려진 쇠막대기의 조각 개수를 구하는 문제입니다.

 

이 문제는 다음과 같은 알고리즘으로 해결합니다.

 

먼저 스택이 공백이 아닌 경우입니다.

 

쇠막대기의 왼쪽 끝을 의미하는 여는괄호가 인식될 때, 결과값을 1 증가시키고 스택에 1을 PUSH 합니다. (왼쪽 끝으로 막대기 1개가 있다고 가정)

 

직전 문자가 여는괄호이고 현재 문자가 닫는괄호라면, 스택에서 POP 연산을 1회 수행하고 결과값에서 1을 뺀 후, 현재 스택의 길이를 결과값에 추가합니다. (POP연산과 결과값에서 1을 빼는 건, 직전 문자가 여는괄호여서 쇠막대기 1개로 인식했으나 현재 닫는괄호가 추가됨으로서 레이저로 인식해야하므로, POP연산과 결과값에서 1을 빼는 것을 수행합니다.) 이에 더해, 스택의 길이를 더하는 이유로는 레이저로 쇠막대기를 잘랐기 때문에 현재 인식된 쇠막대기가 2배가 됩니다.

 

직전문자가 닫는괄호이고 현재 문자가 닫는괄호라면, 스택에서 POP 연산을 1회 수행합니다.

 

스택이 공백인 경우, 스택에 1을 PUSH하고, 결과값을 1 증가시킵니다. 이 경우, 어떠한 쇠막대기도 남아있지 않은 경우이므로, 올바른 쇠막대기가 들어온다고 가정할 때, 스택에 1을 PUSH하고 결과값을 1 증가시키는 연산을 수행하게 됩니다.

 

해당 내용의 순서를 정리하면 다음과 같습니다.

1. 괄호 문자열을 입력받는다.
2. 괄호 문자열의 길이만큼 반복문을 돌며 다음 조건들을 검사합니다.
   1. 스택이 공백이 아니라면 다음 조건을 검사합니다.
      1. 현재 문자가 여는괄호라면, 스택에 1을 PUSH하고, 결과값을 1을 증가시킵니다.
      2. 직전 문자가 여는괄호이고, 현재 문자가 닫는괄호라면, 결과값을 1 감소시키고 POP 연산을 1회 수행한 후 결과값에 스택의 길이만큼 추가합니다.
      3. 직전 문자가 닫는괄호이고, 현재 문자가 닫는괄호라면, POP 연산을 1회 수행합니다.
   2. 스택이 공백이라면, 스택에 1을 PUSH하고, 결과값을 1을 증가시킵니다.
3. 결과값을 출력합니다.

아래는 C++ 코드입니다.

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
int stack[200000] = {0,};
int top = 0;
 
int main() {
    int res = 0;
    char input[100001];
    cin >> input;
    int length = strlen(input);
    
    for(int i = 0; i < length; ++i) {
        if(top > 0) {
            if(input[i] == '(') {
                stack[top++] = 1;
                res++;
            }
            else if(input[i-1] == '(' && input[i] == ')') {
                res--;
                stack[--top] = 0;
                res += top;
            }
            else if(input[i-1] == ')' && input[i] == ')') {
                stack[--top] = 0;
            }
        else {
            stack[top++] = 1;
            res++;
        }
    }
    cout << res;
 
    return 0;
}        

다음은 Python 코드입니다.

 

stack = []
 
def push(n) :
    stack.append(n);
 
def pop() :
    stack.pop(-1)
 
def isEmpty() :
    if len(stack) > 0 :
        return False
    else :
        return True
 
iron = input()
length = len(iron)
res = 0
 
for i in range(length) :
    if isEmpty() == True :
        push(1)
        res += 1
    else :
        if iron[i] == '(' :
            push(1)
            res += 1
        elif iron[i-1] == '(' && iron[i] == ')' :
            res -= 1
            pop()
            res += len(stack)
        elif iron[i-1] == ')' && iron[i] == ')' :
            pop()
 
print(res)

해당 문제는 스택의 길이와 쇠파이프간의 관계를 이해하고 PUSH, POP 연산을 괄호로 연관지을 수 있다면 풀이가 어렵지는 않은 문제였습니다.

 

다음 포스트에서 또 다른 문제 풀이로 작성해보겠습니다. 감사합니다.