백준 2504 괄호의 값 java
문제 설명
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.
- 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
- 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
- X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.
- ‘()’ 인 괄호열의 값은 2이다.
- ‘[]’ 인 괄호열의 값은 3이다.
- ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
- ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
- 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.
입력
첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.
출력
첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.
처음 아이디어(실패)
여는게 나오면 stack push 닫으면 stack pop
[ push (push [push (push [([(
) pop ] pop ) pop ] pop -> pop을 하는데 주어진 괄호와 짝 안맞으면 0출력
pop 할때 곱하기 주기
stack이 비면 값 저장하고 다음 값과 더하기
틀린코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String st = bufferedReader.readLine();
Stack<Character> stack = new Stack<>();
int result=0;
int num =1;
boolean check=true;
for (int i = 0; i < st.length(); i++) {
char c = st.charAt(i);
if (c == '(' || c == '[') {
if (num != 1) {
result+=num;
num=1;
}
stack.push(c);
}
else {
if (stack.isEmpty()) {
System.out.println(0);
check=false;
break;
}
Character pop = stack.pop();
if ((pop == '(' && c == ']') || (pop == '[' && c == ')')) {
System.out.println(0);
check = false;
break;
}
if (pop == '(') {
num *= 2;
} else {
num*=3;
}
}
}
if (check&&!stack.isEmpty()) {
System.out.println(0);
check = false;
} else {
if (check){
System.out.println(result);
}
}
}
}
=> 입력이 잘못된 경우 잡아내기는 성공
문제점
(()[[]])([]) 의 경우 (()[[]]) 에서 제일 바깥쪽 내부에 괄호 안쪽 두 값을 더한 후 2를 곱해야 하는데 그 과정이 생략되어 틀린 값이 출력됨
생각한 해결방법
다음괄호가 열리는 괄호이면서 스택이 비어있는 경우 괄호 한개가 끝났다고 생각하고 그 값을 저장하고 더해줌
괄호 닫히고 바로 새로운 괄호 시작시(스택 비어있지 않음)에 전에 계산한 값 저장( 전 값에 더하기)
괄호 닫히고 새로운 괄호 시작하는데 스택이 비었을때 다 더하기 저장했던값 결과로 옮기고 비우기
여러 테스트케이스 성공했지만 반례 발생함
틀린코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String st = bufferedReader.readLine();
Stack<Character> stack = new Stack<>();
int result=0;
int num =1;
int temp = 0;
boolean check=true;
for (int i = 0; i < st.length(); i++) {
char c = st.charAt(i);
if (c == '(' || c == '[') {
stack.push(c);
}
else if (c==')'|| c==']'){
//앞쪽 괄호가 없는 경우
if (stack.isEmpty()) {
System.out.println(0);
check=false;
break;
}
Character pop = stack.pop();
//앞쪽에 짝이 안맞는 괄호가 있는 경우
if ((pop == '(' && c == ']') || (pop == '[' && c == ')')) {
System.out.println(0);
check = false;
break;
}
char next=' ';
if (i != st.length() - 1) {
next = st.charAt(i + 1);
}
//마지막이거나 다음에 괄호가 열리고 스택이 비어있는 경우
if ((i+1 == st.length())|| ((next == '(' || next == '[' )&& stack.isEmpty())) {
temp += num;
if (pop == '(') {
temp*= 2;
} else {
temp *= 3;
}
result += temp;
temp=0;
num=1;
continue;
}
if (pop == '(') {
num *= 2;
} else if(pop=='['){
num*=3;
}
//괄호 닫히고 바로 새로운 괄호 시작시(스택 비어있지 않음)에 전에 계산한 값 저장( 전 값에 더하기)
if (next == '(' || next == '[') {
temp += num;
num=1;
}
}else {
System.out.println('0');
check = false;
}
}
if (check&&!stack.isEmpty()) {
System.out.println(0);
check = false;
} else {
if (check){
System.out.println(result);
}
}
}
}
괄호 닫히고 바로 새로운 괄호 시작시(스택 비어있지 않음)에 전에 계산한 값 저장( 전 값에 더하기)
=> 이부분에서 문제 발생
((())[(())()])
위와 같은 케이스의 경우 ((())[(()) 여기서 다음 괄호가 열리는데 이걸 이전 괄호가 끝났다고 생각하고 temp에 저장해버림 그래서 [ ] 안의 값을 더해서 3을 곱해야 하는데 앞에서 계산한 (()) 와 더해버리는 상황 발생
=> 이 방법 유지하려면 어떤 괄호가 시작인지 확인해야해서 코드가 더 정신없어질 것 같다는 판단 다른 방법으로 풀기 시도
다음 아이디어(성공)
괄호가 열릴 때 값을 곱하고 닫힐때마다 더해주는 방식
열릴때 *2 하고 가장 안쪽 괄호가 닫힐때 지금까지 곱한 값을 결과값에 더해주고 나누기 2 -> 가중치를 조절하며 풀이
((() -> *2*2*2 를 결과값에 더한 후 /2 -> result=8 , num=4
((()) -> 결과값은 변하지 않고 가중치만 /2 -> result=8, num=2
((())[(() -> num*3*2*2 를 결과값에 더한 후 /2 -> result = 24+8 = 32, num=12
((())[(())()] -> )닫힐때 num/2 -> , 열릴때 *2, 닫힐때 가장 안쪽 괄호이기 때문에 result에 num 더해준 후 /2 -> result = 32+ 12 = 44 , num= 6
((())[(())()]) -> 닫힐때 num/2지만 결과값에는 영향x
=> 결과는 44
정답 코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String st = bufferedReader.readLine();
Stack<Character> stack = new Stack<>();
int result=0;
int num =1;
boolean check=true;
for (int i = 0; i < st.length(); i++) {
char c = st.charAt(i);
if (c == '(' || c == '[') {
stack.push(c);
if (c == '(') {
num *= 2;
} else {
num *= 3;
}
} else if (c == ')' || c == ']') {
//앞쪽 괄호가 없는 경우
if (stack.isEmpty()) {
check = false;
break;
}
Character pop = stack.pop();
//앞쪽에 짝이 안맞는 괄호가 있는 경우
if ((pop == '(' && c == ']') || (pop == '[' && c == ')')) {
check = false;
break;
}
//가장 안쪽 괄호인지 확인
char pre = st.charAt(i - 1); //직전 괄호
if ((pre == '(' && c == ')') || (pre == '[' && c == ']')) {
result += num;
}
if (c == ')') {
num /= 2;
} else {
num /= 3;
}
} else {
check = false;
}
}
if (check&&!stack.isEmpty()) {
check = false;
}
if (check) {
System.out.println(result);
} else {
System.out.println(0);
}
}
}
틀린 입력 잡아주는 코드는 그대로 사용
세시간동안 잡고있었다..