알고리즘(소수 찾기, 더 맵게, H-Index)

[소수 찾기]

 

* 로직

• 1개부터 numbers.length()개 만큼 뽑는 경우의 수를 모두 구한다 (각 순열의 합)
• 경우의 수를 구하게 되면
  • 해당 숫자가 이전에 존재했는지 확인한다
  • 존재하지 않았다면
    • 소수 판별을 진행하고, 만약 소수라면 개수를 카운팅한다
    • 해당 경우의 수를 마킹한다
• 위 과정을 반복한다

 

//소수찾기
import java.util.HashMap;
import java.util.LinkedList;

public class Problem_FindPrimeNum {
    static boolean[] checekd;
    static HashMap<Integer, Boolean> hashMap;
    static int result;

    public static void main(String[] args) {
        String numbers = "011";
        int answer = solution(numbers);
        System.out.println(answer);
    }

    public static int solution(String numbers) {
        int answer = 0;
        result = 0;
        hashMap = new HashMap<>();

        //1개뽑는 경우 ~ size개 뽑는 경우까지 (순열의 합)
        for(int size=1; size<=numbers.length(); ++size) {
            LinkedList<String> pathList = new LinkedList<>();
            checekd = new boolean[numbers.length()];

            doProcess(size, pathList, numbers);
        }

        return answer = result;
    }

    private static void doProcess(int size, LinkedList<String> pathList, String numbers) {
        if(size == 0) {
            StringBuilder sb = new StringBuilder();
            for(String tmp : pathList) {
                sb.append(tmp);
            }

            //문자 -> 숫자
            int num = Integer.parseInt(sb.toString());

            //처음 만들어진 숫자라면
            if(hashMap.isEmpty() || !hashMap.containsKey(num)) {

                //소수판별
                if(deterPrime(num)) result++;

                hashMap.put(num, true);
            }
            return;
        }

        for(int i=0; i<numbers.length(); ++i) {
            if(!checekd[i]) {
                checekd[i] = true;
                pathList.offer(numbers.substring(i, i+1));
                doProcess(size-1, pathList, numbers);
                pathList.removeLast();
                checekd[i] = false;
            }
        }
    }

    private static boolean deterPrime(int num) {
        if(num == 0 || num == 1) return false;

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

        return true;
    }
}

 

 

[더 맵게]

 

* 로직

• 가장 작은 2개의 수를 뽑아 스코빌 지수를 넣어줘야기 때문에, 효율성을 고려하여 우선순위 큐를 사용한다
• 우선순위 큐의 루트(가장 작은 수) < K 라면
  • 2개의 수를 뽑고 새로운 스코빌 지수를 만든다
  • 새로운 스코빌 지수를 넣어준다
  • answer++ 해준다
  • 만약 수를 뽑을 때 큐의 사이즈가 1이라면 -> 2개를 뽑을 수 없기 때문에 -1을 리턴한다

//더 맵게
import java.util.PriorityQueue;

public class Problem_MoreSpicy {

    public static void main(String[] args) {
        int[] scoville = {1, 2, 3, 9, 10, 12};
        int K = 7;
        int answer = solution(scoville, K);

        System.out.println(answer);
    }

    public static int solution(int[] scoville, int K) {
        int answer = 0;

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for(int input : scoville) {
            priorityQueue.offer(input);
        }

        //모든 음식의 스코빌 지수가 K 이상이 되었다면 종료
        while (priorityQueue.peek() < K) {
            if(priorityQueue.size() == 1) return -1;

            int food1 = priorityQueue.poll();
            int food2 = priorityQueue.poll();

            int value = food1 + (food2 * 2);
            priorityQueue.offer(value);
            answer++;
        }

        return answer;
    }
}

 

 

[H-Index]

* 로직

• 이분탐색을 활용해 H-Index가 나올 수 있는 최댓값을 구한다
• 정렬을 한다 (오름차순)
• mid가 주어지면, 이를 기준으로 인용수 및 미인용수를 구한다
• 만약 인용수 >= mid, 미인용수 <= mid라면
  • 답을 갱신하고 범위를 늘리기 위해 front = mid + 1
• 만약 인용수가 더 적다면
  • 범위를 좁혀줘야하기 때문에 rear = mid - 1
• 위 과정이 종료되면 답을 출력한다

 

//H-Index
import java.util.Arrays;

public class Problem_H_Index {

    public static void main(String[] args) {
        int[] citations = {3, 0, 6, 1, 5};
        int answer = solution(citations);
        System.out.println(answer);
    }

    public static int solution(int[] citations) {
        int answer = 0;
        int size = citations.length;
        Arrays.sort(citations);

        int front = 0;
        int rear = citations[size-1];
        while(front <= rear){
            int mid = (front + rear) / 2;

            //해당 인용수 h를 기준으로 인용수 및 미인용수 계산
            int cnt_cite=0;
            int cnt_none=0;
            for(int i=0; i<size; ++i){
                if(citations[i] >= mid) cnt_cite++;
                else cnt_none++;
            }

            //조건에 부합된다면 -> 더 큰 최댓값에 있는지 확인 필요
            if(cnt_cite >= mid && cnt_none <= mid){
                answer = mid;
                front = mid+1;
            }

            //인용 수가 더 적다는 말은 -> h를 낮춰야함 -> 범위 줄이기
            else rear = mid-1;
        }

        return answer;
    }
}