[프로그래머스/C#] 괄호 회전하기

문제

---

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

프로그래머스

 

 

 

 

 

코드

---

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(string s) {
        int answer = 0;
        Dictionary<char, char> d = new Dictionary<char, char>(){{')', '('}, {']', '['}, {'}', '{'}};
        int size = s.Length;
        for(int i = 0;i<s.Length;i++){
            Stack<int> stack = new Stack<int>();
            for(int j = i;j<i+size;j++){
                char c = s[j%size];
                if(c=='('||c=='['||c=='{'){
                    stack.Push(c);
                }
                else if(c==')'||c==']'||c=='}'){
                    if(stack.Count==0||stack.Peek()!=d[c]){
                        answer=0;
                        break;
                    }
                    else if(stack.Count>0&&stack.Peek()==d[c]){
                        stack.Pop();
                        if(stack.Count==0)
                            answer++;
                    }
                }
            }
            if(answer!=0&&stack.Count==0)
                break;
            else answer=0;
        }
        return answer;
    }
}

 

 

 

풀이

---

x번 회전시켰을 때 올바른 괄호 문자열이 되게 하는 x의 개수를 구하기 위해서는 다음을 고려해야 한다.

 

A, B가 올바른 괄호 문자열이라면 AB도 올바른 괄호 문자열이다. => BA 역시 올바른 괄호 문자열이다.

즉 전체 문자열이 올바른 괄호 문자열일 때 문자열의 시작이 올바른 괄호인 부분 문자열의 시작지점이면 된다.

이와 같은 전제를 가지고 위의 코드를 짰다.

 

각각의 괄호 짝들을 dictionary를 사용하여 연결하였다.

 

 

for문을 이용하여 순회

바깥쪽 for문은 올바른 괄호 문자열 검사의 시작지점을 나타내며, 그 때마다 스택을 새로 생성해준다.

안쪽 for문은 올바른 괄호 문자열 검사를 위해 i를 기점으로 전체 문자열을 순회하는 부분이다.

 

안쪽 for문의 코드이다.

'(', '{', '[' 문자를 만났다면 stack에 삽입

')', '}', ']' 문자를 만났다면 stack의 top에 있는 문자가 dictionary에 저장되어 있는 문자와 같은 쌍이 아니라면 answer를 0으로 만들고, 더 이상 탐색할 가치가 없으므로 break;

만약 같은 쌍이라면 stack을 pop하여 top에 있는 문자를 제거, 만약 스택이 비어있다면 올바른 괄호의 부분문자열 하나를 발견한 것이므로 answer를 1 증가

 

만약 올바른 괄호의 부분 문자열을 찾았고, 그게 전체적으로도 올바른 괄호 문자열 형태를 띈다면 for문을 벗어나고 바로 answer를 return

그게 아니라면 answer 값을 0으로 만들고 다시 for문 순회