11 to 9, Day 21

Today, ToDoList

• 백준 코드 퀴즈
• 스택 자료구조

---

백준 코드 퀴즈

fast A+B

import java.io.*;

class Main {

    public static void main(String[] args) {

        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            int t = Integer.parseInt(reader.readLine());
            try (BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))){
                for ( int i = 0; i < t; i++ ) {
                    String[] nums = reader.readLine().split(" ");
                    int a = Integer.parseInt(nums[0]);
                    int b = Integer.parseInt(nums[1]);
                    writer.write(String.valueOf(a+b));
                    writer.newLine();
                }
                writer.flush();
            } catch (IOException e) {
                e.printStackTrace();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

    }
}

---

스택 자료구조

• FILO / LIFO
• push(), pop(), peek(), top() 모두 시간복잡도 O(1)

package stack;

import java.util.Stack;

public class MyStack {

    Stack<Integer> stack = new Stack<>();

    //스택 뒤집기 - 순회
    //또 다른 자료구조 사용 필요
    //시간 복잡도 O(N), 공간 복잡도 O(N)
    public void reverse1() {
        int length = stack.size();
        Stack<Integer> newStack = new Stack<>();

        while (!stack.empty()) {
            newStack.push(stack.pop());
        }
        stack = newStack;
    }

    //스택 뒤집기 - 재귀
    //또 다른 자료구조 사용하지 않고도 가능
    //시간 복잡도 O(N^2), 공간 복잡도 O(N)
    public void reverse2() {
        if (stack.isEmpty()) {
        } else {
            int temp = stack.pop();
            reverse2();
            reverseRecursive(stack, temp);
        }
    }

    private void reverseRecursive(Stack<Integer> stack, Integer num) {
        if (stack.isEmpty()) {
            stack.push(num);
        } else {
            int temp = stack.pop();
            reverseRecursive(stack, num);
            stack.push(temp);
        }
    }


    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.stack.push(1);
        myStack.stack.push(2);
        myStack.stack.push(3);

        //myStack.reverse1();
        myStack.reverse2();

        System.out.println(myStack.stack.pop());
        System.out.println(myStack.stack.pop());
        System.out.println(myStack.stack.pop());
        System.out.println(myStack.stack.isEmpty());
    }
}

package stack;

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class BracketCount {

    //주어진 수식의 괄호짝이 맞는지 체크
    //시간복잡도 O(N) , 공간복잡도 O(N)
    public boolean solution1(String expression) {
        List<Character> open = Arrays.asList('(','{','[');
        List<Character> close = Arrays.asList(')','}',']');
        Stack<Character> stack = new Stack<>();

        char[] chars = expression.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if ( open.contains(chars[i]) ) {
                stack.push(close.get(open.indexOf(chars[i])));
            } else if ( close.contains(chars[i]) ) {
                if ( stack.isEmpty() || stack.pop() != chars[i] ) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        BracketCount bracketCount = new BracketCount();
        System.out.println(bracketCount.solution1("[{(1+2)-1}+10]"));
        System.out.println(bracketCount.solution1("[[{(1+2)-1}+10]"));
        System.out.println(bracketCount.solution1("[{(1+2)-1)+10]"));
    }
}