매일 Algorithm

백준 17299번

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class problem474 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int size = in.nextInt();
        int[] arr = new int[size];
        int[] result = new int[size];
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        StringBuilder output = new StringBuilder();
        for (int i = 0; i < size; i++) {
            arr[i] = in.nextInt();
        }

        // 배열 숫자의 빈도수 저장
        for (int i = 0; i < size; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }

        // map 객체 현황
        // 1,3
        // 2,2
        // 3,1
        // 4,1

        // 배열 입력
        // 1 1 2 3 4 2 1
        for (int i = 0; i < size; i++) {
            while (!stack.isEmpty() && 
            		map.get(arr[i]) > map.get(arr[stack.peek()])) {
                result[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1; // -1 초기화
        }

        for (int i : result) {
            output.append(i).append(" ");
        }
        System.out.println(output.toString());

    }
}

백준 1463번

import java.util.Scanner;

public class problem475 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int num = in.nextInt();

        // dp 문제에서는 배열을 한개 더 크게만든다.
        int[] dp = new int[num + 1];


        // dp에서는 초기값 초기화가 중요
        dp[1] = 0;


        // 입력값이 3일 경우, 1을 빼면 연산횟수 2회 3을 나누면 1회
        for (int i = 2; i <= num; i++) {
            dp[i] = dp[i - 1] + 1;

            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }

        System.out.println(dp[num]);
    }
}