백준/1 - 5000
[백준] 1662번 : 압축(JAVA)
lms0806
2021. 8. 30. 14:05
728x90
https://www.acmicpc.net/problem/1662
풀이
일단 String을 계속 선언하면서 하면 최종적으로 메모리초과가 뜹니다.
문제는 최종 문자열을 출력하는게 아닌 문자열의 길이를 출력하는거니 길이체크만 해주면 되서 long으로 해주면됩니다.
stack을 활용하여 )가 나올 시 (까지 count를 세줍니다.
여기서 *(count를 세준 후 나온 값을 *과함께 넣어줌)이 나올 경우 그값을 그대로 더해줍니다. 아닌경우 +1
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<String> stack = new Stack<>();
for(char ch : br.readLine().toCharArray()) {
if(ch != ')') {
stack.add(ch + "");
}
else {
int count = 0;
while(!stack.peek().equals("(")) {
count += stack.pop().equals("*") ? Integer.parseInt(stack.pop()) : 1;
}
stack.pop();
stack.push(String.valueOf(count * Integer.parseInt(stack.pop())));
stack.push("*");
}
}
long answer = 0;
while(!stack.isEmpty()) {
answer += stack.pop().equals("*") ? Integer.parseInt(stack.pop()) : 1;
}
System.out.print(answer);
}
}
728x90