Code Kata 2-3

괄호로 이루어진 string 유효성 판단

문제

s는 여러 괄호들로 이루어진 String 인자입니다.
s가 유효한 표현인지 아닌지 true/false로 반환해주세요.

종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다. 아래의 경우 유효합니다.

한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
괄호 순서가 맞아야 한다.

예를 들어 아래와 같습니다.

s = "()"
return true

s = "()[]{}"
return true

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

풀이

1. 주어진 s의 인자가 열린 괄호이면 빈 리스트에 차곡차곡 쌓아주다가
2. 닫힌 괄호가 나오면 해당 닫힌 괄호가 마지막으로 쌓인(추가된) 열린 괄호와 동일한지 비교하고
3. 같다면 해당 열린 괄호를 제거하여 다음 괄호를 비교할 수 있는 상태를 만들어 주자
4. 다르다면 유효한 표현이 아니므로 False 반환

1. '('와 ')', '{'와 '}', '['와 ']' 짝 지어 주기 위한 딕셔너리 만들기

couple = {
    ')' : '(',
    ']' : '[',
    '}' : '{'
}

2. s인자를 하나씩 빼오기 위해 for문 사용

for i in string:

3. 딕셔너리에 키값(닫힌 괄호) 존재 여부 확인

if i in couple:
.
.
.

else:
  open.append(i)

존재하지 않는다는 것은 해당 인자가 열린 괄호(딕셔너리의 value값)라는 것을 의미하므로

open이라는 리스트안에 쌓아 준다.

(✔️ for문을 선언하기 전에 open이라는 빈 리스트를 만들어 둔다.)

i in couple 이 성립한다는 것은 인자가 닫힌 괄호라는것을 뜻한다.

그러므로 아래 4번의 단계를 진행

4. 쌓인 열린 괄호와 비교

if [couple[i]] == open[-1:]: 
  open.pop()
  
else:
  return False

리스트에 가장 마지막으로 쌓인 인자(open[-1])가 해당 닫힌 괄호와 짝이 맞는지 확인해 줄 단계이다.

couple[i]를 통해 해당 인자가 key값으로 존재하는 value의 값, 즉 짝이 되는 열린 괄호가 무엇인지 알 수 있다.

같다면 비교했던 열린 괄호를 삭제해주어 다음 괄호가 마지막 자리에 위치되어 비교할 수 있도록 해준다.

다르다면 문제 성립이 안되는것이므로 False 반환

이 때, open 리스트 안의 마지막값을 가지고 올 때 open[-1]이 아닌 open[-1:]을 사용한 이유는 값을 리스트 형태로 받기 위해서이다.

그렇다면 왜 리스트 형태로 받아야 할까?

리스트안에 쌓인 열린괄호가 없는경우, 즉 주어진 s에 열린 괄호가 포함되어 있지 않을 경우를 생각해 주기 위해서이다.

이런 이유로 couple[i]도 대괄호를 씌워주어 리스트로 바꿔 주고 비교한다.
(같은 데이터 타입끼리 비교해야하므로)

+ 상쇄가능한 모든 괄호 쌍을 제거한 뒤의 리스트 안의 값 유무 판단

if open:                   
  return False

위의 과정에서 상쇄 시킬 수 있는 모든 조합들을 제거하고 난 뒤에도 open안에 열린 괄호가 남아 있을 수 있다.

열린 괄호가 남아 있다는 것은 쌍을 이루는 닫힌 괄호가 인자로 포함되지 않았다는 것을 뜻하므로 False를 반환해야 한다.

그러므로 열린 괄호를 담기로 한 open 이라는 리스트에 값이 있으면 False, 없으면 True를 반환하기로 하자.

총정리

def is_valid(string):
    couple = {
        ')' : '(',
        ']' : '[',
        '}' : '{'
    }

    open = []
    for i in string:
        if i in couple:
            if [couple[i]] == open[-1:]:   
                open.pop()
            else:
                return False
        else:
            open.append(i)
    if open:                     
        return False

    return True