Grind 75: Valid Parentheses

[0tak2]

Valid Parentheses

[0tak2]

아이디어

여는 기호라면 스택에 넣고, 닫는 기호라면 스택을 peek해서 짝이 맞는 기호인지 확인 후 pop

구현

go의 표준 라이브러리 중 Stack은 없어서 그냥 List를 사용

List가 링크드 리스트로 구현되어 있어서 굳이 선택한건데 그냥 slice 쓰는게 빠르다는 얘기도 있음. slice는 go에서 제공하는 가변 길이 시퀀스 타입

slice로 하는게 타이핑 양도 줄일 수 있었을 듯

답안

// 0ms, 4.57MB

import "container/list"

var st *list.List

func handleChar(s rune) bool {
    if s == '(' || s == '[' || s == '{' {
        st.PushBack(s)
        return true
    }

    lastEl := st.Back()
    if lastEl == nil {
        return false
    }
    lastChar := lastEl.Value.(rune)

        // todo: 짝을 맞추느라 반복된 if문
    if s == ')' && lastChar == '(' {
        st.Remove(lastEl)
        return true
    }

    if s == ']' && lastChar == '[' {
        st.Remove(lastEl)
        return true
    }

    if s == '}' && lastChar == '{' {
        st.Remove(lastEl)
        return true
    }

    return false
}

func isValid(s string) bool {
    if len(s) < 2 {
        return false
    }

    st = list.New()

    for _, c := range s {
        if !handleChar(c) {
            return false
        }
    }

    if st.Len() > 0 {
        return false
    }

    return true
}