[프로그래머스 / C언어] 코딩테스트 '괄호 회전하기' 문제

프로그래머스 코딩테스트 연습 문제 중 '괄호 회전하기' 문제를 풀어보았다.

https://school.programmers.co.kr/learn/courses/30/lessons/76502#

프로그래머스

 

 비슷한 문제를 예전에 풀었던 기억이 있는데, 아마 괄호 회전하기가 아니라 그냥 괄호가 올바른지 확인하는 문제였던 것 같다. 비슷한 문제를 쉽게 풀었던 기억이 있어 문제 풀이를 업로드하지 않으려 했으나, 간과했던 부분이 있어 올리게 되었다.

 

 처음에는 stack을 사용하지 않고, 크기가 3인 int array를 선언해서, 각각의 닫는 괄호가 여는 괄호보다 먼저 나오지 않는지 확인하는 방식으로 코드를 작성했다. 그렇게 하니, 테스트 케이스에서 이상하게 하나만 오답이 나오고 나머지는 정답이 나왔다. 그렇게 고전하던 끝에 질문 게시판에서 나에게 맞는 반례를 발견했고, 이 문제는 결국 stack으로 풀어야 하는 문제라는 것을 깨달았다. 

 

 오류가 발생하는 원인을 찾게해준 반례는 아래와 같다. 아래의 경우, 여는 중괄호 뒤에 닫는 중괄호가 나오고, 여는 소괄호 뒤에 닫는 소괄호가 나오므로, 괄호의 종류 별로 나누어 보면, 즉 내가 앞서 사용했다고 언급한 방식대로 보면 result로 1이 도출되게 된다. (현상태인 s=0일 때가 올바른 괄호 문자열, 나머지 경우 아님) 하지만 아래의 경우는 올바른 괄호 문자열이 아니다. 중괄호가 닫히기 전에 소괄호가 열렸기 때문이다.

input : "{(})"
result : 1
answer : 0

 

 위와 같은 반례를 처리하기 위해서는 결국 스택을 사용해주어야 한다. 수정한 코드 전문은 아래와 같다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool is_correct(const char* s, int len, int l, int r) {
    int* stack = (int*)malloc(sizeof(int) * len);
    int top = 0;
    
    do {
        char cur = s[l];
        if (cur == '(' || cur == '{' || cur == '[') {
            stack[top++] = cur;
        } else if (cur == ')') {
            if (top > 0 && stack[top-1] == '(') top--;
            else return false;
        } else if (cur == '}') {
            if (top > 0 && stack[top-1] == '{') top--;
            else return false;
        } else if (cur == ']') {
            if (top > 0 && stack[top-1] == '[') top--;
            else return false;
        }
        l++;
        if (l == len && r != len) l = 0;
    } while (l != r);
    free(stack);
    
    if (top == 0) return true;
    else return false;
}

int solution(const char* s) {
    int len = strlen(s);
    int answer = 0;
    if (is_correct(s, len, 0, len)) answer++;
    for (int i = 1; i < len; i++) {
        if (is_correct(s, len, i, i)) answer++;
    }
    return answer;
}