프로그래머스 Level 2 : 괄호 회전하기 C언어

▶문제 : 코딩테스트 연습 - 괄호 회전하기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 괄호 회전하기

 

▶코드 작성

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

int stack[501]; //()=1, {}=2, []=3

int solution(const char *s)
{
    int answer = 0;
    int len = strlen(s);
    int n;//스택 크기
    char ch;
    bool t;//올바른 괄호인지 체크

    for (int i = 0; i < len; i++) {//문자열 s를 i=0부터 회전
        n = -1;
        t = true;
        for (int j = i; j < len; j++) {//문자열의 i부터 len-1까지 괄호 확인
            ch = s[j];
            if (ch == '(') stack[++n] = 1;//소괄호 : 1
            else if (ch == '{') stack[++n] = 2;//중괄호 : 2
            else if (ch == '[') stack[++n] = 3;//대괄호 : 3
            else if (ch == ')' && stack[n] == 1) n--;//스택 마지막이 소괄호라면 pop
            else if (ch == '}' && stack[n] == 2) n--;//스택 마지막이 중괄호라면 pop
            else if (ch == ']' && stack[n] == 3) n--;//스택 마지막이 대괄호라면 pop
            else {//그 외는 올바른 괄호가 아니므로 종료
                t = false;
                break;
            }
        }
        for (int j = 0; j < i && t == true; j++) {//문자열의 0부터 i-1까지 괄호 확인
            ch = s[j];
            if (ch == '(') stack[++n] = 1;
            else if (ch == '{') stack[++n] = 2;
            else if (ch == '[') stack[++n] = 3;
            else if (ch == ')' && stack[n] == 1) n--;
            else if (ch == '}' && stack[n] == 2) n--;
            else if (ch == ']' && stack[n] == 3) n--;
            else {
                t = false;
                break;
            }
        }
        if (t == true && n == -1) answer++;//스택이 다 비워져있으면 올바른 괄호
    }

    return answer;
}

 

▶해석

괄호를 먼저 열고, 열었던 괄호를 닫았다는 사실을 확인해야 하므로 스택을 이용하여 풀이하였다.

이때 소괄호, 중괄호, 대괄호를 1,2,3으로 표현해 같은 종류인지만 확인할 수 있도록 하였다.

 

괄호를 열 때는 조건 없이 스택에 넣었고, 닫을 때는 열었던 순서에 맞게 닫아야 하기 때문에 스택의 맨 위 값을 확인하여 같은 종류의 괄호라면 닫는 것을 인정해 스택에서 pop 하였다.

 

문자열의 회전은 반복문을 활용해 마치 회전한 것처럼 괄호를 확인하도록 하였다.

가장 바깥 반복문의 i는 회전한 문자열의 시작점이라 생각하고

그 안쪽의 첫 번째 반복문은 i부터 len-1까지 괄호를 확인,

두 번째 반복문은 0부터 i-1까지 확인하면서

i값이 증가함에 따라 올바른 괄호인지 확인하는 시작점이 달라지게 되어 실제 회전 없이 판별할 수 있다.