Swift 알고리즘, 백준 1662 압축 스택 문제풀이

 

 

 

 

안녕하세요? Developer, 멍구입니다.

오늘은 백준 알고리즘 문제 1662번, 압축을 swift로 풀어보도록 하겠습니다~ 🤗

 

---

백준 1662 압축

1662번: 압축

백준 1662번, 압축문제는 solved.ac기준, 실버1의 난이도로 명시되어 있습니다.
압축 문제는 과연 어떤문제일까요? 이어서 문제 내용을 보겠습니다. 

 

 

압축 알고리즘 문제는 압출되지 않은 하나의 문제열, S가 주어졌을때 해당 문자열을 K(Q)의 부분문자열 형태를 조건에 따라 압축을 하고, 결과적으로 압축을 거듭한 뒤의 문자열 길이를 구하는 문제입니다.

여기서 K(Q)에 대해서 살펴보자면, K는 한자리 정수, Q는 0자리 이상의 문자열입니다.

즉, 23(66) 은 3(66)의 부분문자열을 갖습니다. 이는 "66" 문자열이 3번 있는 것을 의미합니다. 즉 23(66) -> 2666666이 됩니다. 66이 세번 들어가게 되면서 문자열이 길어진 것이죠.

 

 

 

---

문제 입출력

 

문자열은 최대 50의 길이를 갖습니다. 또한 문자열의 길이는 Int 범위라고 합니다. 즉, 21억 이하의 길이를 갖고 있다고 하는 것이지요. 해당 문제는 괄호의 응용문제입니다. 보통 괄호가 나온다면 재귀, 스택문제과 관련 깊을 가능성이 큽니다. 

해당 문제는 말 그대로 압축을 풀고 문자열을 나열하면 메모리초과를 면하기 힘듭니다. 21억개의 문자열길이를 가질 수도 있기 때문이죠. 
그렇다면 지금부터 스택 원리를 활용해서 해당 문제를 풀어보도록 하겠습니다. 

해당 문제는 스택의 깊이를 인덱스로 참고하여 규칙에 따라 문제를 접근, 연산해가면 비교적 쉽게 풀 수 있는 문제입니다.

 

 

---

Swift 알고리즘 문제풀이

스위프트 풀이를 시작해보겠습니다.

먼저 입력 및 준비하는 부분을 보겠니다. 여기에서 S는 문자열을 받아 저장합니다.
각각의 변수, 상수에 대한 역할을 정리해 보겠습니다.

- S : 문자열을 입력받아 저장
- idx : 스택의 깊이(인덱스 용)를 판단하는 변수
- G : 각 스택의 깊이 별 문자열을 저장하기 위한 Character 변수, 인덱스 별 [Character] 배열이 필요하므로 2차원으로 정의됩니다. 총 문자열 길이는 50이지만 넉넉하게 101로 크기를 지정해도 메모리 부담은 없습니다.
- V : 각 괄호 깊이(스택 깊이) 별 연산된 문자열의 길이를 기록합니다. 

해당 문제는 스택의 원리를 활용할 수 있습니다.
- "(" 괄호가 들어오면 깊이, index는 증가합니다.
- ")" 괄호의 경우에는 반대로 깊이, index가 감소합니다. 감소할 때는 K(Q)의 조건에 따라 문자열을 복사해주어야합니다. idx(스택 깊이)를 감소 시킴과 동시에 이때의 길이를 V[idx]에 반복 된 문자열의 연산된 길이를 기록합니다.
- 그 외의 경우 각각의 깊이 별 문자를 G 배열에 기록합니다.

이제 핵심적인 알고리즘 Swift 구현코드를 이어서 보겠습니다. 

 

 

 

먼저 S의 계수범위를 indices를 통해 지정하고 S 문자열을 순회하는 모습입니다. 제가 달아 둔 주석을 읽으며 설명을 들으시는 것을 추천드립니다.

여기서 요점으로 보아야 할 규칙은 아래와 같습니다.

- 현재 순회중인 문자가 숫자라면 해당 숫자를 현재 깊이의 G[idx] 에 누적시킵니다.
해당 문자는 K(Q)의 K 정수를 판단하는데 사용됩니다. 

- 현재 순회중인 문자가 "(" 라면 idx(스택 깊이)를 증가시깁니다. 
idx는 각각의 스택 깊이 별 문자열을 기록하고, 반복 문자열의 길이를 연산해서 누적할 때 인덱스로 사용됩니다.

- 현재 순회중인 문자가 ")"라면 idx(스택 깊이)를 감소시킵니다.
이때는 K(Q) 규칙에 따라 반복된 문자열의 길이를 연산하여 기록합니다.
K는 한자리의 정수입니다. 그러므로 각 스택 깊이 별 문자열을 저장해놓은 G배열과 연산된 문자열 길이를 갖는 V배열을 참고합니다.

이때 ")" 문자가 올때 K(Q) 규칙에 따라 연산되는 코드 부분은 아래와 같습니다.

 

V[idx] += Int(G[idx].last!.asciiValue! - 48) * V[idx+1] - 1

이 부분은 즉, "V[idx]에 연산된 문자열 길이에 K(Q)로 반복된 문자열 길이를 누적시켜라" 를 의미합니다.

G[idx].last!.asciiValue!는 해당 문자의 아스키 값을 반환하는데, 가령 '0' ~ '9'의 실제 정수 값을 갖고자 한다면 본래 아스키 값에서 48을 빼면 되기 때문에 48을 빼고 있습니다.

그렇게 K(Q)의 K를 구할 수 있으며, V[idx+1]은 현재 반복되야 할 문자열의 길이를 담습니다.
-1 을 해주는 이유는 반복 문자열이 생성된 후, 반복횟수를 표현하는 한자리 정수, K가 남아있을 필요가 없기 때문입니다.

이렇게 세개의 조건을 두어 한번 문자열을 순회하면, O(N)의 복잡도로 해당 문제를 풀 수 있습니다. 
아마도 이러한 문제가 처음이라면 한 번의 설명을 보는 것 만으로는 문제 풀이법을 이해하기 힘들 수 있습니다. 그러므로 한번 관련 문제 예시를 들어보겠습니다.

 

 

 

---

알고리즘 연산 예시

let S = "33(562(71(9)))"

위의 문제열은 백준 문제에서 제시하는 예제입력입니다. 
문자열 S를 순회해보겠습니다. 먼저 "33(562(71(9" 까지 간 뒤의 상태를 보겠습니다. "(" 문자는 3번 나왔으므로, idx의 깊이는 3인 상태가 됩니다. 

 

G = [["3", "3"],["5", "6", "2"],["7", "1"],["9"], ...]
V = [2, 3, 2, 1, ....]

위와 같이 깊이에 따라 값이 연산되고 각각의 배열에 기록이 됩니다.
- G 배열에 저장된 값들은 곧 K(Q)의 K를 구하는데 활용 됩니다. 각 인덱스의 끝(.last!) 값들은 언제든 K 가 될 수 있겠지요. 
- V 배열에는 각 깊이 별 저장된 문자의 갯수 즉, 해당 깊이의 문자열 길이를 갖게 됩니다.
가령, "33"은 길이가 2이죠. "562"는 길이가 3입니다.


자, 이제 처음으로 ")" 문자가 나옵니다. 그 뒤에는 어떻게 될까요?

 

G = [["3", "3"],["5", "6", "2"],["7"],[], ...]
V = [2, 3, 2, 0, ....]
idx = 2

여기서 가장 깊은 인덱스인 3의 문자열, "9"는 그 이전 인덱스에 저장된 문자열의 맨 끝 한자리 정수의 횟수만큼 반복됩니다.

즉, 1("9")로 "9"가 1번 반복되므로 현재 반복문자열의 길이는 그대로 1입니다. 해당 값은 이전 인덱스에 누적되지만, 한자리정수, K로서 사용된 숫자는 사라지고 -1 되어 V[2]의 2는 그대로 2입니다.

-> V[2] += 1 - 1 -> 현상유지

이어서 다음 ")" 순회 간 연산결과를 보겠습니다.

 

G = [["3", "3"],["5", "6", "2"],[],[], ...]
V = [2, 6, 0, 0, ....]
idx = 1

")" 문자가 다시 나오며 스택 깊이는 1 감소합니다. idx는 1이 되지요.

이어서 반복문자열의 연산을 시작합니다.
이번에도 V[1] += K(Q)의 길이를 연산합니다.

-> 여기서  K(Q)의 길이는 "3" * V[2] - 1 (G[1] 맨 끝 정수 인 2 * V[2] - 1) 가 됩니다.
-> V[1] += 2 * 2 - 1이 되며 결과적으로 V[1]는 6이 됩니다.

이제 마지막 ")" 문자가 기다리고 있습니다. 마지막 연산을 진행해봅니다. 🤗

ㄱ

G = [["3", "3"],[],[],[], ...]
V = [19, 0, 0, 0, ....]
idx = 0

지금까지 설명은 충분이 했으니, 이번 마지막 연산은 연산 수식 결과만 기록하겠습니다.

최종적으로 결과는 -> V[0] += 3 * 6 - 1, V[0] = 19 가 됩니다. 
이렇게 최종적으로 K(Q)의 압축 해제 후의 길이는 19가 되며 이는 곧 정답이 됩니다. 

 

 

 

---

오늘은 스택문제, 1662번 압축 문제를 Swift(스위프트)로 풀어봤습니다.

아마도 이러한 괄호문제에 익숙하지 않으시다면 한번에 이해하기는 힘들 수 있습니다. 그러므로 스택의 원리를 생각하면서, 직접 그림을 그려보시거나 디버깅을 해보시는 것을 추천드립니다. 👩🏻‍💻

 

다음에도 스위프트로 많은 알고리즘 문제를 풀어봐요~
많은 의견 부탁드립니다. 즐거운 코딩 되세요~ ^-^// 👨🏻‍💻