[Coding Test] Baekjoon 알고리즘 기초 1/2 (1)

1. 200 - 자료구조1

1-1. 스택 (10828)

import java.util.*;
import java.io.*;

public class P10828_스택 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        Stack<Integer> stack = new Stack<>();

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();

            if (str.equals("push")) {
                stack.push(Integer.parseInt(st.nextToken()));
            } else if (str.equals("pop")) {
                if (stack.isEmpty()) {
                    bw.write("-1\n");
                } else {
                    bw.write(stack.pop() + "\n");
                }
            } else if (str.equals("size")) {
                bw.write(stack.size() + "\n");
            } else if (str.equals("empty")) {
                if (stack.empty()) {
                    bw.write("1\n");
                } else {
                    bw.write("0\n");
                }
            } else if (str.equals("top")) {
                if (stack.empty()) {
                    bw.write("-1\n");
                } else {
                    bw.write(stack.peek() + "\n");
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

---

1-2. 단어 뒤집기 (9093)

import java.io.*;
import java.util.*;

public class P9093 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                char[] arr = st.nextToken().toCharArray();
                for (int j = 0; j < arr.length; j++) {
                    stack.push(arr[j]);
                }

                while (!stack.empty()) {
                    sb.append(stack.pop());
                }

                sb.append(" ");
            }

            bw.write(sb.toString() + "\n");
            sb.setLength(0);
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

---

1-3. 괄호 (9012)

import java.io.*;
import java.io.*;

public class P9012_괄호 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        boolean bl;

        for (int i = 0; i < T; i++) {
            bl = true;
            char[] arr = br.readLine().toCharArray();
            int start = 0;
            int end = 0;

            for (int j = 0; j < arr.length; j++) {
                if (arr[j] == '(') {
                    start++;
                } else {
                    end++;
                }

                if (start < end) {
                    bl = false;
                    break;
                }
            }

            if (!bl || start != end) {
                bw.write("NO\n");
            } else {
                bw.write("YES\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

---

1-4. 스택 수열 (1406)

import java.util.Scanner;
import java.util.Stack;

public class P1874_스택수열 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int value = 1;
        boolean result = true;
        Stack<Integer> stackInt = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();
            if (num >= value) {
                while (num >= value) {
                    stackInt.push(value++);
                    sb.append("+\n");
                }
                stackInt.pop();
                sb.append("-\n");
            } else if (num < value) {
                int n = stackInt.pop();
                if (num < n) {
                    sb.setLength(0);
                    sb.append("NO\n");
                    result = false;
                    break;
                } else {
                    sb.append("-\n");
                }
            }
        }
        if (result) System.out.println(sb);
        else System.out.println(sb);
    }
}

---

1-5. 에디터 (1406)

// iter 사용
import java.io.*;
import java.util.*;

public class P1406_에디터 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        LinkedList<Character> list = new LinkedList<>();

        char[] arr = br.readLine().toCharArray();
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }

        int N = Integer.parseInt(br.readLine());

        ListIterator<Character> iter = list.listIterator();
        while (iter.hasNext()) {
            iter.next();
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();

            if (str.equals("L")) {
                if (iter.hasPrevious()) {
                    iter.previous();
                }
            } else if (str.equals("D")) {
                if (iter.hasNext()) {
                    iter.next();
                }
            } else if (str.equals("B")) {
                if (iter.hasPrevious()) {
                    iter.previous();
                    iter.remove();
                }
            } else if (str.equals("P")) {
                String str1 = st.nextToken();
                iter.add(str1.charAt(0));
            }
        }

        for (char ch : list) {
            bw.write(ch);
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

//stack 사용
import java.io.*;
import java.util.*;

public class P1406_에디터 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        char[] arr = br.readLine().toCharArray();
        int N = Integer.parseInt(br.readLine());

        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            stack1.push(arr[i]);
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();

            if (str.equals("L")) {
                if (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            } else if (str.equals("D")) {
                if (!stack2.isEmpty()) {
                    stack1.push(stack2.pop());
                }
            } else if (str.equals("B")) {
                if (!stack1.isEmpty()) {
                    stack1.pop();
                }
            } else if (str.equals("P")) {
                String str1 = st.nextToken();
                stack1.push(str1.charAt(0));
            }
        }

        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }

        StringBuilder sb = new StringBuilder();
        while (!stack1.isEmpty()) {
            sb.append(stack1.pop());
        }

        bw.write(sb.reverse().toString() + "");

        bw.flush();
        bw.close();
        br.close();
    }
}

---

1-6. 큐 (10845)

import java.io.*;
import java.util.*;

public class P10845_큐 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        Queue<Integer> queue = new LinkedList<>();

        int N = Integer.parseInt(br.readLine());
        int rear = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();

            switch (str) {

                case "push":
                    int num = Integer.parseInt(st.nextToken());
                    queue.add(num);
                    rear = num;
                    break;

                case "pop":
                    if (queue.size() == 0) {
                        bw.write("-1\n");
                    } else {
                        bw.write(queue.poll() + "\n");
                    }
                    break;

                case "size":
                    bw.write(queue.size() + "\n");
                    break;

                case "empty":
                    bw.write((queue.isEmpty() ? 1 : 0) + "\n");
                    break;

                case "front":
                    bw.write((queue.isEmpty() ? -1 : queue.peek()) + "\n");
                    break;

                case "back":
                    bw.write((queue.isEmpty() ? -1 : rear) + "\n");
                    break;
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

---

1-7. 요세푸스 문제 (1158)

import java.io.*;
import java.util.*;

class P1158_요세푸스문제 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Queue<Integer> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        sb.append("<");

        for (int i = 1; i <= N; i++) {
            queue.add(i);
        }

        while (queue.size() != 1) {
            for (int i = 1; i < K; i++) {
                queue.add(queue.poll());
            }
            sb.append(queue.poll() + ", ");
        }
        sb.append(queue.poll());

//        int cnt = 1;
//        int cnt2 = 0;
//        while (!queue.isEmpty()) {
//            if (cnt % K == 0) {
//                cnt2++;
//                if (cnt2 == N) {
//                    sb.append(queue.poll());
//                } else {
//                    sb.append(queue.poll() + ", ");
//                }
//            } else {
//                queue.add(queue.poll());
//            }
//            cnt++;
//        }

        sb.append(">");
        bw.write(sb.toString() + "");

        bw.flush();
        bw.close();
        br.close();
    }
}

---

1-8. 덱 (10866)

import java.io.*;
import java.util.*;

class P10866_덱 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        Deque<Integer> deque = new LinkedList<>();

        int num;
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();

            switch (str) {

                case "push_front":
                    num = Integer.parseInt(st.nextToken());
                    deque.addFirst(num);
                    break;

                case "push_back":
                    num = Integer.parseInt(st.nextToken());
                    deque.addLast(num);
                    break;

                case "pop_front":
                    bw.write((deque.isEmpty() ? -1 : deque.removeFirst()) + "\n");
                    break;

                case "pop_back":
                    bw.write((deque.isEmpty() ? -1 : deque.removeLast()) + "\n");
                    break;

                case "size":
                    bw.write(deque.size() + "\n");
                    break;

                case "empty":
                    bw.write((deque.isEmpty() ? 1 : 0) + "\n");
                    break;

                case "front":
                    bw.write((deque.isEmpty() ? -1 : deque.peekFirst()) + "\n");
                    break;

                case "back":
                    bw.write((deque.isEmpty() ? -1 : deque.peekLast()) + "\n");
                    break;
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

---

2. 201 - 자료구조1 (연습)

2-1. 단어 뒤집기 2 (17413)

import java.io.*;
import java.util.*;

public class P17413_단어뒤집기2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        boolean flag = false;
        char[] arr = br.readLine().toCharArray();

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '<') {
                flag = true;
                while (!stack.isEmpty()) {
                    sb.append(stack.pop());
                }
                sb.append(arr[i]);
            } else if (arr[i] == '>') {
                flag = false;
                sb.append(arr[i]);
            } else if (flag) {
                sb.append(arr[i]);
            } else if (!flag && arr[i] == ' ') {
                while (!stack.isEmpty()) {
                    sb.append(stack.pop());
                }
                sb.append(arr[i]);
            } else if (!flag) {
                stack.push(arr[i]);
            }
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        bw.write(sb.toString() + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

---

2-2. 쇠막대기 (10799)

import java.io.*;
import java.util.*;

public class P10799_쇠막대기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Stack<Character> stack = new Stack<>();
        char[] arr = br.readLine().toCharArray();

        int answer = 0;
        char ch = ' ';
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(') {
                stack.push(arr[i]);
            } else if (arr[i] == ')' && ch == '(') {
                stack.pop();
                answer += stack.size();
            } else if (arr[i] == ')' && ch == ')') {
                answer += 1;
                stack.pop();
            }

            ch = arr[i];
        }

        bw.write(answer + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

---

2-3. 오큰수 (17298)

import java.io.*;
import java.util.*;

public class P17298_오큰수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                if (arr[stack.peek()] < arr[i]) {
                    while (arr[stack.peek()] < arr[i]) {
                        arr[stack.peek()] = arr[i];
                        stack.pop();
                        if (stack.isEmpty()) break;
                    }
                }
                stack.push(i);
            }
        }

        if (!stack.isEmpty()) {
            while (!stack.isEmpty()) {
                arr[stack.peek()] = -1;
                stack.pop();
            }
        }

        for (int i = 0; i < N; i++) {
            bw.write(arr[i] + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

---

2-4. 오등큰수 (17299)

import java.io.*;
import java.util.*;

public class P17299_오등큰수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }

        int[] answer = new int[N];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < N; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                if (map.get(arr[stack.peek()]) < map.get(arr[i])) {
                    while (!stack.isEmpty() && map.get(arr[stack.peek()]) < map.get(arr[i])) {
                        answer[stack.pop()] = arr[i];
                    }
                }
                stack.push(i);
            }
        }

        if (!stack.isEmpty()) {
            while (!stack.isEmpty()) {
                answer[stack.pop()] = -1;
            }
        }

        for (int i = 0; i < N; i++) {
            bw.write(answer[i] + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

---

3. 203 - 자료구조1 (참고)

3-1. 후위 표기식2 (1935)

import java.io.*;
import java.util.*;

public class P1935_후위표기식2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int N = Integer.parseInt(br.readLine());
        char[] arr = br.readLine().toCharArray();

        double[] data = new double[N];
        for (int i = 0; i < N; i++) {
            data[i] = Double.parseDouble(br.readLine());
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= 'A' && arr[i] <= 'Z') {
                stack.push(data[arr[i] - 'A']);
            } else {
                double b = stack.pop();
                double a = stack.pop();
                switch (arr[i]) {
                    case '+':
                        stack.push(a + b);
                        break;
                    case '-':
                        stack.push(a - b);
                        break;
                    case '*':
                        stack.push(a * b);
                        break;
                    case '/':
                        stack.push(a / b);
                        break;
                }
            }
        }

        double result = stack.peek();
        System.out.printf("%.2f", result);
    }
}

---