어흥
[백준 1662] 압축 (Java) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/1662
1. 주의할 점
- 괄호에 대한 처리
- 문자열을 복원 v.s 길이만 구하기
2. 구현
- 문자열을 복원하지 않고 길이만 구해도 되므로, 길이만 구하여 메모리 또한 아낄 수 있도록 한다. 다만, 구현이 좀 더 복잡 할 수 있다
- Stack 2개를 이용하여 해결한다
#예시
234(10)
- Len 스택에는 '(' 괄호가 나오기 전의 숫자를 제외하고 계산된 길이. 위의 예시에선 '23'이 해당하므로 길이 2를 저장
- Mul 스택에는 '(' 괄호 직전에 나온 숫자를 저장. 위의 예시에선 '4'가 해당하므로 4를 저장
- 위의 설명이 부실하기에 아래 몇 개의 TC를 예로 들겠습니다
#TC 1
11(00)9
Len: push(1) -> pop()
Mul: push(1) -> pop()
#TC 2
22(234(01)1)
Len: push(1) -> push(2) -> pop() -> pop()
Mul: push(2) -> push(4) -> pop() -> pop()
#TC 3
33(562(71(9)22)2)
Len: push(1) -> push(2) -> push(1) -> pop() -> pop() -> pop()
Mul: push(3) -> push(2) -> push(1) -> pop() -> pop() -> pop()
- Cnt를 0으로 초기화하고 문자열을 좌에서 우로 순차적으로 검사한다
- 문자열에서 숫자가 나오면 Cnt++, '('가 나오면 Cnt를 계산하여 Len과 Mul 스택에 값을 추가한다. ')'가 나오면 Mul과 Len 스택에서 원소를 뽑아서 계산하고 Cnt에 할당한다
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
public static void main (String[] args) throws java.lang.Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine().trim();
Stack<Integer> len = new Stack<>();
Stack<Integer> mul = new Stack<>();
int cnt=0;
for(int i=0;i<str.length();i++){
char c = str.charAt(i);
if(c=='('){
cnt-=1;
int mulNum = str.charAt(i-1)-'0';
len.add(cnt);
mul.add(mulNum);
cnt=0;
}
else if(c==')'){
int val = mul.peek();
mul.pop();
val*=cnt;
int plus = len.peek();
len.pop();
cnt = plus + val;
}
else cnt++; //숫자
}
System.out.print(cnt);
}
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 17265] 나의 인생에는 수학과 함께 (Java) (6) | 2021.07.27 |
---|---|
[백준 22116] 창영이와 퇴근 (Java) (0) | 2021.07.27 |
[백준 17616] 등수 찾기 (Java) (0) | 2021.06.17 |
[백준 2637] 장난감조립 (Java) (0) | 2021.06.17 |
[백준 11562] 백양로 브레이크 (Java) (0) | 2021.06.16 |
Comments