🔗 문제
난이도 - 실버 1
알고리즘 분류 - 구현, 자료구조, 스택
💬 풀이
스트링 형태로 괄호열을 입력 받고, 반복문으로 돌며 각각의 문자에 대해 크게 케이스를 분류하여 처리한다.
괄호 문제이므로 스택 자료구조를 사용하고 괄호의 종류에 따라, 빈 스택인지의 여부에 따라 분기하여 최종적으로 구해야 할 result 변수에 값을 더하거나 곱할 것이다.
- 닫힌 괄호
-> 스택 top의 값이 괄호 쌍과 일치한다면 (): 2, []: 3을 리턴하는 함수 정의- 열린 괄호가 스택에 남아있는 경우(!stack.isEmpty())
- 바로 뒤에 닫힌 괄호 등장? tmp 임시 변수에 곱셈을 하여 저장- 바로 뒤에 열린 괄호 등장?
-임시변수가 초기화된 상태? result에 반환값 바로 저장
-임시변수에 무언가 변화가 있는 상태? 임시 변수값을 result에 더하여 저장
- 바로 뒤에 열린 괄호 등장?
- 열린 괄호가 스택에 남아있는 경우(!stack.isEmpty())
- 열린 괄호
- 바로 스택에 넣어준다.
💻 코드
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class _2504 {
static Stack<Character> stack = new Stack<>();
static Stack<Integer> nums = new Stack<>();
static String line;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int result = 0;
int tmp = 1;
line = br.readLine();
stack.add(line.charAt(0));
for (int i=1; i<line.length(); i++) {
int temp = isClose(line.charAt(i)); // 괄호 쌍을 찾으면 -1이 아닌 값을 가짐
if (temp != -1) {
if (!stack.isEmpty()) {
if (isNextValue(i)) {
tmp *= temp;
} else if (!isNextValue(i)) {
if (tmp == 1) {
result += temp;
} else {
if (result == 0) {
result += tmp;
} else {
result *= tmp;
}
}
}
} else {
if (i == line.length()-1) {
tmp *= temp;
if (tmp != 1) result += tmp;
break;
}
if (tmp != 1) result += tmp;
result *= temp;
tmp = 1;
}
}
System.out.println(stack.toString() + " result, temp, tmp = " + result + ", " + temp + ", " + tmp);
}
System.out.println(stack.isEmpty() ? result : 0);
}
private static int isClose(char c) {
char curr = 0;
int num = 1;
if (!stack.isEmpty()) {
curr = (char) stack.peek();
}
if (!nums.isEmpty()) {
num = nums.pop();
}
switch (c) {
case ')':
if (curr == '(') {
stack.pop();
return 2 *num;
}
break;
case ']':
if (curr == '[') {
stack.pop();
return 3 *num;
}
break;
}
if (c == '(' || c == '[') {
stack.add(c);
}
if (isNum(c)) {
System.out.println(c);
nums.add(Integer.parseInt(String.valueOf(c)));
}
return -1;
}
/**
* @return
* 열린 괄호 뒤에 열린 괄호 / 닫힌 괄호 뒤에 닫힌 괄호 : true
* 이외: false
*/
private static boolean isNextValue(int i) {
if (i == line.length()-1) return false;
if (line.charAt(i) == ')' || line.charAt(i) == ']') {
return line.charAt(i + 1) == ')' || line.charAt(i + 1) == ']';
} else if (line.charAt(i) == '(' || line.charAt(i) == '[') {
return line.charAt(i + 1) == '(' || line.charAt(i + 1) == '[';
}
return false;
}
private static boolean isNum(char c) {
try {
Integer.parseInt(String.valueOf(c));
return true;
} catch (NumberFormatException e) {
return false;
}
}
}
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class _2504_2 {
static Stack<Character> stack = new Stack<>();
static String line;
static int mul = 1;
static int result = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
line = br.readLine();
for (int i=0; i<line.length(); i++) {
isClose(i);
}
System.out.println(stack.isEmpty() ? result : 0);
}
private static void isClose(int idx) {
switch (line.charAt(idx)) {
case '(':
stack.push('(');
mul *= 2;
break;
case '[':
stack.push('[');
mul *= 3;
break;
case ')':
if (stack.isEmpty() || stack.peek() != '(') {
result = 0;
break;
}
if (line.charAt(idx-1) == '(') {
result += mul;
}
stack.pop();
mul /= 2;
break;
case ']':
if (stack.isEmpty() || stack.peek() != '[') {
result = 0;
break;
}
if (line.charAt(idx-1) == '[') {
result += mul;
}
stack.pop();
mul /= 3;
break;
}
}
}
📊 정리
📍 어려웠거나 해결하지 못한 부분
스택에 열린 괄호만 push 하고, 닫힌 괄호에서는 이를 pop 하는 과정으로 각각의 괄호에 따라 2와 3을 곱해나가게 했지만 계속 실패가 떴다.
결국 다른 풀이를 찾아보니 난 pop과 동시에 2와 3을 각각 곱해줬다면, 대부분 push와 동시에 2와 3을 먼저 곱해두고, 더하기로 이어진 것이라면 다시 곱했던 수로 나누어 되돌려놓는 작업을 해주었다.
📍 오늘의 메모
문제의 테스트 케이스로 나온 값보다 반례가 훨씬 많은 문제라 한참을 헤맸다.
이 문제만 거의 몇 시간을 붙잡고 있으면서 느낀 바는, 일단 모르면 그림을 그리거나 글로 분기처리를 해나가면서 적고 난 후에 그에 맞게 조건식을 세우는 기본적인 방식으로 접근해보자 이다.
계속 머리로만 생각하고 그걸 코드로 작성하려 하니까 고도의 집중 상태가 아니고서야 쉽게 해결해내기 어려웠다.
그래도 일일이 하나하나 과정마다 출력해보며 답을 찾아간 것에서 스택 자료구조 복습도 하고, 백준에서는 실패로 처리되었지만 테스트 케이스와 내가 스스로 테스트해본 것으로는 코드가 돌아가 그것만으로 충분히 뿌듯하고 큰 쾌감을 느꼈다.
📍 참고 자료
서버 개발자를 꿈꾸며 성장하는 쭌입니다 😽