수식 최대화

Posted on Edited on In , ,

문제정의

(+,-,*)로 이루어진 수식이 있다. 이 수식의 우선순위를 정하여 수식 결과의 최대 절대값을 구하는 문제이다. 단 세 연산자 간의 우선순위는 같을 수 없다.

문제풀이

전체 코드는 다음과 같다. 

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
package level2;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class MaximizeExpression {

    //프로그래머스 문제풀이 level2 수식 최대화
    public static void main(String[] args) {
        String expression = "100-200*300-500+20";
        int[] price = new int[6];
        Queue<String> q1 = ReturnPostfix(1, 2, 3, expression);
        Queue<String> q2 = ReturnPostfix(1, 3, 2, expression);
        Queue<String> q3 = ReturnPostfix(2, 1, 3, expression);
        Queue<String> q4 = ReturnPostfix(3, 1, 2, expression);
        Queue<String> q5 = ReturnPostfix(2, 3, 1, expression);
        Queue<String> q6 = ReturnPostfix(3, 2, 1, expression);
        
        price[0] = ReturnPrice(q1);
        price[1] = ReturnPrice(q2);
        price[2] = ReturnPrice(q3);
        price[3] = ReturnPrice(q4);
        price[4] = ReturnPrice(q5);
        price[5] = ReturnPrice(q6);

        int answer = 0;
        for(int n : price)
        {
            if(answer < n)
                answer = n;
        }
        
        System.out.println(answer);
        
    }
    public static int ReturnPriority(int p_rank, int s_rank, int m_rank, char c)
    {
        switch(c){
            case '+':
                return p_rank;
            case '-':
                return s_rank;
            case '*':
                return m_rank;
            default:
                return -1;
        }
    }
    public static Queue<String> ReturnPostfix(int p_rank, int s_rank, int m_rank, String expression)
    {
        Stack<Character> stack = new Stack<>();
        Queue<String> q = new LinkedList<>();
        StringBuilder buff = new StringBuilder();
        for(char c : expression.toCharArray())
        {
            if(c >= 48 && c <=57)
                buff.append(c);
            else
            {
                q.add(buff.toString());
                buff.delete(0, buff.length());
                if(stack.empty())
                    stack.push(c);
                else
                {
                    int rank = ReturnPriority(p_rank, s_rank, m_rank, c);
                    while(!stack.empty() && ReturnPriority(p_rank, s_rank, m_rank, stack.peek()) <= rank)
                    {
                        q.add(String.valueOf(stack.peek()));
                        stack.pop();
                    }
                    stack.push(c);
                }
                
                    
            }
        }
        q.add(buff.toString());
        while(!stack.empty())
        {
            q.add(String.valueOf(stack.peek()));
            stack.pop();
        }
        return q;
    }
    public static int ReturnPrice(Queue<String> q)
    {
        Stack<Integer> stack = new Stack<>();
        while(!q.isEmpty())
        {
            String s = q.poll();
            try{
                int n = Integer.parseInt(s);
                stack.push(n);
            }catch(NumberFormatException e)
            {
                int n2 = stack.peek();
                stack.pop();
                int n1 = stack.peek();
                stack.pop();
                if(s.equals("+"))
                    stack.push(n1+n2);
                else if(s.equals("-"))
                    stack.push(n1-n2);
                else
                    stack.push(n1*n2);
            }
        }
        return Math.abs(stack.peek());
    }
}
코드가 좀 긴 편인데 과정을 설명하자면 다음과 같다. 1. 중위표기식(infix)를 후위표기식(postfix)로 고친다. 2. 후위표기식을 계산하고 절대값을 반환한다. 3. 3가지 연산자로 만들 수 있는 모든 우선순위인 6가지에 대해서 1,2과정을 반복하고 가장 큰 값을 반환한다.

main에 있는 것이 3번과정이다. 우리는 1번과 2번에 대한 상세한 내용을 보려고 한다. 일단 중위표기식을 후위표기식으로 변환하는 코드를 살펴보자.

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
public static Queue<String> ReturnPostfix(int p_rank, int s_rank, int m_rank, String expression)
{
    Stack<Character> stack = new Stack<>();
    Queue<String> q = new LinkedList<>();
    StringBuilder buff = new StringBuilder();
    for(char c : expression.toCharArray())
    {
        if(c >= 48 && c <=57)
            buff.append(c);
        else
        {
            q.add(buff.toString());
            buff.delete(0, buff.length());
            if(stack.empty())
                stack.push(c);
            else
            {
                int rank = ReturnPriority(p_rank, s_rank, m_rank, c);
                while(!stack.empty() && ReturnPriority(p_rank, s_rank, m_rank, stack.peek()) <= rank)
                {
                    q.add(String.valueOf(stack.peek()));
                    stack.pop();
                }
                stack.push(c);
            }
            
                
        }
    }
    q.add(buff.toString());
    while(!stack.empty())
    {
        q.add(String.valueOf(stack.peek()));
        stack.pop();
    }
    return q;
}

받은 매개변수에 대해 간단히 살펴보면 p가 더하기 s가 빼기 m을 곱하기로 보면 된다. 이들에 대한 우선순위를 main에서 받아오는 것이며, 숫자가 작을 수록 우선순위가 높은 것으로 가정했다. expression은 중위표기식이다. 이제 중위표기식을 문자단위로 쪼갠다. 이 문자들을 살펴보면서 변환과정을 할 예정이다. for문의 첫번째 if문을 보면 c가 숫자인 경우 버퍼에다 문자를 담아준다. 주어진 식이 한자리 수만 주어진 것이 아니기 때문에 이렇게 한다. 만약 연산자가 주어진 경우 여태까지 버퍼에 담긴것이 한 숫자이므로 이를 스트링으로 바꿔 큐에 삽입한다. 삽입하고 난 뒤 버퍼에 있는 내용은 지운다. 이제 연산자에 대한 처리를 할 차례이다. 만약 스택이 비어있다면 연산자를 그대로 넣어준다. 그렇지 않다면 스택에 있는 연산자들과의 비교가 필요하다. 이들의 우선순위를 비교하여 우선순위가 자신보다 같거나 작다면 스택에서 꺼내서 큐에 넣는다. 이때, 우선순위가 같아도 꺼내는 이유는 같은 연산자일 때, 왼쪽에 있는 연산자가 더 우세하기 때문이다. 꺼내는 과정을 모두 마치면 해당 연산자를 넣는다(ReturnPriority에 대한 코드는 각자가 보길 바란다.). 모든 문자에 대해 이 과정을 마치면 버퍼에는 마지막 피연산자가 있으므로 이를 넣어주고 스택에 남은 모든 연산자를 꺼내어 큐에 넣어준다.

스택에서 푸쉬와 팝이 이루어지지만 전체 중위표기식의 길이를 n이라 할 때, 이것보단 미미한 수이므로 시간복잡도는 \(O(n)\)이다.

이렇게 바꾼 후위표기식을 연산해보자. 

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
public static int ReturnPrice(Queue<String> q)
{
    Stack<Integer> stack = new Stack<>();
    while(!q.isEmpty())
    {
        String s = q.poll();
        try{
            int n = Integer.parseInt(s);
            stack.push(n);
        }catch(NumberFormatException e)
        {
            int n2 = stack.peek();
            stack.pop();
            int n1 = stack.peek();
            stack.pop();
            if(s.equals("+"))
                stack.push(n1+n2);
            else if(s.equals("-"))
                stack.push(n1-n2);
            else
                stack.push(n1*n2);
        }
    }
    return Math.abs(stack.peek());
}
연산은 간단하다 큐에서 원소들을 하나씩 빼서 숫자인 경우 스택에 넣는다. 만약 연산자인 경우 스택에서 두 수를 꺼내어 연산을 해준 뒤 다시 스택에 넣어주면 된다. 큐가 비어있으면 스택에 남은 원소 하나가 결과값이다(이 코드를 작성할 때 첫번째로 꺼내는 수가 n1이 아니라 n2라는 것에 주의하자.).

이 부분의 시간복잡도 역시 \(O(n)\)이라 볼 수 있다. 최종 시간복잡도는 \(O(n)\)이다.

테스트



후위표기식으로 변환하는 방법과 연산을 다 까먹어서 다시 공부하는데 애를 먹었다. 대학교 2학년 때 과제만 치중해서 원리를 제대로 공부하지 못한 내 자신이 살짝 원망스럽다. 그래도 이번 기회에 제대로 공부했으니 앞으로는 잊지 말아야겠다.