스택의 활용(연산 표기법 : 중위 표기법, 전위 표기법, 후위 표기법) + 큐 연습문제

수식을 표현하는 방법에 3가지가 있습니다.

1. 중위표기법(infix) : 연산자가 안에 있어서 infix라고 부릅니다. ex) 2 + 3 * 5
2. 전위 표기법(prefix) : 연산자가 앞에 있어서 prefix라고 부릅니다. + 2 * 3 5
3. 후위 표기법(postfix) 연산자가 피 연산자 다음에 있어서 postfix라고 부릅니다. ex) 2 3 5 * +

💡 후위표기법이 필요한 이유

우리가 익숙하게 사용하는 중위표기법은 컴퓨터가 이해하기 힘들다.

컴퓨터가 이해하기 쉽게 도와주는 방법이 후위표기법을 사용하는 이유이다.

 

infix → postfix로 변환 방법

1. 각각의 연산에 괄호를 친다.
2. 연산자의 오른쪽 괄호 다음으로 연산자를 이동한다.
3. 괄호 지운다.

infix -> postfix 변환방법

infix를 posfix로 변환하는 방벙(코드)

스택을 활용해서 문제를 해결한다.

1. 피 연산자는 순서대로 출력한다.
2. 연산자는 stack에 넣는다.
3. 스택에 연산자가 있고 stack의 top이 다음에 들어올 연산자보다 우선순위가 높거나 같은 연산자는 모두 pop을 한 후 push를 한다.
4. 수식이 끝나면 모든 연산자를 pop 한다.

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        String s = "2*3+5";

        for(int i = 0; i < s.length(); i++) {
            if(Character.isDigit(s.charAt(i))) { // 문자열 순서대로 숫자인지 확인
                sb.append(s.charAt(i));
            }
            else { // 숫자가 아닐경우(연산자 일경우)
                while(!stack.isEmpty() && checkPriority(stack.peek()) >= checkPriority(s.charAt(i))) {
                    sb.append(stack.pop());
                }
                stack.push(s.charAt(i));
            }
        }
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        System.out.println(sb);

    }
    public static int checkPriority(char c) {
        if(c == '+' || c == '-') return 1;
        return 2;
    }
}

 

스택을 활용한 연습문제

 

문제에서 짝을 맞히는 느낌의 문제가 나오면 스택을 사용해나라고 의심을 해봐야 합니다.(물론 100%는 아닙니다)

스택을 써야 풀 수 있는지 판단하고 스택으로 풀 수 있을 경우 스택을 활용해서 문제를 해결하면 됩니다.

대표적인 짝 맞추는 문제 괄호 문제가 있습니다.

문제 1 괄호

https://www.acmicpc.net/problem/9012

9012번: 괄호

 

💡 문제 1번 풀이

( 가 들어왔을 때를 기준으로 생각을 하자!

만약 스택이 비어있으면 괄호를 추가하면 된다.

스택이 비어있지 않는 상태에서 스택의 Top 이 “(” 일경우 현재 괄호가 “)” 면 스택을 pop을 한다.

아닐 경우 push를 진행한다.

스택의 최상단이 “)” 일 경우 그냥 스택에 push 한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < n; i++) {
            char[] c = br.readLine().toCharArray();
            Stack<Character> stack = new Stack<>();

            for(int j = 0; j < c.length; j++) {
                if(stack.isEmpty()){ // 스택이 비어있는 경우 스택에 괄호 추가
                    stack.push(c[j]);
                    continue; // 조금이나마 빠른 연산을 위해 스택에 추가한 순간 아래 코드는 건너 뜀
                }
                if(stack.peek() == '('){ // 스택의 최상단이 ( 일경우
                    if(c[j] == ')') stack.pop(); // 들어온 값이 ) 이면 pop
                    else stack.push(c[j]); // 아니면 push

                }
                else {
                    stack.push(c[j]); // 스택 최상단이 ) 일경우 그냥 푸시
                }
            }
            if(stack.isEmpty()) sb.append("YES").append("\\n");
            else sb.append("NO").append("\\n");
        }
        System.out.println(sb);
    }
}

 

사실 위 코드에서 좀 더 성능 최적화를 진행할 수 있다.

스택이 비어있거나 닫는 괄호가 최상단일 때 다음 괄호가 닫는 괄호이면 그냥 연산을 안 하고 NO를 출력하면 된다.

-> 올바른 괄호인지 판단하고 출력하는 부분을 함수로 만들면 바로 return이 가능하다.

 

큐를 활용한 연습문제

큐의 특성상 큐를 활용한 문제는 보편적으로 빼고 순서를 마지막으로 넣는 반복적인 행위? 의 문제가 나오면 큐를 해결해야 한다는 생각을 가질 수 있습니다. (ex 요세푸스) https://namu.wiki/w/요세푸스 문제

큐의 이러한 특성으로 추후 BFS에서 많이 사용됩니다. (BFS에서 다시 다뤄볼 예정)

 

문제2 요세푸스 문제 0

https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

 

문제 2번 코드

💡 문제 2번 풀이 큐를 활용했을 때 정말 쉽게 문제를 풀 수 있다. queue에 숫자를 집어넣는다. K번째가 아닐 때까지 queue에 숫자를 빼서 다시 집어넣는다. K번째가 될 때마다 queue에 있는 숫자를 빼서 출력한다. 이과정을 queue가 비어있을 때까지 반복한다.

 

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Queue<Integer> queue = new LinkedList<>();
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        for(int i = 1; i <= N; i++) {
            queue.add(i);
        }
        sb.append('<');
        while(queue.size() > 1) {
            for(int i = 0; i < K - 1; i++) { // queue를 빼서 맨 밑으로 넣는다.
                queue.offer(queue.poll());
            }
            sb.append(queue.poll()).append(", ");
        }
        sb.append(queue.poll()).append('>'); // K 번째 숫자를 빼서 출력한다.
        System.out.println(sb);
    }
}