[프로그래머스] 올바른 괄호 (python)

문제

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 

 

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

 

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 만드는 문제입니다.

 

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

 

 

풀이

 이 문제는 스택을 이용하여 여는 괄호( '(' ) 와 닫는 괄호( ')' ) 의 짝이 일치하는지를 찾는 문제입니다. 

 

문제의 해결을 위해 스택을 이용해야하고, 괄호의 짝이 맞는지를 확인해야 하기 때문에 처음에 접근을 다음과 같이 진행하였습니다.

 

 

1. answer 리스트 (스택) 의 길이가 0인 경우 (비어있는 경우)

   - '(' 일 경우 answer에 append 

   - ')' 일 경우 짝이 맞지 않게 되어 False를 리턴

 

2. answer 리스트의 길이가 0이 아닌 경우 

  - '(' 일 경우 더 이상 확인할 것이 없기 때문에 동일하게 answer에 append 

  - ')' 일 경우 다시 2가지로 나누어짐

     - answer 리스트의 top 값 (answer[-1]) 이 존재하는 경우에는 top 값을 pop

     - answer 리스트의 top 값이 존재하지 않는 경우 (비어있는 경우) 에는 False를 리턴

 

3. 위의 과정이 모두 끝난 후

  - answer 리스트의 길이가 0보다 클 경우 -> 짝이 맞지 않는 경우이므로 False를 리턴

  - answer 리스트의 길이가 0인 경우 -> True를 리턴

 

코드로 정리하면 대략적으로 다음과 같을 것입니다.

def solution(s):
    answer = []
    
    for i in s:
    	if(len(answer) ==0):
        	if(여는괄호일때):
            	answer.append(i)
            else:
            	return False
        else:
        	if(여는괄호일때):
            	answer.append(i)
            else:
            	if(top이 존재하는 경우):
                	answer.pop()
                else:
                	return False
    
    if(len(answer) ==0):
    	return False
    else:
    	return True

 

이렇게 풀이를 하고 나니 2번의 조건에서 리스트의 길이가 0이 아닐때 ')' 가 나온경우 조건이 top이 존재하는지를 비교하는 것인데, 이 문제에서는 ')'를 append 하는 일은 없으므로 결국 answer 리스트가 비어있는지를 확인하는 것이 됩니다. 또한 '('일 경우에는 별다른 조건없이 리스트에 append하면 됩니다.  즉 1번 조건과 2번 조건을 각각 따로 처리할 필요가 없다는 것을 의미합니다. 지금까지 정리한 내용을 토대로 조건을 다시 정리하면 다음과 같습니다.

 

 

1. 문자열의 n번째 값이 '(' 일 경우 

   - 조건없이 answer에 append 

 

2. 문자열의 n번째 값이 ')' 일 경우 

  - answer 리스트의 길이가 0이면 (비어있으면) False를 리턴

  - 비어있지 않은 경우 top 값은 무조건 '(' 이므로 pop

 

3. 위의 과정이 모두 끝난 후

  - answer 리스트의 길이가 0보다 클 경우 -> 짝이 맞지 않는 경우이므로 False를 리턴

  - answer 리스트의 길이가 0인 경우 -> True를 리턴

 

 

이렇게 조건을 정리하니 위의 방법으로 풀이를 진행했을때보다 비교해야하는 조건이 줄어든 것을 확인할 수 있습니다. 코드로 작성하면 다음과 같습니다.

 

def solution(s):
    answer = []
    
    for i in s:
        if(i == '('):            # '(' 일 경우 push 해주면 됨
            answer.append(i)
        else:
            if(len(answer) == 0):    # ')' 일 경우 answer가 비어있으면 짝이 안맞다는 것임
                return False
            else:                    # answer에 값이 있을 경우 pop 해주면 됨
                answer.pop()
    
    if(len(answer) !=0):         # 여는 괄호가 닫는 괄호보다 많은 경우 짝이 안맞음(False)
        return False
    else:
        return True

 

 

 

이렇게 풀이하니 코드의 길이도 줄어든 것을 확인할 수 있으며 정확성/효율성 테스트도 모두 잘 통과하는 것을 확인할 수 있습니다.