Baekjoon 문제 풀기 (4949번 : 균형잡힌 세상) Python

4949번 : 균형잡힌 세상

1. 문제읽기

---

괄호들이 짝이 맞는지 확인하기

입력값을 받는 것부터 이해가 힘들었다.
예제 문제가 전부 마지막에 온점(.)이 붙어있어서 처음에는 문장 마지막에 .이 있어야 종료가 된다는 것으로 이해했다.
몇번 문제를 읽어보다가 제대로 이해했다. 그냥 마지막 입력 줄에 . 하나만 입력됐을 경우 입력을 종료하는 것이였다.

그리고 길이가 100글자로 제한되어있어서 완전탐색 문제인가 해서 조건문으로 열심히 풀려고도 해봤다.
pop을 써볼까 생각은 했는데, 결과적으로 풀지 못한 이유는 조건을 어떻게 구현해야 할지 몰랐던 것이 가장 큰 것 같고, 그 과정에서 stack을 써야한다는 생각을 하지 못한 것이다.

2. 제출 코드

---

제출하지 못한 코드이다.

문제의 조건을 구현하기 위한 방법은 총 2개이다.

1. 여는 괄호와 닫는 괄호가 다른 경우
2. 짝이 맞지 않는 경우

두 경우를 모두 고려하는 방법을 구현하는 것이 너무 어려웠다.
그래서 포기하고 정답 코드를 보았다.
다시보니 입력값을 받는 것부터 잘못되었음을 알 수 있었다…

import sys
arr = []
tgt_s = ["(", "["]
tgt_e = [")", "]"]
tgt_a = ["(", "[", ")", "]"]
while 1:
    input = sys.stdin.readline().strip()
    if input == ".":
        break
    arr.append(input)


def func(arr):
    tgt_arr = []
    for j in range(len(arr)):
        for i in range(len(arr[j])):
            if arr[j][i] in tgt_e:
                tgt_arr.append(arr[j][i])
            elif arr[j][i] in tgt_s:
                tgt_arr.append(arr[j][i])
    return tgt_arr

def isEven(arr):
    if arr[0] in tgt_e:
        return "no"
    while 1:
        for i in range(len(arr)):
            for j in range(i+1, len(arr)-1):
                if arr[i] == "(":
                    arr[j] == ")"
                elif arr[i] == "[":


print(func(arr))
print(isEven(func(arr)))

3. 공부할 것

---

1) 입력값 받기

내 코드는 입력값을 문자열로 받아 리스트로 만든 문자열 리스트였다. 그러나 그렇게하면 이중포문을 써야해서 쉽지 않았다.
정답 코드는 무한반복문으로 문자열을 한개씩 받아 처리한 뒤, 종료 조건을 만나면 종료한다. 한 반복에 한 문자열을 처리할 수 있다.

2) 구현 하기

내 코드는 문자열에서 괄호를 따로 빼온 리스트에서 출발했다.
정답 코드도 괄호를 따로 빼는 건 마찬가지지만, 새로운 리스트에 저장하는 것은 시작 괄호만이다. 닫는 괄호를 if문으로 캐치하면 pop을 해서 짝을 맞춰 없애준다.
stack 리스트가 비어있는지 비어있지 않은지도 중요한 부분인데, 예를 들어 비어있는데 닫는 괄호를 만난다면 바로 no가 되버리는 것이다.

3) 조건 두개 맞추기

문제의 조건을 구현하기 위한 방법은 총 2개이다.
아래 정답코드 두개를 모두 참고하여 정리하면 아래와 같다.

1. 여는 괄호와 닫는 괄호가 다른 경우 ex) [ ) ( )
   • 정답코드 1: true_flag로 구현
   • 정답코드 2: 리스트에 추가
2. 짝이 맞지 않는 경우 ex) [ ] (
   • 정답코드 1: stack 의 길이
   • 정답코드 2: 리스트에 추가
3. 판별하기
   • 정답코드 1: true_flag가 true 이고, stack의 길이가 0이면 yes다.
   • 정답코드 2: 리스트의 길이가 0이면 yes다.

괄호는 잘 맞는데 짝이 안맞거나, 짝은 잘 맞는데 괄호가 맞지 않거나의 경우가 있으므로 조건은 두개를 달아줘야한다.
첫번째 코드는 flag과 stack의 길이로 각각 나타냈다.
두번째 코드는 맞는 괄호일 때는 지워서 없애버리고, 맞지 않으면 그냥 맞지 않는 괄호를 append해서 길이를 늘려버렸다. 결과적으로 길이가 0이 아니면 no를 출력하게 되는 것이다.

뭔가 간단한 것 같은 문제였는데 풀이 해석도 그렇고 생각할게 엄청 많았던 문제였다.
stack을 사용한다는 접근도 어려웠고, 구현도 어려웠던 문제였다.
개인적으로 실버 4 문제가 아닌 것 같았다….
역시나 아직 익숙하지 않아서 그런거겠지…? ^.ㅠ…

정답 코드 1

import sys

input = sys.stdin.readline

while 1:
    string = input().rstrip()
    stack = []
    true_flag = 1

    for cha in string:
        if cha == '(' or cha == '[':
            stack.append(cha)
        elif cha == ')':
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                true_flag = 0
                break
        elif cha == ']':
            if stack and stack[-1] == '[':
                stack.pop()
            else:
                true_flag = 0
                break

    if string == '.':
        break

    if true_flag and not stack:
        print("yes")
    else:
        print("no")

정답 코드 2

while True :
    a = input()
    stack = []

    if a == "." :
        break

    for i in a :
        if i == '[' or i == '(' :
            stack.append(i)
        elif i == ']' :
            if len(stack) != 0 and stack[-1] == '[' :
                stack.pop() # 맞으면 지워서 stack을 비워준다.
            else : 
                stack.append(']')
                break
        elif i == ')' :
            if len(stack) != 0 and stack[-1] == '(' :
                stack.pop()
            else :
                stack.append(')')
                break
    if len(stack) == 0 :
        print('yes')
    else :
        print('no')