백준 4949번 - 균형잡힌 세상 / Go

문제: https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

문제 설명

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

예제 입력 1 복사

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

예제 출력 1 복사

yes
yes
no
no
no
yes
yes

힌트

7번째의 " ."와 같이 괄호가 하나도 없는 경우도 균형잡힌 문자열로 간주할 수 있다.

 

---

정답

package main

import (
	"bufio"
	"fmt"
	"os"
	"testing"
	"unicode"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	for {
		scanner.Scan()
		str := scanner.Text()
		if str == "." {
			break
		}
		fmt.Println(solution4949(str))
	}
}

func solution4949(str string) (result string) {
	stack := []string{}
	pairBracket := map[string]string{
		")": "(",
		"}": "{",
		"]": "[",
	}

	for _, i32 := range str {
		if unicode.IsLetter(i32) || " " == string(i32) || "." == string(i32) {
			continue
		}

		s := string(i32)
		if pair, ok := pairBracket[s]; ok {
			if len(stack) == 0 {
				return "no"
			}
			if pair == stack[len(stack)-1] {
				stack = stack[:len(stack)-1]
			} else {
				return "no"
			}
		} else {
			stack = append(stack, s)
		}
	}

	if len(stack) > 0 {
		return "no"
	}

	return "yes"
}

func Benchmark4949(b *testing.B) {
	for i := 0; i < b.N; i++ {
		solution4949("So when I die (the [first] I will see in (heaven) is a score list).")
	}
}

func Test_solution4949(t *testing.T) {
	type args struct {
		str string
	}
	tests := []struct {
		name       string
		args       args
		wantResult string
	}{
		{name: "", args: args{str: "So when I die (the [first] I will see in (heaven) is a score list)."}, wantResult: "yes"},
		{name: "", args: args{str: "[ first in ] ( first out )."}, wantResult: "yes"},
		{name: "", args: args{str: "Half Moon tonight (At least it is better than no Moon at all]."}, wantResult: "no"},
		{name: "", args: args{str: "A rope may form )( a trail in a maze."}, wantResult: "no"},
		{name: "", args: args{str: "Help( I[m being held prisoner in a fortune cookie factory)].\n"}, wantResult: "no"},
		{name: "", args: args{str: "([ (([( [ ] ) ( ) (( ))] )) ])."}, wantResult: "yes"},
		{name: "", args: args{str: " ."}, wantResult: "yes"},
		{name: "", args: args{str: "("}, wantResult: "no"},
		{name: "", args: args{str: "["}, wantResult: "no"},
		{name: "", args: args{str: ")"}, wantResult: "no"},
		{name: "", args: args{str: "]"}, wantResult: "no"},
		{name: "", args: args{str: "]"}, wantResult: "no"},
		{name: "", args: args{str: "(((("}, wantResult: "no"},
		{name: "", args: args{str: "([)"}, wantResult: "no"},
		{name: "", args: args{str: ".."}, wantResult: "yes"},
		{name: "", args: args{str: "([)]"}, wantResult: "no"},
		{name: "", args: args{str: "(])]"}, wantResult: "no"},
		{name: "", args: args{str: "())"}, wantResult: "no"},
		{name: "", args: args{str: "a"}, wantResult: "yes"},
		{name: "", args: args{str: "(( [[ ]) ])"}, wantResult: "no"},
		{name: "", args: args{str: "[(()])."}, wantResult: "no"},
		{name: "", args: args{str: "t [least it is b[etter than no Moon at all]"}, wantResult: "no"},
		{name: "", args: args{str: "[least it is b[etter than no Moon at all]"}, wantResult: "no"},
		{name: "", args: args{str: "Half Moon tonight (At least it is better than no Moon at all]."}, wantResult: "no"},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if gotResult := solution4949(tt.args.str); gotResult != tt.wantResult {
				t.Errorf("solution4949() = %v, want %v", gotResult, tt.wantResult)
			}
		})
	}
}

 

---

풀이

 파이썬으로 했으면 금방 풀었을 문제인데, Go로 문제를 풀려니까 엄청 오래 걸린 문제였습니다. 시간도 순위권의 경우 8ms인데, 이 풀이는 168ms로 차이가 매우 많이 납니다.

 

 이 문제는 유명한 스택을 이용한 괄호 확인 문제입니다. 스택에 괄호를 넣고 비교하면서 올바른 괄호 문자열인지 확인하면 됩니다. 

 

 닫는 괄호만 확인하면서 앞의 괄호와 짝 괄호인지 확인하고, 아니면 "no"를 리턴하면 됩니다.