Programmers] 괄호 회전하기

📌 파이썬 으로 풀이

 

📌 문제 링크 :

프로그래머스

 

📌 문제 설명 :

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

📌 제한 사항

• s의 길이는 1 이상 1,000 이하입니다.

 

📌 입출력 예

---

추측) 

괄호짝을 배열로 만들어 준비한다. 

문자열 s를 리스트로 만들어 맨앞에 것을 pop해 뒤로 append해주는 방식으로 회전을 시키고 문자열로 합쳐준다 (처음 회전이 필요없는 경우는 그냥) 

그리고 그 문자열에서 괄호짝 배열 for문을 돌려 짝을 찾으면 삭제하는 방식을 반복한다. 

대신 3개의 괄호짝이 없을 경우 각각 flag를 0으로 바꾸어주고 모두 0이 되면 카운팅 없이 나오기

text길이가 0이되면 모두 지워냈으므로 올바른 괄호문자열이라 카운팅한다

이를 반복해서 마지막에 카운트를 반환

 

소스코드) 

* 1차) 실패 : 정확도 78.6

def solution(s):
    answer = 0
    bracket = ['()', '[]', '{}']
    s_list = list(s)
    for i in range(len(s)):
        text = ""
        if i != 0:
            s_list.append(s_list.pop(0))
            text = ''.join(one for one in s_list)
        else :
            text = s

        flag_list = [1, 1, 1]
        flag = True
        while flag:
            if len(text) == 0 :
                answer += 1
                break

            if flag_list == [0, 0, 0]:
                break

            for x in range(len(bracket)) :
                if bracket[x] in text:
                    text = text.replace(bracket[x], "")
                else:
                    flag_list[x] = 0
                    pass

    return answer

* 2차) 실패 : 정확도 92.9 😭 악 단하나의 케이스가

def solution(s):
    answer = 0
    bracket = ['()', '[]', '{}']
    s_list = list(s)
    for i in range(len(s)):
        text = ""
        if i != 0:
            s_list.append(s_list.pop(0))
            text = ''.join(one for one in s_list)
        else :
            text = s

        flag_list = [1, 1, 1]
        flag = True
        while flag:
            if len(text) == 0 :
                answer += 1
                break

            if flag_list == [0, 0, 0]:
                if text.find(bracket[0]) and text.find(bracket[1]) and text.find(bracket[2]):
                    break

            for x in range(len(bracket)) :
                if bracket[x] in text:
                    text = text.replace(bracket[x], "")
                else:
                    flag_list[x] = 0
                    pass

    return answer

* 3차) 성공

def solution(s):
    answer = 0
    bracket = ['(',')', '[',']', '{','}']
    s_list = list(s)
    for i in range(len(s)):
        if i != 0:
            s_list.append(s_list.pop(0))

        stack = []
        for one in s_list:
            stack.append(one)
            stack_len = len(stack)
            if stack_len >= 2:
                for x in range(0,len(bracket),2) :
                    if stack[stack_len-2:stack_len] == bracket[x:x+2]:
                        stack = stack[:stack_len-2]

        if len(stack) == 0 :
            answer += 1

    return answer

 

 

리뷰) 

 

1차)

플래그를 세울기점을 잘 생각해봐야 할듯하다.

왜냐면 지금 내 로직대로는 만약 ({}) 괄호 경우 () 차례에서 이걸 못찾아서 플래그를 0으로 넣고 {} 이걸 지우고 나서야 ()를 판별할 수 있는데 이미 플래그는 0이 됬기 때문

 

2차) 

통과하지 못한 1번 케이스 뭐지..  1번 케이스로 고민하다가 전에 이거랑 비슷한 문제를 풀었던게 생각나서 햄버거 문제에서 썼던 stack 방식을 응용하니 바로 3차에서 성공 오오오!!!! 이런 유형이 바로 스택 유형!

 

Programmers] 햄버거 만들기

 

그런데! 3차 방식으로 통과한거랑 2차에 하나의 케이스만 실패한 경우를 비교하면 2차가 더 말도안되게 빠름... 

2차는 for/while/for 로 사용한 3중 문인데 훨씬더 속도가 빠르다 😯😯

2차가 통과하지 못한 케이스에 대해 좀더 생각해봐야할 듯 하다.

 

3차 결과

2차 결과