[오늘의 문제]
https://www.acmicpc.net/problem/1662
[오늘의 학습 키워드]
- 스택
1. 문제 설명
압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.
문제 설명만 보면 조금 불친절 해서 예시를 보며 이해해야 합니다.
33(562(71(9))) 가 주어질 때 해당 문자열은 압축된 문자열이고 문자열을 압축 해제하면 문자열의 길이가 19가 된다는 의미입니다.
앞서 주어진 K와 Q를 살펴보면 K와 Q의 모양은 반드시 K(Q) 모양입니다.
여기서 K는 반드시 한자리 숫자 라고 하니 주어진 입력을 분해하면 다음과 같이 볼 수 있습니다.
3 3(56 2(7 1(9))))
여기서 K(Q) 모양을 만족하는 가장 안쪽 1(9) 부터 풀어 보면 9가 1번 반복된다는 의미입니다.
그럼 9가 나오고 앞에있는 7과 더해져 79가 된다는 의미입니다.
다시 K(Q) 모양을 보면 2(79) 입니다. 즉, 79가 두번 반복된다는 의미이니 7979로 표시됩니다.
여기에 앞에있는 56을 만나 567979 가 되고 이게 3번 반복된다는 의미입니다.
그럼 567979567979567979 로 표시되고 자릿수는 18 입니다.
여기에 앞에있는 3을 더해 356797956979567979 로 총 자릿수가 19가 되는 것입니다.
이제 조건에 따라 문제를 해결해 보겠습니다.
[제한사항]
- 시간 제한 2초
- 메모리 제한 128MB
- S의 길이는 최대 50
- 문자열은 (, ), 0-9사이의 숫자로만 들어온다.
2. 접근 방식
입력으로 주어지는 것은 (, ), 숫자 총 3개가 주어집니다.
그럼 문자열을 입력받고 반복문을 돌릴 때 3번의 조건을 나누어 보겠습니다.
우선 숫자가 오는 경우를 보겠습니다.
숫자가 오는 경우 우선 자릿수를 세어주어야 합니다.
K든 Q든 결국 문제는 자릿수를 구하는 문제이므로 자릿수를 구할 count 변수를 생성해 자릿수를 세어줍니다.
그럼 앞에있는 33 부터 자릿수를 세어주겠죠
여기서 여는괄호를 만나는데 이때 저장할 정보는 K의 숫자정보와 K앞에 위치하는 숫자의 자릿수를 저장해야 합니다.
이는 stack에 저장하고 닫는 괄호를 만날 때 pop을 통해 순서대로 계산이 가능하게 해보겠습니다.
그럼 여는 괄호를 만났으니 이전까지 세어둔 자릿수를 저장해야 하는데 count가 2겠죠?
근데 아직 K를 제외시키지 않았으니 count-1을 stack에 저장하고 K를 저장해 주어야 합니다.
그럼 K는 어떻게 파악하는지가 또 문제이니 숫자를 세며 K를 계속 업데이트 해줍니다.
여는 괄호를 만나기 전의 모든 숫자는 K가 될 수 있습니다. 따라서 계속 K를 업데이트 하다가 여는 괄호를 만나면 K와 자릿수를 stack에 저장합니다.
그럼 닫는 괄호를 만날 경우인 (9) 의 경우 여는 괄호를 만나 이전까지 저장된 K와 자릿수가 있을 겁니다.
닫는 괄호를 만났으니 9가 Q가 되어야 합니다.
그럼 Q는 현재 세어준 자릿수가 될 테고, 이전에 구한 K만큼 Q를 반복시켜주어야 합니다.
즉 Q의 자릿수가 K만큼 곱해지는 겁니다. 거기에 이전 자릿수를 더해주면 되겠죠
이걸 닫는 괄호가 올 때마다 실행해 주어야 합니다.
코드로 보겠습니다.
3. 코드
import sys
input = sys.stdin.readline
S = input().strip()
count = 0
K = 0
stack = []
for s in S:
# 현재 문자의 자릿수
if s == "(":
stack.append([count - 1, K])
count = 0
elif s == ")":
num_range, k = stack.pop()
count = count * k + num_range
# 숫자가 온 경우
else:
count += 1
K = int(s)
print(count)[코드 설명]
앞서 접근 방식에 설명한 것을 그대로 코드로 구현한 것입니다.
여는 괄호가 오는 경우
닫는 괄호가 오는 경우
숫자가 오는 경우를 구분해 최대 50자리인 문자열을 탐색하는 겁니다.
그럼 반복문의 최대 횟수는 O(50)이 되겠죠
실제 동작을 살펴보면
1. 3을 만나 count를 늘려줍니다.
K 는 현재 3이 됩ㄴ다.
2. 3을 만나 count를 늘려줍니다.
count는 2가 되고 K는 3입니다.
3. 여는 괄호를 만났습니다.
현재 2자리인데 K가 구분되지 않았으니 count-1을 해주어 자릿수를 구하고 K를 stack에 저장합니다.
그럼 1, 3이 stack에 저장되겠죠
4. 5를 만나 count를 늘려줍니다.
count는 1, K는 5 입니다.
5. 6을 만나 count를 늘려줍니다.
count는 2, K는 6입니다.
6. 2를 만나 count를 늘려줍니다.
count는 3, K는 2 입니다.
7. 여는괄호를 만나 stack에 업데이트 해줍니다.
count-1 과 K를 업데이트 하면 현재 스택은 다음과 같습니다.
stack = [[1, 3], [2, 2]]
8. 7을 만나 count를 늘려줍니다.
count는 1 K는 7입니다.
9. 1을 만나 count를 늘려줍니다.
count는 2, K는 1 입니다.
10. 여는괄호를 만나 stack을 업데이트 합니다.
stack = [[1, 3], [2, 2], [1, 1]]
11. 9를 만나 count를 1 늘려줍니다.
count 는 1, K 는 9가 됩니다.
12. 닫는 괄호를 만나 stack을 pop 해줍니다.
stack의 가장 마지막 1, 1이 나옵니다.
여기서 자릿수는 1, K는 1 이죠 이걸 현재 자릿수에 계산합니다.
1 * 1 + 1 = 2가 되죠 즉 79가 된 것입니다.
이걸 count로 업데이트 합니다.
13. 닫는 괄호를 만나 stack을 pop 해줍니다.
현재 stack의 마지막 2, 2를 pop 합니다.
여기서 자릿수는 2, K는 2죠 이걸 계산하면
현재 count * K + 자릿수
2 * 2 + 2 를 하면 6이 되죠
그럼 count는 6이 됩니다.
14. 닫는 괄호를 만나 stack을 pop 해줍니다.
현재 stack의 마지막 1, 3을 pop 해줍니다.
현재 count는 6, K는 3, 자릿수는 1 입니다. 계산하면 19가 나오고 반복문이 종료됩니다.
4. 결과
[회고]
사실 문제는 매일 풀고 있었는데 현생을 산다고 글을 쓰지 못했습니다.
대신 velog는 최대한 쓰려고 했습니다.
이번 문제의 경우 접근 방법을 찾는게 굉장히 어려웠습니다.
첫 문제를 이해하는 것도 어려워서 알고리즘을 같이푸는 형에게 물어봤습니다.
문제를 이해하고 처음에는 stack 대신 문자열을 이용하려 했는데 이러면 무조건 메모리 초과가 날 것 같았습니다.
왜냐하면 잘못하면 Q의 자릿수에 9씩 계속곱해서 자릿수가 2,147,473,647 이 값을 넘어갈 수도 있기 때문입니다.
S의 최대 길이가 50이니 9(1)가 최대 50개 입력된다면 9의 약 20승이 넘게 되고 대충 계산해보니 12,157,665,459,056,928,801 이정도 나옵니다.
무조건 메모리 초과나니 이건 아닌것 같고 어떻게 접근하지를 고민을 많이 했습니다.
그러다 꽃힌게 K가 무조건 1자리가 온다는 것이엇습니다.
그럼 자릿수 계산하려면 필요한게 K랑 이전에 몇개의 숫자가 온건지만 알면 되었기 때문입니다.
그렇게 생각하고 자릿수만 계산하려는데 이번에는 count가 문제였습니다.
조건분기는 했는데 자릿수를 어떻게 세어주지?숫자랑 괄호만날때마다 변수를 다시 선언하고 하면 이것도 문제가 될 것 같은데 라는 생각이 들었었고 계속 고민했는데 이게 여는 괄호를 만나기 직전에 오는 숫자가 K가 되는 거니까 이제까지 세어준 숫자자리수는 K 앞에 오는 숫자가 되겠구나 라는 생각이 들었고 어 그럼 굳이 변수 여러개 안써도 되겠는데 라는 생각이 들어 count 하나로 해결이 가능했습니다.
숫자를 만나면 무조건 자릿수를 세어주고 K를 계속 업데이트 하다가 여는 괄호 만나면 자릿수 -1 해서 K 앞에 오는 숫자 자릿수 맞춰주고 업데이트 한 K를 같이 묶어서 저장하면 되겠네 라고 생각해서 stack을 썻습니다.
마지막 닫는 괄호가 올때는 이제 스택에 저장한 값을 써야하는데 흠,, 이러다가 그냥 마지막부터 빼서 계산만 하면 되네 가 보였고 계산만 해서 처음에는 answer를 업데이트 하려 했는데 그렇게 하면 또 count와 answer를 맞추는 불필요한 과정이 생겼습니다.
그래서 결론적으로 count 하나로 자릿수를 세며 결과를 출력할 수 있었습니다.
'알고리즘' 카테고리의 다른 글
| [백준] 4179 불! - 골드 3 (0) | 2025.03.31 |
|---|---|
| [백준] 17471 게리맨더링 - 골드 3 (0) | 2025.03.30 |
| [백준] 6539 상범 빌딩 - 골드 5 (0) | 2025.03.23 |
| [프로그래머스] 2025 프로그래머스 코드챌린지 1차 예선 - 지게차와 크레인 - Lv. (0) | 2025.03.21 |
| [프로그래머스] 202 프로그래머스 코드챌린지 2차 예선 - 완전범죄 - Lv.2 (0) | 2025.03.20 |