[코테] 올바른 괄호

문제링크

프로그래머스

<로직 고민/>

• 음 "("은 +1 ")"은 -1 값을 줘서 문자열을 +1 -1 이런 식으로 치환했을 때 0이 나오면 true, 그 외의 값이 나오면 false 이렇게 하면 어떨까
• 그럼 일단 문자열을 for문으로 돌려서 인덱스 값마다 하나씩 봐야겠네

def solution(s):
    sum_p = 0
    if s[0] == ")":
        return False
    for p in s:
        if p == "(":
            sum_p += 1
        else:
            sum_p -= 1
    if sum_p == 0:
        return True
    else:
        return False

• 이렇게 했을 때 예시 문제는 다 통과하긴 하는데
• "())(()" 이런 경우엔 값이 제대로 나오지 않는다
• 음..일단 조건을 더 추가했다
• for문이 돌다가 sum_p가 -1이 된다는 건 여는 괄호 없이 닫는 괄호가 먼저 나왔다는 뜻이므로 false를 return 하는 코드를 추가했다
• 그리고 또 뭐가 있는지는 모르겠지만 일단 "())(()"은 통과하길래 채점을 했는데 통과했다..! 5점..!
• 이 문제는 다른 사람 풀이가 꽤나 궁금하다 어떻게 풀어야 좋은 풀이였을까....

---

<완성된 풀이/>

def solution(s):
    sum_p = 0
    # ")"로 시작하거나 "("로 끝나는 경우 false
    if s[0] == ")" and s[-1] == "(":
        return False
    
    for p in s:
        if p == "(":
            sum_p += 1
        else:
            sum_p -= 1
        # for문이 돌다가 sum_p가 -1이 되면 false
        if sum_p == -1:
            return False
        
    # for문이 다 돌고 sum_p가 0이면 true, 그 외 값은 false
    if sum_p == 0:
        return True
    else:
        return False

---

<다른 사람 풀이/>

- 천재풀이1

def solution(s):
    pair = 0
    for x in s:
        if pair < 0: break
        pair = pair + 1 if x == "(" else pair - 1 if x == ")" else pair
    return pair == 0

• 4번째 if문은 내 코드의 13,14번째 줄이군
• 5번째 줄은 x가 "("이면 pair에 1을 더하고, ")"이면 1을 빼고 둘 다 아니면 pair 그대로...?
• 그대로 부분이 헷갈려서 댓글 보니까 if x == ")" else pair는 불필요하다고 한다
• 문자열 s에는 괄호만 있어서 "("이면 1을 더하고 아니면 1을 빼면 되니까 수정하면 아래와 같다

def solution(s):
    pair = 0
    for x in s:
        if pair < 0: break
        pair = pair + 1 if x == "(" else pair - 1
    return pair == 0

---

- 천재풀이2

def solution(s):
    st = list()
    for c in s:
        if c == '(':
            st.append(c)

        if c == ')':
            try:
                st.pop()
            except IndexError:
                return False

    return len(st) == 0

• 뭔가 이 풀이가 이 문제의 정답같다
• 여는 괄호와 닫는 괄호가 순서에 맞게 나오면 st 리스트에 아무것도 없을 테니 여는 괄호 없이 닫는 괄호가 나오면 index error가 뜬다 그럼 false 반환
• 그리고 여는 괄호와 닫는 괄호가 순서에 맞게 둘 다 잘 있으면 st 리스트는 빈 리스트가 될 것이니 true 반환, 여는 괄호가 더 있다면 빈 리스트가 아니니까 false 반환
• 아주 좋은 풀이인 거 같군!!

---

<수정/>

def solution(s):
    sum_p = 0
    for p in s:
        if p == "(":
            sum_p += 1
        else:
            sum_p -= 1
        # for문이 돌다가 sum_p가 -1이 되면 false
        if sum_p == -1: break

    # for문이 다 돌고 sum_p가 0이면 true, 그 외 값은 false
    return sum_p == 0

• 다른 두 풀이를 보니까 내 코드의 17~20번째 줄을 return sum_p == 0 으로 하면 되는 거였구나 하고 깨달았다!
• 이렇게 또 새로운 걸 배워가는구만! (사실 전에 이런 거 본 적 있어서 알긴 했는데 생각해내지 못했다,,ㅎㅎ)
• 그리고 13번째 줄은 천재풀이1의 4번째 줄을 보고 나도 이렇게 하면 되겠구나 싶어서 수정했다!
• 이렇게 수정하니까 효율성 테스트에서 코드 실행시간이 처음 풀이보다 1~2ms 정도 단축됐다(근데 왜지? 원래 코드는 if문에서 바로 return하는 거고, 바꾼 건 for문을 나간 다음 최종 return에서 sum_p가 0이 아닌 것을 또 확인하고 false가 반환되는 건데...?!)
• 그리고 원래 코드에 있던 4,5번째 줄을 지워도 채점이 되길래 지웠다
• 4,5번째 줄을 지우니까 효율성 테스트도 6ms대가 나온다