Assignment 1 - check_brackets

Assignment 1 - check_brackets

이번 Week 1에서 배운내용을 토대로 프로그래밍 과제를 풀었다.
총 4개의 문항이며 이 중 2개만 풀면 Pass된다.

우선 Check Brackets이라는 과제에 대한 설명을 보면 괄호의 짝이 맞는지 확인하는 것이 주된 업무이다. (가 있다면 그 뒤 )가 있어야 하고 [가 있다면 ]로 짝을 맞춰야하는 것이다. 짝이 맞다면 Success를 출력, 그 이외에는 짝이 맞지않는 무리 중 가장 마지막 괄호의 index를 반환해야한다.

그 뒤의 샘플들이 나오고 이에 대한 예상 출력을 보여준다.

강의 시간에 설명했던 IsBalanced 함수의 알고리즘을 변형하면 더 접근하기 쉬울 수 있다고 한다.

# python3
from collections import namedtuple

Bracket = namedtuple("Bracket", ["char", "position"])


def are_matching(left, right):
    return (left + right) in ["()", "[]", "{}"]


def find_mismatch(text):
    opening_brackets_stack = []
    for i, next in enumerate(text):
        if next in "([{":
            # Process opening bracket, write your code here            pass
        if next in ")]}":
            # Process closing bracket, write your code here            pass

def main():
    text = input()
    mismatch = find_mismatch(text)
    # Printing answer, write your code here

if __name__ == "__main__":
    main()

우선 과제를 열어보면 위와 같이 초기 구성이 이루어져 있는 것을 볼 수 있다.
5줄의 namedtuple이 어떤역할인지 몰랐지만 찾아보니 Braket이라는 데이터타입을 형성해주는 것을 알았다. 따라서 [문자, 위치]를 저장하기에 아주 적합한 형식.

are_matching이라는 함수는 이미 완성되어 짝이 맞는지 여부만 확인해주고 find_mismatch 함수를 수정하여 짝이 맞지 않는 부분을 확인하는 기능을 완성해본다.

# python3
from collections import namedtuple

Bracket = namedtuple("Bracket", ["char", "position"])


def are_matching(left, right):
    return (left + right) in ["()", "[]", "{}"]


def find_mismatch(text):
    opening_brackets_stack = []
    for i, next in enumerate(text):
        if next in "([{":
            # Process opening bracket, write your code here            

            opening_brackets_stack.append(Bracket(next, i))

        if next in ")]}":
            # Process closing bracket, write your code here            
            opening_brackets_stack.append(Bracket(next, i))
br = list(zip(*opening_brackets_stack))

        if br == []:
            pass        

        elif len(br[0]) >= 2:
            for j in (range(len(br[0]) - 1)):
                tf = are_matching(br[0][j], br[0][j+1])
                if tf is True:
                    del opening_brackets_stack[j+1]
                    del opening_brackets_stack[j]

    return opening_brackets_stack


def main():
    text = input()
    mismatch = find_mismatch(text)
    # Printing answer, write your code here    

    if mismatch == []:
        print('Success')
    else:
        print(int(mismatch[-1][1]) + 1)

if __name__ == "__main__":
    main()

우여곡절끝에 완성한 코드. 간결하지 않을 수도 있겠으나 일단 동작은 하니.... 이로써 check_bracket 문제를 해결.

우선 구성한 find_mismatch 함수를 보자면 text인자를 받아 인덱스와 한문자씩 받아온다.(enumerate) 이 후 해당 글자가 "({[)}]" 중 하나에 속한다면 opening_brackets_stack 리스트에 담고 해당 리스트를 zip을 활용하여 인덱스와 문자별로 재분류하여 br에 담는다.

이 후 br이 빈 리스트가 아니라면 길이가 2 이상일 때에 for문으로 접근한다. br 리스트 내에 있는 문자를 한쌍씩 are_matching함수를 통해 비교하교 True가 반환되면 해당 문자 두개를 지운다. (j번째가 아닌 j+1번째를 먼저 지워야하는 부분에서 약간 혼란스러웠다)

이제 main함수에서는 input을 text에 저장한 뒤 mismatch를 통해 빈리스트가 반환되는지 아니라면 리스트 내 마지막 인덱스를 반환하도록 하면 끝!

추가 수정 및 보완

과제를 약간 잘못이해한 것인지 마지막 괄호의 인덱스를 반환하는 것이 아닌 처음으로 잘못 매칭한 괄호의 인덱스를 반환해야 했었다.

따라서 아래와 같이 더 간단한 코드로 수정할 수 있었다.

# python3
from collections import namedtuple

Bracket = namedtuple("Bracket", ["char", "position"])


def are_matching(left, right):
    return (left + right) in ["()", "[]", "{}"]


def find_mismatch(text):
    opening_brackets_stack = []
    r = []
    for i, next in enumerate(text):
        if next in "([{":
            # Process opening bracket, write your code here            opening_brackets_stack.append(Bracket(next, i))

        if next in ")]}":
            # Process closing bracket, write your code here            if not opening_brackets_stack:
                opening_brackets_stack.append(Bracket(next, i))
                break
            else:
                if are_matching(opening_brackets_stack[-1][0], next) is True:
                    del opening_brackets_stack[-1]
                else:
                    opening_brackets_stack.append(Bracket(next, i))
                    break
    return opening_brackets_stack

def main():
    text = input()
    mismatch = find_mismatch(text)
    # Printing answer, write your code here    if not mismatch:
        print('Success')
    else:
        print(int(mismatch[-1][1]) + 1)


if __name__ == "__main__":
    main()

괄호를 여는 족족 opening_brackets_stack에 추가시키고 닫는 괄호의 경우 케이스에 맞게 매칭이 되면 이전 여는 괄호와 함께 삭제해주고 아니라면 해당 괄호를 Bracket 타입을 opening_brackets_stack에 추가하여 반복문을 빠져나온다.

그럼 main함수에서 mismatch가 비어있는 상태면 Success, 아니면 인덱스를 반환하게 된다!