24-06-23 알고리즘 문제 풀이

오늘도 코드를 더 작성해보면서 시간을 보내기 보다는 이론적인 부분에 대해서 조금 더 찾아보면서 시간을 보냈던 것 같다. 네트워크 쪽 지식에 대해서는 앞으로도 매일매일 더 찾아보게 될 것 같다.

 

여기에는 오늘 풀어 본 알고리즘 문제 하나를 정리해본다.

 

1. 알고리즘 문제 풀이

오늘은 프로그래머스에 있는 '괄호 회전하기' 문제를 풀어보았다.

 

1-1. 풀어본 문제

[문제]

 

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB도 올바른 괄호 문자열입니다. 예를 들어, {}와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 <= x (s의 길이))칸 만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

- 제한 사항

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

- 입출력 예

s	result
"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

 

- 입출력 예 설명

 

입출력 예 #1

• 다음 표는 "[](){}"를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"[](){}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}[]()"	O
5	"}[](){"	X

• 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

 

입출력 예 #2

• 다음 표는 "}]()[{"를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"}]()[{"	X
1	"]()[{}"	X
2	"()[{}]"	O
3	")[{}]("	X
4	"[{}]()"	O
5	"{}]()["	X

• 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

 

1-2. 문제 풀이

사실 이 문제는 이전에 풀어보려다가 도무지 감이 안와서 제쳐두었던 문제였다. 알고리즘 문제 풀이를 이제는 충분히 연습해왔기 때문에 이제는 다시 풀면 풀 수 있을 것 같다는 생각이 들어서 다시 풀어보게 되었다.

 

스택, 큐 개념은 알았지만 문제 풀이에 어떻게 활용할지 잘 몰랐던 때가 있었는데 이제는 어떻게 활용하는지 어느정도 알게 되어서 문제를 수월하게 풀어낼 수 있었다.

 

먼저 주어진 문자열 s를 회전시키는 것 부터 해결해야했다. 간단히 될 줄 알았는데 생각보다 시간이 좀 걸렸다. 이중 반복문을 이용해야한다는 것 까진 알았는데 내부에서 반복을 어떻게 돌려야하나 고민했는데 나머지 연산을 이용해서 쉽게 해결할 수 있었다.

 

아래와 같이 이중 반복문을 이용해 문자를 하나하나 스택에 저장하는 것 까지는 해결할 수 있었다.

fun main() {

    val s = "[](){}"

    for (i in s.indices) {
        val stack = ArrayDeque<Char>()

        for (j in s.indices) {
            // (i+j)를 s의 길이로 나눈 나머지의 인덱스에 해당하는 문자
            val char = s[(i+j)%s.length]

            stack.add(char)
        }
        println(stack.joinToString(""))
    }

    // - 실행 결과 -
    // {}()[]
    // }()[]{
    // ()[]{}
    // )[]{}(
    // []{}()
    // ]{}()[
}

그런 다음 이제 만들어진 문자열이 올바른 괄호 문자열인지를 판단해야하는 문제만 남았다.

 

스택일 이용하면 이것은 쉽게 해결할 수 있다. 스택이 비어있으면 현재 문자를 스택에 채워넣고, 스택이 비어있지 않다면 스택의 마지막 요소와 현재 요소가 짝을 이룬다면 스택의 마지막 요소를 제거한다. 이 둘에 해당하지 않는 경우도 스택에 현재 요소를 채워넣는다.

 

가장 먼저 스택이 비어있는지 여부를 확인하는 이유는 stack.last()에서 예외(NoSuchElementException)가 발생할 수 있기 때문이다. (또는 lastOrNull() 함수를 이용할 수도 있다.)

 

최종적으로 작성된 코드는 아래와 같다.

class Solution {
    fun solution(s: String): Int {
        var answer = 0
        
        // 짝을 리스트에 저장해두기
        val pairList = listOf('[' to ']','{' to '}','(' to ')')
        
        
        for (i in s.indices) {
            val stack = ArrayDeque<Char>()
            
            for (j in s.indices) {
                val char = s[(i+j)%s.length]
                
                // 스택이 비어있으면 채워넣는다
                if (stack.isEmpty()){
                    stack.add(char)
                // 스택의 마지막 요소와 현재 요소가 짝을 이루면 마지막 요소를 스택에서 제거한다
                } else if (stack.last() to char in pairList) {
                    stack.removeLast()
                // 위 둘에 해당하지 않으면 스택에 더한다
                } else {
                    stack.add(char)
                }   
            }
            // 최종적으로 스택이 비어있으면 답을 1 증가시킨다
            if (queue.isEmpty()) answer++
        }
        
        return answer
    }
}

위와 같이 답을 작성했더니 답으로 잘 통과되었다.

 

이것 보다 조금 더 효율적인 코드를 작성할 수도 있었을 것 같긴한데 일단 이전에 시도했다가 포기했던 문제를 어렵지 않게 풀어냈다라는 점에서 아주 만족스러웠다.

 

스택, 큐 자료구조에 대해서 익숙해지도록 더 연습해보아야겠다.

 

2. 오늘 배운 것

- 물리 계층, 데이터 링크 계층과 같이 아주 기초적인 부분부터 네트워크에 대해 조금 공부해보았다.