CODEKATA : 99 ~ 104

99번 롤케이크 자르기

/*
문제 분석
1. 정보
    - 철수는 롤케이크를 두 조각으로 잘라 동생과 한 조각씩 나눠 먹으려고 한다.
    - 해당 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있다.
    - 철수와 동생은 롤케이크를 나눠먹으려 하는데, 그들은 크기보다 위에 올려진 토핑의 종류에 더 관심이 많다.
    - 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이, 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나눠진 것으로 간주한다.
    
2. 목표
     - 롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열이 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return
     
3. 제약 조건
    - 1 <= 토핑의 길이 <= 1000000
        - 1 <= 토핑의 원소 <= 10000

풀이
1. 아이디어
    - 누적합을 사용해 토핑의 개수를 구하여 푼다
        - sum[i] = i번째 토핑까지 포함 했을 때의 토핑의 개수
            - 예를 들어 [1,2,2,3,1,4,1,2] 가 들어왔을 경우
                - 누적합은 A[] = [1,2,2,3,3,4,4,4]이다.
                - 거꾸로도 구해보면 B[] = [1,2,3,3,4,4,4,4] 이다.
                - 이걸 뒤집으면 [4,4,4,4,3,3,2,1]이 나온다.
                - A[] = [1,2,2,3,3,4,4,4]
                - B[] = [4,4,4,4,3,3,2,1]을 통해 구할 수 있겠다.
                - 여기서 i번째를 기준으로 자른다면, A[i]의 값과 B[i + 1]의 값이 같으면 동일한 양의 토핑이 들어가 있으므로, count++해준다.
        - 이후 count를 return한다.
*/

import java.util.*;

class Solution {
        public int solution(int[] topping) {
            int[] A = new int[topping.length];
            int[] B = new int[topping.length];
            Set<Integer> set = new HashSet<>();
            for (int i = 0, count = 0; i < topping.length; i++) {
                if (!set.contains(topping[i])) {
                    set.add(topping[i]);
                    count++;
                }
                A[i] = count;
            }

            set.clear();
            for (int i = topping.length - 1, count = 0; i >= 0; i--) {
                if (!set.contains(topping[i])) {
                    set.add(topping[i]);
                    count++;
                }
                B[i] = count;
            }


            int answer = 0;
            for (int i = 0; i < topping.length - 1; i++) {
                if (A[i] == B[i + 1]) {
                    answer++;
                }
            }

            return answer;
        }
    }

100번 숫자 변환하기

/*
문제 분석
1. 정보
    - 자연수 x를 y로 변환하려고 한다. 사용할 수 있는 연산은 다음과 같다.
    - x에 n을 더한다
    - x에 2를 곱한다
    - x에 3을 곱한다

2. 목표
    - 자연수 x,y,n이 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return
3. 제약 조건
    - 1 <= x <= y <= 1000000
    - 1 <= n < y

풀이
1. 아이디어
    - BFS 사용
        - dp[i] : i번째 수를 만드는데 필요한 최소 연산 횟수
        - i : x ~ y - n까지
            - 만약 dp[i] = Integer.MAX_VALUE, continue;
            - 아니라면
                - 만약 i + n이 y보다 작다면
                    - dp[i + n] = Math.min(dp[i] + 1, dp[i + n])
                - 만약 i * 2가 y보다 작다면
                    - dp[i * 2] = Math.min(dp[i] + 1, dp[i * 2])
                - 만약 i * 3가 y보다 작다면
                    - dp[i * 3] = Math.min(dp[i] + 1, dp[i * 3])
         - dp[y]를 return
 */

import java.util.Arrays;

class Solution {
        public int solution(int x, int y, int n) {
            int[] dp = new int[y + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[x] = 0;
            for (int i = x; i < y; i++) {
                if (dp[i] == Integer.MAX_VALUE) {
                    continue;
                }

                if (i + n <= y) {
                    dp[i + n] = Math.min(dp[i] + 1, dp[i + n]);
                }

                if (i * 2 <= y) {
                    dp[i * 2] = Math.min(dp[i] + 1, dp[i * 2]);
                }

                if (i * 3 <= y) {
                    dp[i * 3] = Math.min(dp[i] + 1, dp[i * 3]);
                }
            }
            return dp[y] == Integer.MAX_VALUE ? -1 : dp[y];
        }
    }

101번 2개 이하로 다른 비트

/*
문제 분석
1. 정보
    - 양의 정수 x에 대한 함수 f(x)는 다음과 같다.
        - x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
2. 목표
    - 정수가 담긴 배열이 주어질때, 해당 배열의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return
3. 제약 조건
    - 1 <= 정수가 담긴 배열 <= 100000
    - 0 <= numbers의 모든 수 <= 10^15

풀이
1. 아이디어
     - x가 짝수인 경우, 마지막 비트는 반드시 0이다. 따라서 x + 1이 가장 가까운 수가 된다,
     - x가 홀수인 경우
        - 만약 x가 7이라면, 0111이다.
        - 해당 값과 조건에 맞고 가장 가까운 값은 11 : 1011이다.
        - 여기서 알 수 있는 점은 가장 오른쪽에 있는 0을 1로 바꾸고, 바로 뒤의 1을 0으로 바꾸면 해당 값이 최소값이다.
     - 즉
         - x가 짝수인 경우 x + 1값 저장
         - x가 홀수인 경우
            - x를 2진법으로 바꾸었을때 가장 오른쪽에 있는 0을 찾기 위해서
                - mask = 1로 설정
                - x와 mask를 & 하여 0이 나온다면 해당 bit가 0이라는 뜻
                    - 즉 (x & mask) != 0 동안
                        - mask << 1씩 증가
                 - 0의 위치를 mask를 통해 구하였고
                 - mask를 이용해 mask자리는 0, mask >> 1 자리는 반대로 바꾸어 주면 최솟값 구하기 가능
                    - (x | mask) & ~(mask >> 1);
*/

class Solution {
        public long[] solution(long[] numbers) {
            long[] answer = new long[numbers.length];
            for (int i = 0; i < numbers.length; i++) {
                long x = numbers[i];

                if (x % 2 == 0) {
                    answer[i] = x + 1;
                }else{
                    long mask = 1;
                    while ((x & mask) != 0) {
                        mask <<= 1;
                    }
                    
                    answer[i] = (x | mask) & ~(mask >> 1);
                }
            }

            return answer;
        }
    }

102번 다리를 지나는 트럭

/*
문제 분석
1. 정보
    - 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 한다.
    - 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하 까지의 무게를 견딜 수 있다.
    - 단 다리에 완전히 오르지 않은 트럭의 무게는 무시한다
2. 목표
    - 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어질 때, 다리를 건너는데 필요한 최소 시간을 return
3. 제약 조건
    - 1 <= bridge_length <= 10000
    - 1 <= weight <= 10000
    - 1 <= truck_weights의 길이 <= 10000
        - 1 <= truck_weights <= weight

풀이
1. 아이디어
    - 큐를 사용해 다리 위에 올라가 있는 트럭들을 관리
        - 1초에 한 칸씩 가므로, 올라 갔을 때의 시간을 기준으로 다리를 다 건넜다면, 큐에서 제거한다.
        - 만약 다리 위에 올라가 있는 트럭들의 무게 합 + 올라갈 트럭의 무게가 다리가 버틸 수 있는 무게 w 보다 작거나 같다면, 트럭을 큐에 넣는다.
        - 무게 w보다 크다면, 해당 트럭은 기다린다.
    - 모든 트럭이 다리위에 올라갔다면
        - 큐가 빌때까지 시간을 ++
            - 1초에 한 칸씩 가므로, 올라 갔을 때의 시간을 기준으로 다리를 다 건넜다면, 큐에서 제거한다.
*/

import java.util.*;

class Solution {
        public int solution(int bridge_length, int weight, int[] truck_weights) {
            Queue<Integer> queue = new LinkedList<>();
            int answer = 0;
            int wSum = 0;
            int inIdx = 0;
            int outIdx = 0;

            while (inIdx < truck_weights.length) {
                 if (!queue.isEmpty() && answer - queue.peek() == bridge_length) {
                    wSum -= truck_weights[outIdx++];
                    queue.poll();
                }
                if (wSum + truck_weights[inIdx] <= weight) {
                    wSum += truck_weights[inIdx];
                    queue.add(answer);
                    inIdx++;
                }
                answer++;
            }

            while (!queue.isEmpty()) {
                if (answer - queue.peek() == bridge_length){
                    queue.poll();
                }
                answer++;
            }

            return answer;
        }
    }

103번 가장 큰 수

/*
문제 분석
1. 정보
    - 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 만들어 return
2. 목표
    - 0 또는 양의 정수가 담긴 배열이 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 만들어 return
3. 제약 조건
    - 1 <= 배열의 길이 <= 100000
    - 0 <= 배열의 원소 <= 1000
    - 문자열로 바꿔 return

풀이
1. 아이디어
    - 배열의 길이가 최대 100000만이라 브루트포스를 사용할 수는 없다고 판단.
    - 결국 얼마나 앞에 큰 숫자 순서대로 넣냐가 관건
        - 하지만 9 와 10이 있을 경우, 앞에 9를 넣어야 숫자가 더 커짐
        - 그렇다면 910 과 109를 비교하여 더 큰쪽이 앞으로 가게?
            - 즉, 두 숫자를 이어 붙여 더 큰 숫자가 앞으로 갈 수 있도록 정렬
    - 주의할 점 : 가장 앞의 숫자가 0이라면, 0을 return 해주어야함.
*/

import java.util.Arrays;

class Solution {
        public String solution(int[] numbers) {
            String[] nums = new String[numbers.length];
            for (int i = 0; i < numbers.length; i++) {
                nums[i] = String.valueOf(numbers[i]);
            }

            Arrays.sort(nums, ((o1, o2) -> {
                int left = Integer.parseInt(o1 + o2);
                int right = Integer.parseInt(o2 + o1);
                return right - left;
            } ));

            StringBuilder sb = new StringBuilder();

            for (String num : nums) {
                sb.append(num);
            }

            return sb.toString().startsWith("0") ? "0" : sb.toString();
        }
    }

104번 소수 찾기

/*
문제 분석
1. 정보
    - 한자리 숫자가 적힌 종이 조각들이 흩어져 있다.
    - 흩어진 종이 조각을 붙여 소수를 몇개 만들 수 있는지 알아내려 한다.
    
2. 목표
    - 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을때, 종이 조각으로 만들 수 있는 소수가 몇 개 인지 return
3. 제약 조건
    - 1 <= numbers 길이 <= 7
    - 0 <= numbers의 원소 <= 9
    - "013"은 0,1,3 숫자가 적힌 종이 조각이 흩어져 있다는 의미

풀이
1. 아이디어
    - 최대 길이는 7
        - 브루트포스를 통해 모든 가능한 숫자의 조합을 찾음
        - 해당 숫자가 소수인지 판별하고, 소수이면 소수 모음에 저장
        - 소수 모음의 길이를 return
    - compute() 메서드를 길이가 1부터 해당 numbers의 길이까지 모두 구함
*/

import java.util.*;

class Solution {

        Set<Integer> set = new HashSet<>();
        boolean[] visited;

        public int solution(String numbers) {
            visited = new boolean[numbers.length()];

            for (int i = 1; i <= numbers.length(); i++) {
                compute("", numbers, 0, i);
            }
            
            for (Integer i : set) {
                System.out.println(i);
            }
            return set.size();
        }

        private void compute(String s, String numbers, int idx, int max) {
            if (idx == max) {
                int num = Integer.parseInt(s);
                if (isPrime(num)) {
                    set.add(num);
                }
                return;
            }

            for (int i = 0; i < numbers.length(); i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    compute(s + numbers.charAt(i), numbers, idx + 1, max);
                    visited[i] = false;
                }
            }
        }

        private boolean isPrime(int n) {
            if (n < 2) {
                return false;
            }

            for (int i = 2; i <= Math.sqrt(n); i++) {
                if (n % i == 0) {
                    return false;
                }
            }

            return true;
        }
    }