프로그래머스 괄호 회전하기
1. 문제 설명
괄호(소, 중 대)들로 이루어진 문자열이 주어진다. 그 문자열이 성립하는지 파악하면 되는 문제. 특이점은 그 문자열을 돌려가면서 성립하는 문자열의 개수를 세는 것.
2. 접근법 및 개선 방안
순차적으로 접근할 필요가 있는 문제이다.
1) 주어진 문자열의 괄호가 성립하는지 파악하는 방법 - 스택 자료구조 사용!
문자열의 괄호가 성립하는지는 스택 자료구조를 통해 파악할 수 있다. 괄호를 열고 닫았을 때, 그 안에 있는 괄호들은 올바르게 짝이 지어져 있어야 한다. 결국 중요한 것은 닫는 괄호이다. 만약 닫는 괄호가 나왔는데 그 이전에 나온 괄호들이 올바르게 짝 지어져 있지 않다면 그 문자열을 성립하지 않는 것이다.
순서를 요약해보면 다음과 같다.
- 여는 괄호라면 스택에 담는다.
- 닫는 괄호라면 스택에서 꺼내어 짝이 맞는지 확인한다.
- 만약에 짝이 맞지 않는다면 안에는 올바르게 짝지어지지 않은 괄호가 있다는 것이고 이는 올바르지 않은 문자열이라는 의미다.
다음과 같은 코드로 나타낼 수 있다.
// stack 클래스 대신 ArrayDeque!
val bracketString = "[](){}"
val stack = ArrayDeque<Char>()
for(bracket in bracketString){
// 여는 괄호라면...
if(bracket == '[' || bracket == '{' || bracket == '(' ){
stack.push(bracket)
} else {
// 닫는 괄호라면
if(stack.isEmpty()){
println("올바르지 않은 괄호")
} else {
// 짝이 맞는지 확인한다.
if(/*짝이 맞는지 판단하는 판단식*/){
// 짝이 맞다면...
stack.pop()
} else {
// 짝이 맞지 않는다면...
println("올바르지 않은 괄호")
}
}
}
}
2) 문자를 어떻게 돌릴 것인가? 과연 돌려야 하는 것인가?
간단하게는 첫 번째 요소를 마지막에 붙이면 될 문제다.삭제와 추가가 빈번하기 때문에 LinkedList로 구현하는 것이 유리할 것이다. 동작은 다음과 같다. 첫 번째 노드를 삭제한다. 삭제한 노드를 끝에 추가한다. 이렇게 문자열을 돌릴 수 있지만 느리다. 아래의 예시에서는 A를 삭제하고 D의 오른쪽으로 옮겨 문자열을 돌렸다.
발상을 전환하여 돌리지 않는 방법을 생각할 수도 있다. 돌리는 이유는 두 번째 요소를 첫 번째 요소로 만들기 위해서 이다. 결국 첫 번째 요소를 바꿔주기 위해서 돌리는 것이라고도 볼 수 있다. 그렇다면 첫 번째 요소를 나타내는 변수를 도입하여 이를 해결할 수 있을 것이다! 이 변수에는 첫 번째 요소의 index를 저장한다. 또한 검사하는 변수(일종의 포인터)를 도입하여 그 변수의 값이 첫 번째 요소의 index와 같을 때까지 1씩 더하길 반복하면 돌리는 것과 같은 효과를 낼 수 있다. 이 예시에선 전자를 startIdx로, 후자를 cutrrentIdx라는 이름의 변수로 만들었다. 우선 startIdx를 A에서 B로 옮긴다. currentIdx에 startIdx의 값을 저장한다. 이후 1씩 더하며 B -> C -> D -> A로 옮겨가면 문자를 돌린 것과 같은 효과를 낼 수 있다. 물론 D의 인덱스를 넘어가면 나머지 연산을 통해 A를 가리키게 한다.
3) 한번에 얼마만큼 돌릴 것인가?
과연 한 칸 씩 돌려야 할까? 그렇지 않다. 이를 정확히 하기 위해서는 언제 괄호가 성립하지 않는지 파악해야 한다. 우선 괄호가 틀린지 판단할 수 있는 것은 닫는 괄호 뿐이다. 열린 괄호는 어디에나 존재할 수 있다. 예를 들어, 그 괄호 다음에 짝이 맞는 괄호가 오면 완전한 괄호가 되기 때문이다. 결국 틀린지 판단할 수 있는 괄호는 닫는 괄호이다. 또한 이전에 온전한 괄호쌍이 있었다면 startIdx를 한 칸 움직이는 불완전한 괄호가 되어버린다. 온전한 괄호는 0개 이상의 괄호가 완성되었을 때를 의미한다.
닫는 괄호는 2가지 상황에서 틀린 괄호가 된다. ① 스택이 비어있는 상황이다. ② 스택에 괄호가 있지만 그 괄호가 닫는 괄호와 짝이 맞지 않는 상황이다. 이를 그림으로 표현해보면 다음과 같다. 주황색은 startIdx를, 파란색은 currentIdx를 의미한다. 첫 번째 경우는 온전한 괄호 뒤에 닫는 괄호가 등장한다. 스택이 비어있다는 것은 이전에 currentIdx가 거친 괄호들이 온전한 괄호를 형성했다는 것을 의미한다. startIdx를 문제의 닫는 괄호( 3번 ) 이전의 어디로 움직여도 문제의 닫는 괄호 때문에 온전한 괄호가 되지 못한다. 그렇기에 startIdx를 4번으로 옮겨서 다시 검사해야 한다. 두 번째 상황은 짝이 맞지 않는 괄호 사이에 온전한 괄호가 있는 상황이다. 어떤 괄호들이 스택에서 만났다는 것은 그 사이에는 온전한 괄호가 있었다는 것을 의미한다. 그렇기에 startIdx를 6번 이전의 어느 괄호로 옮겨도 6번 괄호 때문에 실패하고 만다. 그렇기에 7번으로 startIdx를 옮겨야 한다.
4) map을 이용해 짝을 짓는 방법
조건식으로 일일이 닫는 괄호와 짝이 맞는 열린 괄호인지 파악할 수 있습니다. 하지만 코드가 길어지고 가독성이 떨어져 다른 방법을 모색해볼 필요가 있습니다. Map을 통해 구현하는 것이 대안이 될 수 있습니다. key를 열린 괄호로 두고, 그에 해당하는 value를 짝에 맞는 닫는 괄호로 두는 것입니다. 이렇게 하면, contains 함수를 통해 열린 괄호인지 여부를 판단할 수 있을 뿐만 아니라 key로 열린 괄호를 전달하여 그와 짝이 맞는 괄호인지 판단할 수 있습니다.
val pairMap = mapOf('(' to ')','[' to ']','{' to '}')
3. 코드
import java.util.*
class Solution {
fun solution(s: String): Int {
val pairMap = mapOf('(' to ')','[' to ']','{' to '}')
val stack = ArrayDeque<Char>()
var answer = 0
// 괄호의 개수가 홀수면 맞는 괄호일 수 없음
if(s.length % 2 != 0){
return 0
}
// 살펴볼 index를 의미
var currentIdx = 0
// 살펴보기 시작한 index를 의미
var startIdx = 0
// currentIdx가 s.length보다 크면 다 돌았다는 뜻
// currentIdx가 startIdx보다 작으면 그 사이에 만들 수 있는 괄호가 없음
while(currentIdx < s.length && currentIdx >= startIdx){
// 시작 지점 저장
startIdx = currentIdx
// 괄호가 성립하는지 판단하는 방법
while(true){
// s[currentIdx]가 여는 괄호인지?
if(pairMap.contains(s[currentIdx])){
stack.push(s[currentIdx])
} else {
// s[currentIdx]가 닫는 괄호!
if(stack.isEmpty()){
break
} else {
// stack의 가장 위에 있는 여는 괄호에 맞는 닫는 괄호인지?
if(pairMap[stack.peek()]!! == s[currentIdx]){
stack.pop()
} else {
break
}
}
}
currentIdx ++
currentIdx %= s.length
// 한 바퀴를 돌았다는 것을 의미
if(currentIdx == startIdx){
answer++
break
}
}
stack.clear()
currentIdx++
}
return answer
}
}
댓글남기기