[코딩테스트][백준] 🔥 백준 1918번 "후위 표기식" 문제: Python과 Java로 완벽 해결하고 면접 준비까지! 🔥
문제 링크
https://www.acmicpc.net/problem/1918
🕒 Python 풀이시간: 40분
from collections import deque
exp = list(input())
ans = []
stack = deque()
# 연산자 우선순위를 저장하는 딕셔너리
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
for c in exp:
if c.isalpha():
ans.append(c)
elif c == '(':
stack.append(c)
elif c == ')':
while stack and stack[-1] != '(':
ans.append(stack.pop())
stack.pop() # '('를 제거
else:
# 현재 연산자와 스택 상단의 연산자 우선순위를 비교하여 처리
while stack and stack[-1] != '(' and precedence.get(stack[-1], 0) >= precedence[c]:
ans.append(stack.pop())
stack.append(c)
while stack:
ans.append(stack.pop())
answer = "".join(ans)
print(answer)
🕒 Java 풀이시간: 40분
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String exp = br.readLine();
System.out.println(infixToPostfix(exp));
}
private static String infixToPostfix(String exp) {
StringBuilder ans = new StringBuilder(exp.length());
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < exp.length(); i++) {
char c = exp.charAt(i);
if (Character.isLetter(c)) {
ans.append(c);
} else if (c == '(') {
stack.addLast(c);
} else if (c == ')') {
while (!stack.isEmpty() && stack.getLast() != '(') {
ans.append(stack.removeLast());
}
stack.removeLast(); // Remove '('
} else {
while (!stack.isEmpty() && precedence(stack.getLast()) >= precedence(c)) {
ans.append(stack.removeLast());
}
stack.addLast(c);
}
}
while (!stack.isEmpty()) {
ans.append(stack.removeLast());
}
return ans.toString();
}
private static int precedence(char op) {
switch (op) {
case '+': case '-':
return 1;
case '*': case '/':
return 2;
default:
return -1; // For '(' and any other invalid character
}
}
}
스택을 이용한 후위표기식 계산하기 🧮
후위표기식(Postfix Notation) 계산은 스택을 활용하여 효율적으로 수행할 수 있습니다. 이번 글에서는 스택을 사용하여 연산자와 괄호를 처리하는 방식을 정리해보겠습니다.
1. 스택의 필요성 💡
후위표기식을 계산할 때, 스택은 연산자와 괄호를 관리하는 중요한 역할을 합니다. 스택을 통해 연산자의 우선순위를 유지하고, 괄호의 쌍을 맞추는 과정을 간편하게 처리할 수 있습니다.
2. 연산자 처리 방법 ⚙️
- 연산자 추가: 연산자가 나타날 경우, 스택에 추가합니다. 이때 우선순위를 고려해야 합니다.
- 낮은 우선순위 연산자 위에는 반드시 높은 우선순위의 연산자만 올 수 있습니다.
- 동일한 우선순위의 연산자는 스택에 추가할 수 없습니다.
3. 괄호 처리 방법 ( ) 🔄
- 여는 괄호 '(': 만나면 스택에 추가합니다.
- 닫는 괄호 ')': 해당 괄호와 쌍을 이루는 여는 괄호가 나올 때까지 스택에서 연산자를 제거합니다. 이를 통해 괄호 안의 연산을 처리하게 됩니다.
4. 피연산자 관리 📊
- 피연산자는 계산 결과를 저장하는 변수(또는 리스트)에 넣습니다. 연산자가 등장할 때마다 스택에서 피연산자를 꺼내어 계산을 수행하고, 결과를 다시 피연산자 저장소에 추가합니다.
5. 정리 및 결론 📝
스택을 이용한 후위표기식 계산은 연산자의 우선순위와 괄호 처리를 통해 정확하고 효율적인 계산을 가능하게 합니다. 이러한 방법은 자료구조의 기초를 이해하는 데 큰 도움이 되며, 다양한 알고리즘 문제에서도 유용하게 활용될 수 있습니다.
코딩 테스트 면접 준비: 효율적인 자료구조와 입출력 방법 🖥️
1. 효율적인 입력 처리: BufferedReader 사용하기 📥
입력 부분에서 System.in으로 스트림을 받아 문자열 처리를 위해 Reader로 변환한 후, 이를 효율적으로 처리하기 위해 BufferedReader를 사용하는 것이 좋습니다. BufferedReader는 내부 버퍼를 사용하여 한 번에 여러 데이터를 읽기 때문에, Scanner보다 훨씬 빠른 성능을 제공합니다. 특히 대량의 데이터를 다룰 때 그 차이는 더욱 두드러집니다.
2. 메모리 효율을 위한 StringBuilder 활용 🛠️
StringBuilder의 길이를 미리 알고 있다면, 해당 길이를 지정해 주어 메모리를 할당하는 것이 메모리 효율상 좋습니다. 이렇게 하면 불필요한 메모리 재할당을 줄일 수 있어 성능이 개선되고, 메모리 사용량도 최적화할 수 있습니다.
3. 성능을 높이는 자료구조: ArrayDeque vs LinkedList ⚙️
LinkedList 대신 ArrayDeque를 사용하는 것이 좋습니다. ArrayDeque는 배열 방식을 사용하여 메모리 접근이 연속적이기 때문에 CPU 캐시 효율성이 높아 성능이 향상됩니다. 반면, LinkedList는 노드가 메모리 상에 분산되어 있어 비연속적 접근을 유발하고, 이로 인해 캐시 미스를 발생시켜 성능을 저하시킵니다. 또한, LinkedList는 포인터를 저장해야 하므로 메모리 사용량도 더 높습니다.
이렇게 Python과 Java로 백준의 "후위 표기식" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
