76502: 괄호 회전하기

Link : https://programmers.co.kr/learn/courses/30/lessons/76502

---

1. 문제

• 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
  • (), [], {} 는 모두 올바른 괄호 문자열입니다.
  • 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
  • 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
  대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

---

2. 문제의 조건

• s의 길이는 1 이상 1,000 이하입니다.

 

---

3. 문제 접근

• 아이디어
  
  기본적으로 괄호검사는 Stack 자료구조를 이용하여 해결합니다. 그 후 옆으로 한칸씩 옮기면서 수행을 합니다.
  이때 저는 deque를 이용하였습니다. deque 자료구조는 [1, 2, 3, 4, 5] 가 있을 경우 1과 5 자리에 pop과 append를 동시에 O(1)에 해결할 수 있는 자료구조입니다. 범위가 작아서 리스트를 직접 pop후 0자리에 append해도 되지만 다양한 자료구조를 이용하고 싶어서 사용해보았습니다.

 

---

4. 풀이 방법

• 한칸을 먼저 shift 후 stack을 이용한 괄호검사를 진행합니다.
  - 괄호검사
  스택이 없으면 무조건 넣어줍니다.
  스택이 존재 할 경우 괄호문자인지 확인 후 마지막 괄호가 (이면서 지금 들어온 문자가 )이거나
  [이면서 ]이거나 {이면서 }일경우 stack을 pop해줍니다. 왜냐하면 이전 괄호가 (인데 )가 들어오면 맞는 괄호 짝이므로 들어온 )는 추가하지않고 (에 대해서만 pop해주면 되기때문입니다.
  스택이 비어있으면 정확하게 괄호검사가 된 것이므로 결과를 1 증가 시켜줍니다.

 

---

5. 소스코드

• https://cjw-git.tistory.com/168

 

---

 

cjw.git@gmail.com