10799번(스택), 10816번(이진 탐색), 2805번(이진 탐색)

10799번

 

스택을 응용한 문제이다

 

괄호들의 묶음을 문자열 한 줄로 입력 받은 후 이를 하나씩 쪼개 문자열 배열로 만든다

for문을 돌며 배열에서 "("이 나오면 스택에 push

")"이 나올 경우 스택에서 pop

 

만약 ")"의 앞이 "("였다면 여는 괄호와 닫는 괄호의 인접한 쌍이므로 레이저이다

만약 ")"의 앞이 ")"였다면 쇠막대기가 끝났다는 의미이다

 

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));
        String str = br.readLine();
        Stack<String> stack = new Stack<>();
        String [] str2 = str.split("");
        int stick = 0;
        for(int i = 0; i< str2.length; i++) {
            if(str2[i].equals("(")) { // 열린 괄호라면 스택에 넣어줌
                stack.push(str2[i]);
            } else if (str2[i].equals(")")) { // 닫힌 괄호가 나오는 경우 레이저 or 쇠막대기 끝 
                // 레이저로 사용한 열린 괄호를 삭제 or 쇠막대기의 시작으로 사용한 열린 괄호 삭제
                stack.pop();
                if(str2[i-1].equals("(")) { // 직전 괄호가 여는 괄호라면 레이저가 나오는 경우이다
                    stick += stack.size(); // 스택의 크기만큼의 개수로 쇠막대기가 잘림 
                } else { // 그 외는 쇠막대기가 끝나는 경우이다 (직전에 닫는 괄호가 있음)
                    stick += 1; // 쇠막대기가 끊기면 쇠막대기의 조각이 하나씩 더 생김
                }
            }
        }
        System.out.println(stick);
    }
}

 

10816번

 

 

이번에는 이진 탐색 메서드를 직접 구현하지 않고 Arrays.binarySearch()를 사용하였다

해당 메서드는 찾는 값이 있으면 해당 인덱스를 반환하고 찾지 못하면 음수를 반환

숫자 카드에서 동일한 숫자의 빈도수를 알아야 하므로 HashMap을 사용하였다

 

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

public class Solution {
    static int [] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Map <Integer,Integer> map= new HashMap<>();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        arr = new int[n];
        for(int i = 0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for(int i =0; i<n; i++) {
            if(map.containsKey(arr[i])) {
                map.put(arr[i],map.get(arr[i])+1);
            } else {
                map.put(arr[i],1);
            }
        }
        Arrays.sort(arr);
        int m = Integer.parseInt(br.readLine());
        int [] arr1 = new int[m];
        st= new StringTokenizer(br.readLine()," ");
        for(int i = 0; i<m; i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
            int result = Arrays.binarySearch(arr,arr1[i]);
            if(result<0) {
                sb.append(0).append(" ");
            } else {
                sb.append(map.get(arr1[i])).append(" ");
            }
        }
        System.out.println(sb);
    }
}

 

2805번

 

 

이진 탐색의 대상은 절단기에 설정할 수 있는 높이이다

절단기에 설정할 수 있는 높이의 최솟값은 0, 최댓값은 나무의 높이의 최대값으로 설정하면 된다

상근이가 가져갈 수 있는 나무의 길이는 나무의 길이에서 절단기에 설정한 높이를 뺀 값이다

 

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 n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int [] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int min = 0;
        int max = arr[arr.length-1];
        int mid = 0;
        while(min<=max) {
            // 범위 내에서 중간 값(=자르는 위치)을 구한다
            mid = (min+max)/2;
            long tree = 0;
            for(int i = 0; i<arr.length; i++) {
                long cut = arr[i] - mid; // tree 잘린 길이 = tree 높이 - 자르는 위치(mid)
                if(cut < 0) {
                    cut = 0; // 자르는 위치가 주어진 나무의 높이보다 큰 경우 잘린 길이는 0이 되어야 함
                }
                tree += cut; // 자른 나무 길이 합
            }
            if(tree < m) { // 자른 나무 길이의 합이 m보다 작다는 것은 자르는 위치가 높다는 의미이므로 높이를 낮춰서 자른 나무의 길이가 길어지도록 해야 한다
                max = mid-1;
            } else { // 자른 나무 길이의 합이 m보다 크다는 것은 자르는 위치가 낮다는 의미이므로 높이를 높여서 자른 나무의 길이가 짧아지도록 해야 한다
                min = mid+1;
            }
        }
        System.out.println(max);
    }
}