1015: 괄호 짝

Link : judge.koreatech.ac.kr/problem.php?id=1015

---

1. 문제

• 괄호마을의 우두머리 리습은 최근 골치를 썩고 있습니다. 원래 (, ) 밖에 살지 않던 마을이였는데 살다보니 {, }, [, ] 들이 추가가 되면서 관리를 하기 너무 복잡해 진 것이죠.
  사람이 늘다보니 질서가 너무 어지럽혀 졌습니다. 본디 괄호란 서로 짝이 어울리는 위치에 있어야 하는데 말이죠.
  리습의 골치를 해결해 주기 위해 나열된 괄호를 보고 올바른 짝이 맞는지 아닌지 판단하여 알려주세요.

 

---

2. 문제의 조건

• n <= 1000 (n : 괄호 길이)

 

---

3. 문제 접근

• 시간 복잡도
  
  시간 제한 1초의 n의 길이는 1000이하이므로 O(N^2.66) 이내의 시간으로 풀면 될 것 같습니다.
  
  
  
• 아이디어
  
  해당 문제는 전형적인 자료구조의 "Stack" LIFO(Last Input First Output) 을 떠올리게 하였습니다.
  기본적으로 스택의 시간복잡도는 O(N)에 해당하므로 해당 문제를 수월하게 풀 수 있습니다.

 

---

4. 풀이 방법

• 만약 괄호가 '(', '{', '[' 과 같은 열리는 형태라면 스택에 넣고 ')', '}', ']'과 같은 닫히는 형태라면 마지막 원소를 추출 한 뒤 비교하시면 됩니다.

 

---

5. 소스코드

• cjw-git.tistory.com/22

 

---

 

cjw.git@gmail.com