문제:
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호 ("()") 와 대괄호 ("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
* 모든 왼쪽 소괄호는 ("(")는 오른쪽 소괄호(")")와만 짝을 이룰 수 있다.
* 모든 왼쪽 대괄호는 ("[")는 오른쪽 대괄호("]")와만 짝을 이룰 수 있다.
* 모든 오른쪽 괄호는 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
* 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
* 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
입력:
하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호 ("()") 대괄호("[]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.
입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.
출력:
각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.
풀이 방법:
처음에는 이와 비슷한 문제들은 ( , [ 를 만나면 count +=1 하고 ), ]를 만나면 count -=1 하는 방법으로 쉽게 풀 수 있어서 비슷한 문제인 줄 알았다. 하지만 예제 중에 5번째 줄인 ( [ ) ] 과 같은 케이스는 마지막 조건에 의해서 안된다는 것을 알게 되었다.
따라서 이 문제를 해결하기 위해서 stack이라는 배열을 만들어서 ( , [를 만나면 담고, ) ] 를 만나면 빼는 ( 예외 케이스 처리 하에) 방법으로 해서 통과를 했다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | while True: string=input() if string==".": break stack=[] answer=True for i in string: if i=='(': stack.append(i) elif i=='[': stack.append(i) elif i==')': if len(stack)==0: answer=False break if stack[-1]=='(': stack.pop() else: answer=False break elif i==']': if len(stack)==0: answer=False break if stack[-1]=='[': stack.pop() else: answer=False break if len(stack)==0 and answer: print("yes") else: print("no") | cs |
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1260. DFS와 BFS (0) | 2019.07.19 |
|---|---|
| [BOJ]2164. 카드2 (0) | 2019.07.18 |
| [BOJ]2004. 조합 0의 개수 (0) | 2019.07.16 |
| [BOJ]2217. 로프 (0) | 2019.07.15 |
| [BOJ]11047. 동전0 (0) | 2019.07.14 |