[알고리즘] 프로그래머스 - 괄호 회전하기

괄호 회전하기

입출력 예)

 

 

 

1. 구해야 하는 것
    # 괄호로만 이루어진 문자열 s를 왼쪽으로 회전시켜서 
    # 올바른 괄호문자열이 되는 x의 개수
2. 1을 구하기 위해 필요한 것
    # 이동시킨 문자열이 유효한가를 판단 및 삭제
        # 스택에 하나씩 쌓아가면서, 스택에 만약 여는 괄호가 있고,
        # 마지막으로 들어온 원소가 닫는 괄호라면 둘다 없애기
    # 회전시킬 방법
        # for문을 사용해 원소를 슬라이싱해서 불이기
3. 그 외 고려해야 할 사항
    # 스택?
    # 시간복잡도?

 

 

1. 처음 접근(실패)

  for문과 슬라이싱을 통해 문자열을 한번 회전시킨 문자열을 s_spin이라는 변수에 할당

 여는 괄호가 스택에 들어있고, 스택의 마지막 원소가 닫는 괄호라면, 해당 괄호를 replace

그러나 다음과 같은 상황에서 문제 발생.

({)} 처럼 생긴 괄호는 올바른 괄호가 아니지만 올바르게 판별해서 정답을 내지 못했다.

def solution(s):
    answer = 0
    for i in range(len(s)):
        s_spin = s[i+1:]+s[:i+1]
        stack = ''
        # print(s_spin)
        for i in s_spin:
            stack += i
            if stack:
                if '(' in stack and stack[-1] == ')':
                    stack = stack.replace(')',"")
                    stack = stack.replace('(',"",1)
                if '{' in stack and stack[-1] == '}':
                    stack = stack.replace('}',"")
                    stack = stack.replace('{',"",1)
                if '[' in stack and stack[-1] == ']':
                    stack = stack.replace(']',"")
                    stack = stack.replace('[',"",1)
        if not stack:
            answer += 1
    return answer

 

 

2. 수정한 코드

올바른 괄호로만 이루어지려면 무조건 올바른 괄호가 하나 이상 존재해야 하기때문에,

if문으로 만약 있다면 제거해줬다.

def solution(s):
    answer = 0
    for i in range(len(s)):
        s_spin = s[i+1:]+s[:i+1]
        stack = ''
        for i in s_spin:
            stack += i
            if '()' in stack:
                stack = stack.replace('()','')  
            if '[]' in stack:
                stack = stack.replace('[]','')
            if '{}' in stack:
                stack = stack.replace('{}','')
        if not stack:
            answer += 1
    return answer

 

 

3. 다른 분의 코드

불필요하게 stack을 사용하지 않고 문자열을 복사해와서 바로 while문으로 올바른 괄호를 모두 지운뒤,

마지막에 빈 문자열이면 answer의 값을 올려주었다.

def solution(s):
    answer = 0
    for _ in s:
        s=s[1:]+s[:1] 
        a=s 
        while "()" in a or "[]" in a or "{}" in a: 
            a=a.replace("()","").replace("[]","").replace("{}","")
            if a == "":
                answer += 1
    return answer