Lessons7. Stacks and Queues(스택과 큐)

스택과 큐는 가장 기본적인 자료구조이다. 자료구조란 자료를 효율적으로 관리하고 구조화 시키는 것을 뜻한다.
스택(Stack)은 ‘쌓아 올리다’의 뜻을 가진 영단어이다. LIFO(Last In First Out)형태로 마지막에 넣은 자료를 가장 먼저 꺼낼 수 있다.
큐(Queues)는 ‘줄을 서서 기다리다’의 뜻을 가진 영단어이다. FiFO(First In First Out)형태로 가장 먼저 넣은 자료를 가장 먼저 꺼낼 수 있다.

1. 문제

문자열 S가 있고, S는 (, ), {, }, [, ]6가지의 문자로 이루어져 있다.
(), {}, [] 각각 한 쌍으로 이루어져야 한다. (], {) 같은 형식은 0을 반환한다.

• {[()()]} 잘 이루어진 문자열이다. 1을 반환한다.
• ([)()] 2번 [로 열려서 3번 ) 닫힌다. [) 이 되므로 0을 반환한다.
• ([{()})] 4, 5번 (), 3, 6번 {}, 2, 7번 [)이 되므로 0을 반환한다.

2. 정답

첫번째 - 100점

$O(N)$

int solution(char *S) {
    
    int stack[strlen(S)];
    int top=-1;
    
    for(int i = 0; i < strlen(S); i++){
        if(S[i] == '[' || S[i] == '{' || S[i] == '(' ){
            stack[++top] = S[i]; 
        }
        else{
            int dif = S[i] - stack[top];
            if(dif == 1 || dif == 2) 
                top--;
            else 
                return 0;
        }
    }
    
    return top < 0 ? 1 : 0;
}

[, {, (값이 나오면 스택에 쌓아올라간다.
], }, )값이 나오면 스택에서 자료를 가져와 비교하여 한쌍이 되는지 확인한다.

비교 부분은 아스키코드(ASCII Code)를 이용하였다. ( = 40, ) = 41 이 된다.
) - ( = 1이 된다. 나머지도 각각 [ = 91, ] = 93, { = 123, } = 125 이다.
] - [ = 2, } - { = 2