CODEKATA : 91 ~ 95

91번 기능개발

/*
문제 분석
1. 정보
    - 기능 개선 작업을 수행중. 각 기능은 진도가 100%일 때 서비스에 반영이 가능
    - 각 기능의 개발속도는 모두 다르기 때문에, 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포 됨
    - 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 데이터가 주어지고, 각 작업의 개발 속도가 적힌 데이터가 주어짐

2. 출력
    - 각 배포마다 몇 개의 기능이 배포되는지를 return

3. 제약 조건
    - 작업의 개수는 100개 이하
    - 1 <= 작업 진도 < 100
    - 1 <= 작업 속도 <= 100
    - 배포는 하루에 한번만 가능, 하루의 끝에 배포가 가능
        - 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 2일 뒤에 이루어짐.

풀이
1. 아이디어
    - 각 진도의 남은 진도율을 속도로 나누어 남은 시간을 구함
        - 만약 남은 진도율이 7이고, 속도가 3이라면, 7 / 3 = 2 + 1 = 3 3일이 필요함
        - 이때, 속도로 나누었을때 나머지가 0이라면 +1을 해주지 않고, 나머지가 존재한다면 +1을 해줌
        - 해당 데이터를 배열에 저장
        - 앞에서 순차적으로 본인의 왼쪽보다 자신이 작다면, 왼쪽 값으로 업데이트하고, 날짜 배열을 생성해 해당 값에 +1해줌
            - 날짜 배열은 해당 날짜에 배포하는 작업의 개수를 담음
        - 이후 날짜 배열 값이 0이 아니라면, list에 저장
        - 저장한 list를 배열로 바꾸어 return
*/
import java.util.*;

class Solution {
        public int[] solution(int[] progresses, int[] speeds) {
            for (int i = 0; i < progresses.length; i++) {
                int remain = 100 - progresses[i];
                int time = 0;
                if (remain % speeds[i] == 0) {
                    time = remain / speeds[i];
                }else{
                    time = remain / speeds[i] + 1;
                }
                progresses[i] = time;
            }

            int[] result = new int[101];
            result[progresses[0]]++;

            for (int i = 1; i < progresses.length; i++) {
                if (progresses[i - 1] > progresses[i]) {
                    progresses[i] = progresses[i - 1];
                }
                result[progresses[i]]++;
            }

            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < result.length; i++) {
                if (result[i] > 0) {
                    list.add(result[i]);
                }
            }

            int[] answer = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                answer[i] = list.get(i);
            }
            return answer;
        }
    }

92번 프로세스

/*
문제 분석
1. 정보
    - OS의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것.
    - 해당 문제에서는 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행 되는지 알아내는 것
        - 1. 실행 대기 큐에서 대기중인 프로세스를 하나 꺼냄
        - 2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면, 방금 꺼낸 프로세스를 다시 큐에 넣음
        - 3. 만약 그런 프로세스가 없다면, 방금 꺼낸 프로세스를 실행
            - 3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료
2. 목표
    - 주어진 위치에 해당 하는 프로세스가 몇 번째로 실행 되는지 return
3. 제약 조건
     - 1 <= 프로세스의 중요도의 길이 <= 100
        - 1 <= 프로세스 중요도 <= 9
     - 0 <= 위치 < 프로세스 개수

풀이
1. 아이디어
    - 숫자가 높을 수록 우선순위가 높음
        - 따라서 우선순위가 9부터 차례대로 프로세스를 실행해 주어야 함.
        - 먼저 해당 우선순위를 가진 프로세스의 개수를 배열로 저장
        - 0번부터 차례대로 프로세스를 돌면서, 현재 우선순위를 가진 프로세스를 찾으면, 해당 프로세스의 우선순위 값을 -1로 설정 하고 idx를 +1 함, 또한 해당 우선순위의 개수를 -1 해줌.
        - 만약 해당 우선순위가 0이 되었으면, 우선순위를 -1해줌
        - 계속 돌아야 하므로, while문을 사용하여 계속돌 수 있도록 해줌.
        - 우리가 찾고자 하는 위치의 프로세스가 실행되었다면, idx값을 return
*/

class Solution {
        public int solution(int[] priorities, int location) {
            int[] priority = new int[10];
            for (int i : priorities) {
                priority[i]++;
            }

            int answer = 0;
            int idx = 0;
            int cnt = 1;
            int p = 0;
            for (int i = 9; i > 1; i--) {
                if (priority[i] > 0) {
                    p = i;
                    break;
                }
            }
            while(true){
                if (priorities[idx] == p) {
                    if (location == idx) {
                        answer = cnt;
                        break;
                    }
                    priorities[idx] = -1;
                    priority[p]--;
                    idx = (idx + 1) % priorities.length;
                    cnt++;

                    if (priority[p] == 0) {
                        for (int i = p; i > 0; i--) {
                            if (priority[i] > 0) {
                                p = i;
                                break;
                            }
                        }
                    }
                }else{
                    idx = (idx + 1) % priorities.length;
                }
            }
            System.out.println(answer);
            return answer;
        }
    }

93번 피로도

/*
문제 분석
1. 정보
    - XX게임에는 피로도 시스탬이 존재하며, 일정 피로도를 사용해 던전 탐험 가능
    - 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을때 소모되는 "소모 피로도"가 존재.
        - "최소 필요 피로도" : 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도
        - "소모 피로도" : 던전을 탐험한 후 소모되는 피로도
    - 하루에 한번씩 탐험할 수 있는 던전이 여러개 존재

2. 목표
    - 유저가 탐험할 수 있는 최대 던전 수를 return

3. 제약 조건
    - 1 <= 현재 피로도 <= 5000
    - 1 <= 던전 개수 <= 8
    - 1 <= 소모 피로도 <= 최소 필요 피로도 <= 1000

풀이
1. 아이디어
    - DFS 사용?
        - 들어온 던전을 최대한 탐험할 수 있게 DFS사용하여 최대 값 구하기
        - 시작은 0부터, visited 배열 사용
        - 만약 해당 던전을 갈수 있고, 방문하지 않았다면
            - 방문 처리하고, 해당 던전에 들어감.
            - 이후 방문 다시 제거
        - 모든 경우의 수를 구한 뒤, 가장 최대값을 return
*/

class Solution {

        int answer = 0;
        boolean[] visited;

        public int solution(int k, int[][] dungeons) {
            visited = new boolean[dungeons.length];

            dfs(k, dungeons, 0, 0);
            System.out.println(answer);
            return answer;
        }

        private void dfs(int k, int[][] dungeons, int idx, int cnt) {
            if (dungeons.length == idx) {
                answer = Math.max(answer, cnt);
                return;
            }

            for (int i = 0; i < dungeons.length; i++) {
                if (visited[i]) {
                    continue;
                }

                visited[i] = true;
                if (dungeons[i][0] <= k) {
                    dfs(k - dungeons[i][1], dungeons, idx + 1, cnt + 1);
                } else {
                    dfs(k, dungeons, idx + 1, cnt);
                }
                visited[i] = false;
            }
        }
    }

94번 타겟 넘버

/*
문제 분석
1. 정보
    - N개의 음이 아닌 정수가 존재
    - 해당 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만드려 함
2. 목표
    - 숫자를 적절히 빼고 더해서 타겟 넘버를 만드는 방법의 수를 return

3. 제약 조건
    - 2 <= 주어지는 숫자의 개수 <= 20
    - 1 <= 각 숫자 <= 50
    - 1 <= 타겟 넘버 <= 1000

풀이
1. 아이디어
     - DFS 알고리즘 사용
        - 가장 앞에있는 숫자부터 차례대로 계산
            - DFS(idx, total, numbers, target)
                - 만약 idx == numbers.length()이고, total == target -> answer++;
                - DFS(idx + 1, total + numbers[idx], numbers, target)
                - DFS(idx + 1, total - numbers[idx], numbers, target)
        - answer return
*/

class Solution {

        int answer = 0;

        public int solution(int[] numbers, int target) {
            dfs(0, 0, numbers, target);
            return answer;
        }

        private void dfs(int idx, int total, int[] numbers, int target){
            if (idx == numbers.length) {
                if(total == target){
                    answer++;
                }
                return;
            }

            dfs(idx + 1, total + numbers[idx], numbers, target);
            dfs(idx + 1, total - numbers[idx], numbers, target);
        }
    }

95번 k진수에서 소수 개수 구하기

/*
문제 분석
1. 정보
    - 양의 정수 n이 주어짐
    - n을 k진수로 바꿨을 때, 아래 조건에 맞는 소수가 몇개 인지 알아보려 함.
        - 0P0처럼 소수 양쪽에 0이 있는 걍우
        - P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
        - 0P처럼 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
        - P처럼 소수 양쪽에 아무것도 없는경우
2. 목표
    - n을 k진수로 바꿨을 때, 조건에 맞는 소수의 개수를 return

3. 제약 조건
    - 1 <= n <= 1000000
    - 3 <= k <= 10

풀이
1. 아이디어
    - 먼저 n을 k진수로 변환
        - 변환한 값 reverse
        - 해당 값을 0을 기준으로 split
        - split한 값 모두 탐색
            - 해당값이 비어있지 않으면
                - 소수인지 판별
            - 소수라면 answer++;
        - 모두 탐색 한 후 answer return

    - 소수인지 판별
        - 만약 n < 2 : return false
        - i = 2 ; i < Math.sqrt(n) ; i++ 까지
            - 만약 n % i == 0 : return false;
        - return true;
*/

class Solution {
        public int solution(int n, int k) {
            int answer = 0;
            StringBuilder sb = new StringBuilder();
            while (n > 0) {
                sb.append(n % k);
                n /= k;
            }
            sb.reverse();

            String[] numbers = sb.toString().split("0");

            for (String number : numbers) {
                System.out.println(number);
                if (!number.isEmpty() && isPrime(Long.parseLong(number))) {
                    answer++;
                }
            }

            return answer;
        }

        private boolean isPrime(long num) {
            if(num < 2) return false;
            for(int i = 2 ; i <= Math.sqrt(num) ; i++){
                if(num % i == 0) return false;
            }
            return true;
        }
    }