백준 길라잡이 (1-4) 기초자료구조(2) 문제풀이

1-4. 기초 자료구조 (2)

A – 9012 괄호 https://www.acmicpc.net/problem/9012

B – 1874 스택 수열 https://www.acmicpc.net/problem/1874

C – 1158 조세퍼스 문제 https://www.acmicpc.net/problem/1158

D – 1966 프린터 큐 https://www.acmicpc.net/problem/1966

E – 5430 AC https://www.acmicpc.net/problem/5430

 

💫프린터큐, 💫AC 문제 다시 한 번 풀어보기 

// 스택수열은 바로 풀었지만, 헷갈리니까 다시 한 번 보기!

 

A번)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

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++){
            String st = br.readLine();
            Stack<Character> stack = new Stack<>();
            String result = "YES";
            for(int j=0; j<st.length(); j++){
                char temp = st.charAt(j);
                if(temp == '('){
                    stack.add(temp);
                }else{
                    if(stack.empty()){
                        result = "NO";
                        break;
                    }
                    stack.pop();
                }
            }
            if(stack.size() > 0){
                result = "NO";
            }
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}

 

 

B번)

package baekjoon.part01_04;

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

/*
 백준 길라잡이 Part01-04 기초 자료구조
 1874번 : 스택 수열
 */
public class Num1874_스택수열 {

    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 n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] number = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        for(int i=0; i<n; i++){
            number[i] = i+1;
        }

        StringBuilder sb = new StringBuilder(); // *** 이거 사용하기!!!
        Stack<Integer> stack = new Stack<>();
        int idx = 0;
        int k = 0;
        while(idx < arr.length && k < number.length){

            if(arr[idx] == number[k]){
                stack.push(arr[idx]);

                sb.append("+\n");
                while(!stack.isEmpty() && stack.peek() == arr[idx]){
                    stack.pop();
                    sb.append("-\n");
                    idx++;
                }
                k++;
            }
            else{
                if(!stack.isEmpty() && arr[idx] < stack.peek()){
                    break;
                }

                stack.push(number[k++]);
                sb.append("+\n");
            }
        }

        if(stack.isEmpty()){
           bw.write(sb.toString());
        }
        else{
            bw.write("NO");
        }

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

}

공책에 number(1부터 n까지 순서대로 저장한 배열) 과 arr를 그려놓고 어떻게 이동해야 할지 그려보며 푸니까 쉽게 풀 수 있었다.

어떤 상황에 stack에 push하고 어떤 상황에 pop할지 생각해 보고, 

pop할 수 없는 상황에서 현재 stack.peek()값이 arr[idx] 값 보다 크다면 원하는 배열을 만들 수 없으므로 break를 걸었다.

마지막으로 제출시 자꾸 출력초과가 떴는데 바보처럼 StringBuilder를 사용하지 않고 바로 bw에 저장함과 System.out을 함께 사용해서 오류가 났었다... 다시 위와 같이 수정하니 잘 제출 되었다.

 

 

C번)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();

        LinkedList<Integer> circle = new LinkedList<>();
        for(int i=1; i<=n; i++){
            circle.add(i);
        }

        int idx = 0;
        sb.append("<");
        while(!circle.isEmpty()){
            idx = (idx + k - 1) % circle.size();
            sb.append(circle.remove(idx));
            if(!circle.isEmpty()){
                sb.append(", ");
            }
        }
        sb.append(">");
        System.out.println(sb);
    }
}

 

 

D번)

package baekjoon.part01_04;

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

// 백준 길라잡이 1-4 기초 자료구조 : 1966번 프린터 큐
public class Num1966_프린터큐 {

    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 testCase = Integer.parseInt(br.readLine());
        for(int i=0; i<testCase; i++){

            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());

            LinkedList<Integer> que = new LinkedList<>(); // queue 대신 이용 : 뒤에 i번째를 get 해야하므로
            LinkedList<Integer> num = new LinkedList<>();
            for(int j=0; j<n; j++){
                que.add(Integer.parseInt(st.nextToken()));
                num.add(j);
            }

            int count = 0;
            while(!que.isEmpty()){

                int front = que.peek();
                int idx = num.peek();
                boolean isMax = true;

                for(int j=0; j<que.size(); j++){
                    if(front < que.get(j)){
                        isMax = false;
                        for(int k=0; k<j; k++){
                            que.add(que.remove());
                            num.add(num.remove());
                        }
                        break;
                    }
                }

                if(isMax){
                    count++;
                    if(idx == m){
                        bw.write(count + "\n");
                        break;
                    }
                    que.remove();
                    num.remove();
                }

            }
        }

        bw.close();

    }

}

 

 

 

E번)

package baekjoon.part01_04;

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

// 백준 길라잡이 1-4) 기초 자료구조(2) : 5430번 - AC
public class Num5430_AC {

    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());
        for(int t = 0; t < T; t++){
            boolean error = false;

            String p = br.readLine();
            int n = Integer.parseInt(br.readLine());

            StringTokenizer st = new StringTokenizer(br.readLine(),"[,]"); // StringTokenizer 은 구분자를 하나의 char씩 다 구분해서 분할해준다
            Deque<Integer> deque = new ArrayDeque<>();
            for(int i=0; i<n; i++){
                deque.addLast(Integer.parseInt(st.nextToken()));
            }

            p = p.replace("RR", "");

            boolean reverse = false;
            for(int c = 0; c < p.length(); c++){
                if(p.charAt(c) == 'R'){ // *** deque를 이용하여 실제로 바꾸지 않고 어디가 앞인지만 구분해준다. ***
                    reverse = !reverse;
                }else{ // 'D'
                    if(deque.isEmpty()){
                        error = true;
                        break;
                    }
                    if(reverse){
                        deque.removeLast();
                    }else{
                        deque.removeFirst();
                    }
                }
            }
            if(error){
                bw.write("error\n");
            }
            else{
                bw.write("[");
                while(!deque.isEmpty()){
                    if(reverse){
                        bw.write(deque.removeLast().toString());
                    }else{
                        bw.write(deque.removeFirst().toString());
                    }
                    if(!deque.isEmpty()){
                        bw.write(",");
                    }
                }
                bw.write("]\n");
            }
        }

        bw.close();
    }

}