👀 문제
https://www.acmicpc.net/problem/1918
👊 도전
1. 설계
- 알파벳은 출력, 문자열은 스택에 넣고 비교한다.
- ’(‘는 스택에 그냥 삽입, ‘)’는 여는 괄호가 나올 때까지 pop한다.
- +,-,*,/ 연산자는 우선순위를 비교하여 넣는다.
- 현재 연산자가 top보다 커야지 넣을 수 있다.
- 같거나 작은 경우에는 3번이 만족할 때까지 pop한다.
- for문 종료 후 스택에 남아있는 값들을 모두 pop한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.*;
import java.io.*;
/**
* @author HEESOO
*
*/
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String str=br.readLine();
int n=str.length();
StringBuilder sb=new StringBuilder();
Stack<Character> st=new Stack<>();
// 연산자별 우선순위 저장
HashMap<Character, Integer> map=new HashMap<>();
map.put('(', 0);
map.put('+', 1);
map.put('-', 1);
map.put('*', 2);
map.put('/', 2);
for(int i=0;i<n;i++) {
char ch=str.charAt(i);
// 알파벳은 바로 출력
if('A'<=ch && ch<='Z') sb.append(ch);
else {
switch(ch) {
case '(':
st.push(ch);
break;
case ')':
// 여는 괄호가 나올 때까지 출력
while(!st.isEmpty() && st.peek()!='(')
sb.append(st.pop());
// 여는 괄호 pop
if(!st.isEmpty() && st.peek()=='(') st.pop();
break;
default: // 연산자
// top우선순위 < ch우선순위여야 push 가능
while(!st.isEmpty() && map.get(st.peek())>=map.get(ch))
sb.append(st.pop());
st.push(ch);
}
}
}
// 남은 연산자들 모두 출력
while(!st.isEmpty()) sb.append(st.pop());
System.out.println(sb.toString());
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 스택에는 연산자만 저장한다
- ’(‘ : 그냥 push
- ’)’ : ‘(‘ 나올 때까지 pop, 닫는 괄호는 스택에 저장하지 않는다.
- 나머지 연산자들은 top보다 내 우선순위가 커야 push할 수 있다.
- 위 조건을 만족할 때까지 pop한다.
- 연산자의 우선순위를 알기 위해 HashMap에 넣어 사용하였다.
- for문 종료 후 스택에 남은 값들을 모두 pop한다.
5. 성능
- 시간 복잡도: O(N)
- 공간 복잡도: O(N)
👏 해결 완료!
참고
- 백준 1918 후위 표기식 Java https://dundung.tistory.com/133