10818번(스택), 18866번(큐), 1654번(이진 탐색)

10818번

 

스택의 개념에 대해 확인하는 문제이다

 

 

주어지는 명령어를 문자열로 받은 후 이것이 제시된 명령어와 동일한지 비교하여 동일한 경우 명령을 수행하도록 한다

 

가장 중요한 점은 push 명령어는 push + 숫자로 구성되어 있으므로 공백을 기준으로 나눠서 생각해줘야 한다. 현재 숫자는 문자열이기 때문에 정수형으로 변환이 필요하다

 

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

public class Practice {
    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();
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i<n; i++) {
            String str = br.readLine();
            if(str.startsWith("push")) { // 입력 받은 문자열이 push 로 시작한다면
                String [] part = str.split(" "); // 공백을 기준으로 문자열을 나눠 뒷부분을 문자열에서 정수로 변환
                int m = Integer.parseInt(part[part.length-1]);
                stack.push(m);
            } else if(str.equals("top")) {
                if(stack.empty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(stack.peek()).append("\n");
                }
            } else if(str.equals("size")) {
                sb.append(stack.size()).append("\n");
            } else if(str.equals("empty")) {
                if(stack.empty()) {
                    sb.append(1).append("\n");
                } else {
                    sb.append(0).append("\n");
                }
            } else if(str.equals("pop")) {
                if(stack.empty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(stack.pop()).append("\n");
                }
            }
        }
        System.out.println(sb);
    }
}

 

18866번

 

요세푸스 순열은 큐를 사용하여 푸는 문제이다

 

 

설명은 그림에 첨부

 

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int num = 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 <= num; i++) {
            queue.offer(i);
        }
        while (queue.size() > 0) {
            for (int i = 0; i < k - 1; i++) {
                int tmp = queue.poll();
                queue.offer(tmp);
            }
            sb.append(queue.poll()).append(", ");
        }

        sb.delete(sb.length()-2,sb.length()).insert(sb.length(), ">");
        System.out.println(sb);
    }
}

 

1654번

 

이진 탐색을 응용한 문제이다

 

 

지금까지 푼 이진 탐색의 문제들은 어떤 값(key)에 대한 배열의 특정 인덱스를 찾기 위한 것이였다하지만 이번에는 랜선의 길이를 이진 탐색해야 한다

 

가지고 있는 랜선에서 길이를 나누기 때문에 가장 긴 길이의 랜선을 먼저 기준으로 설정

처음 시작하는 범위는 min=1, max=가장 긴 랜선의 길이로 설정

 

원하는 갯수보다 잘라진 선들의 개수가 많을 경우 하나의 잘라진 선이 너무 짧다는 의미 >  더 길게 만들 수 있다

min = mid + 1 로 초기화하여 탐색 범위를 줄인다

 

원하는 갯수보다 잘라진 선들의 개수가 적을 경우 하나의 잘라진 선이 너무 길다는 의미 >  더 짧게 만들 수 있다

max = mid - 1로 초기화하여 탐색 범위를 줄인다

 

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

public class Practice {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int [] arr = new int[k];
        for(int i = 0; i<k; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        long min = 1;
        long max = arr[arr.length-1];
        long mid = 0; // 랜선 길이는 자연수므로  최솟값 1로 세팅해야함
        while(min<=max) {
            // 범위 내에서 중간 길이를 구한다
            mid = (min+max)/2;
            long count = 0;
            for(int i = 0; i<arr.length; i++) {
                count += arr[i]/mid; // 자른 개수 합
            }
            if(count < n) { // mid 길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면 자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다
                max = mid-1;
            } else { // mid 길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 크다면 자르고자 하는 길이를 늘리기 위해 최소 길이를 늘린다
                min = mid+1;
            }
        }
        System.out.println(max);
    }
}