[알고리즘 문제 풀이] - 올바른 괄호

오늘도 프로그래머스에서 문제들을 풀어 보았습니다.

 

 

 

Input은 오직 괄호로만 이루어져 있습니다.

 

올바른 괄호인지 아닌지만 체크해서 True나 False로 리턴하면 되는 문제입니다.

 

Leetcode에도 비슷한 문제가 있고 Hackerrank에도 비슷한 문제가 있는걸로 봐서

 

굉장히 유명하고 자주 나오는 유형 같습니다.

 

<생각의 과정>

1. input string s를 처음부터 끝까지 살펴볼것이기 때문에 for loop을 쓴다.

 

2. 왼쪽 괄호와 오른쪽 괄호의 개수를 세자

 

3. 왼쪽부터 loop을 돌리는데 오른쪽 괄호가 더 많다면 그건 올바르지 않은 괄호다.

 

 

<풀이>

def solution(s):
    opened, closed = '(', ')'
    cnum, onum = 0,0
    for ch in s:
        if ch == closed:
            cnum += 1
            if cnum > onum:
                break
        else:
            onum += 1
    return onum == cnum

string s의 왼쪽 괄호와 오른쪽 괄호의 숫자를 세서

 

그 숫자가 다르다면 False를 리턴하는 알고리즘을 만들었습니다.

 

왼쪽에서부터 체크를 하기 때문에 어느 순간에 오른쪽 괄호가 더 많다면 그건 이미 올바르지 않은 괄호로 판단을 

 

하고 loop을 break 합니다.

 

결과는

 

 

효율성 테스트를 모두 통과 했네요.

 

사실 처음에 '('를 찾고 그에 맞는 ')' 찾아 짝지어서 string에서 제거해나가는 

 

알고리즘을 만들어서 돌려보았습니다.

 

정확성 테스트는 모두 통과를 했지만 안타깝게도 효율성을 둘다 통과 못하더군요 ㅠ

 

그래서 O(N^2)으로는 답이 없겠다 생각해서 O(N)이 가능한 알고리즘을 생각해보다가

 

'(' 개수와 ')'의 개수를 순간 마다 세는 알고리즘을 만들어서

 

통과 했네요... 후

 

처음부터 최적 시간을 고려하면서 알고리즘을 짜야 겠네요..

 

일단 답만 찾고 보자는 마인드로 문제를 풀었더니 

 

효율성에서 시간 초과가 나올때가 많네요