알고리즘 풀이/백준

★ [백준][Java] 2504번 괄호의 값(Stack) #2

배게 2021. 9. 11. 09:22
728x90
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        char[] input = br.readLine().toCharArray();
        
        int unit = 1;
        int res = 0;
        Stack<Character> st = new Stack<>();
        for(int i=0; i<input.length; i++) {
            if(input[i] == '(') {
                unit*=2;
                st.push('(');
            }
            else if(input[i] == '[') {
                unit*=3;
                st.push('[');
            }
            else if(input[i] == ')') {
                if(st.isEmpty() || st.peek() == '[') {
                    System.out.println(0);
                    return ;
                }
                else if(input[i-1]=='(') {
                    res+=unit;
                }
                unit/=2;
                st.pop();
            }
            else if(input[i] == ']') {
                if(st.isEmpty() || st.peek() == '(') {
                    System.out.println(0);
                    return ;
                }
                else if(input[i-1]=='[') {
                    res+=unit;
                }
                unit/=3;
                st.pop();
            }
        }
        
        
        if(st.isEmpty())
            System.out.println(res);
        else 
            System.out.println(0);
        
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}
cs

 

 

 

뭔가 어려웠음

수학 공식(분배법칙?)으로 해결책을 못끌어내면 못푸는 문제일듯

 

a * ( b + c ) = a*b + a*c 이런 식으로 풀어 써야함

 

+ 모든 과정 끝나고 stack isEmpty()를 만족 못하면 0 출력

 

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    public static void main(String[] args) throws IOException{
        char[] arr = br.readLine().toCharArray();
        
        Stack<Character> st = new Stack<>();
        int res = 0;
        int val = 1;
        boolean valOn = false;
        for(int i=0; i<arr.length; i++) {
            if(arr[i]=='(') {
                st.push('(');
                val*=2;
                valOn = true;
            }
            else if(arr[i]=='[') {
                st.push('[');
                val*=3;
                valOn = true;
            }
            else if(arr[i]==')') {
                if(st.isEmpty() || st.peek()!='(') {
                    System.out.println("0");
                    return;
                }
                else {
                    st.pop();
                    if(valOn) {
                        res+=val;
                        valOn = false;
                    }
                    val/=2;
                }
                
                
                
            }
            else if(arr[i]==']') {
                if(st.isEmpty() || st.peek()!='[') {
                    System.out.println("0");
                    return;
                }
                else {
                    st.pop();
                    if(valOn) {
                        res+=val;
                        valOn = false;
                    }
                    val/=3;
                }
            }
            
        }
//        System.out.println(res);
        if(!st.isEmpty()) res = 0;
        bw.write(String.valueOf(res)); 
        bw.flush(); 
        bw.close();
    }
}
 cs
저작자표시