Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 멘딕스
- 정렬
- 트리
- Recursion
- 재귀
- 집합
- microflow
- 매개변수 탐색
- 완전탐색
- domain model
- SQL
- MySQL
- algorithm
- 자료구조
- Mendix
- Bruteforce
- 가중치없는그래프
- dfs
- 반효경교수님
- 그래프
- 이분탐색
- 해시맵
- git
- 알고리즘
- 스택
- lcap
- 백트래킹
- Sort
- 자바
- 프로그래머스
Archives
- Today
- Total
mondegreen
[240409] 알고리즘 리부트 46일차 - 백준 2504 자바 본문
알고리즘 풀이 및 리뷰/[패캠] 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 리뷰
[240409] 알고리즘 리부트 46일차 - 백준 2504 자바
앙갱 2024. 4. 10. 21:13반응형
[Part2-Chapter02-Clip04]
-백준 2504 괄호의 값
짝이 되는 괄호를 if 문으로 복잡하게 쓰지 않기 위해 map에 담아서 짝을 맞추도록 했고 소괄호와 대괄호를 2와 3으로 매칭시키는 것도 map을 활용했다. 값을 넣을 때마다 최근 넣은 값을 저장한다. 괄호가 열릴 때마다 곱을 해주고 닫힐 때마다 다시 해당하는 수로 나누어서 결과값을 갱신시키는 방식으로 풀이했다. 가장 먼저 예외처리할 부분은 괄호가 짝이 맞도록 닫히지 않는다면 0을 반환해야 한다. 따라서 일단 입력값의 길이가 홀수라면 바로 0을 반환하고, stack을 활용해 괄호가 잘 닫히고 있는지도 확인하여 스택에 남은 값이 있다면 0을 반환하도록 구현했다.
여는괄호인 경우 스택에 담아주고 해당하는 숫자를 곱해준다. 닫는 괄호인 경우 스택이 비어 있지 않고 스택의 맨 위값이 여는 괄호이고 짝이 맞다면 스택에서 최상단 값을 제거한다. 직전에 넣은 값이 여는 괄호였다면 현재 누적곱 값을 결과값에 더해주고 누적곱에서 해당 값을 다시 나눠서 원상복구 해준다. 직전에 넣은 값이 닫는 괄호였다면 원상복구만 진행해준다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
Deque<Character> basic = new ArrayDeque<>();
HashMap<Character, Character> map = new HashMap<>();
HashMap<Character, Integer> num = new HashMap<>();
map.put('(', ')');
map.put('[', ']');
num.put('(', 2);
num.put('[', 3);
num.put(')', 2);
num.put(']', 3);
int ans = 0;
int multiple = 1;
if (str.toCharArray().length % 2 == 0) {
char lastLetter = '-';
for (char c : str.toCharArray()) {
// 여는 괄호라면
if (map.containsKey(c)) {
basic.push(c);
multiple *= num.get(c);
}
// 이번에 넣는 값이 닫는 괄호이고
else {
//만약 스택 상단의 값과 일치한다면 pop
if (!basic.isEmpty() && map.containsKey(basic.peek()) && map.get(basic.peek()) == c) {
basic.pop();
// 직전에 넣은 값이 여는 괄호였다면
if (map.containsKey(lastLetter)) {
ans += multiple;
}
multiple /= num.get(c);
} else {
basic.push(c);
}
}
lastLetter = c;
}
}
if (!basic.isEmpty()) ans = 0;
System.out.println(ans);
}
}
반응형
'알고리즘 풀이 및 리뷰 > [패캠] 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 리뷰' 카테고리의 다른 글
[240420] 알고리즘 리부트 53일차 - 백준 2747 자바 (0) | 2024.04.20 |
---|---|
[240410] 알고리즘 리부트 47일차 - 백준 5397 자바 (0) | 2024.04.10 |
[240325] 알고리즘 리부트 38일차 - 백준 10828 자바 (0) | 2024.03.25 |
[240322] 알고리즘 리부트 36일차 - 백준 2230 자바 (0) | 2024.03.22 |
[240321] 알고리즘 리부트 35일차 - 백준 2003, 1806 자바 (0) | 2024.03.21 |