Computer Science Knowledge Storage

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

H-Index를 찾기 위해서 정렬이 꼭 필요합니다. 또 i를 0부터 순회하면 len - i는 최대 값이 되므로 다음 코드와 같이 로직을 계산합니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);

        int len = citations.length;
        for (int i = 0; i < len; i++) {
            if (citations[i] >= len - i) {
                return len - i;
            }
        }
        return 0;
    }
}

코드 설명

• Arrays.sort(citations);
  주어진 citations 배열을 오름차순으로 정렬합니다. 이는 논문의 인용 횟수를 작은 순서부터 큰 순서로 정렬하여 H-Index를 계산하기 쉽게 만듭니다.
• for (int i = 0; i < len; i++) { if (citations[i] >= len - i) { return len - i; } }
  citations 배열을 순회하며 H-Index 조건을 검사합니다.
  
  • citations[i]는 논문의 인용 횟수를 나타냅니다.
  • len - i는 현재 인덱스 기준으로 남은 논문 개수를 나타냅니다.
  • if (citations[i] >= len - i): 논문 i번째의 인용 횟수가 남은 논문 개수 이상일 경우, H-Index 조건을 만족합니다. 즉, 인용 횟수가 적어도 len - i 이상인 논문이 len - i편 존재한다는 의미입니다.
• 루프를 다 돌아도 H-Index 조건을 만족하는 값이 없다면 0을 반환합니다. 이는 모든 논문의 인용 횟수가 H-Index 조건을 만족하지 않을 때입니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

각 자릿수를 토대로 비교하면서 가장 큰 수를 구할 수도 있겠습니다만, 시간 초과가 날 것입니다.
이를 위해 문자열 정렬로 생각하여 문제를 풀었습니다. 예를 들어, a = "3"와 b = "30"일 때 (b + a)는 "303"이고 (a + b)는 "330"입니다. 따라서 "330"이 더 앞에 오도록 구현하였습니다.

소스코드

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        StringBuilder sb = new StringBuilder();

        String[] strNumbers = Arrays.stream(numbers)
                .mapToObj(String::valueOf)
                .toArray(String[]::new);

        Arrays.sort(strNumbers, (a, b) -> (b + a).compareTo(a + b));

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

        if (sb.toString().charAt(0) == '0') {
            return "0";
        }
        
        return sb.toString();
    }
}

코드 설명

• StringBuilder sb = new StringBuilder();
  문자열을 효율적으로 생성하기 위해 StringBuilder 객체 sb를 생성합니다. 최종 결과 문자열을 생성하는 데 사용됩니다.
• String[] strNumbers = Arrays.stream(numbers).mapToObj(String::valueOf).toArray(String[]::new);
  numbers 배열의 각 요소를 문자열로 변환하여 새로운 String 배열 strNumbers에 저장합니다.
  
  • Arrays.stream(numbers): numbers 배열을 스트림으로 변환합니다.
  • .mapToObj(String::valueOf): 각 정수 요소를 String 객체로 변환합니다.
  • .toArray(String[]::new): 스트림의 결과를 String 배열로 반환합니다.
• Arrays.sort(strNumbers, (a, b) -> (b + a).compareTo(a + b));
  strNumbers 배열을 사용자 정의 비교자로 정렬합니다.
  
  • 정렬 기준을 문자열 (a + b) 와 (b + a)의 비교로 결정합니다.
  • (b + a).compareTo(a + b): 두 연결 결과를 비교하여 내림차순으로 정렬합니다.
• if (sb.toString().charAt(0) == '0') { return "0"; }
  생성된 문자열이 0으로 시작하는 경우, 이는 numbers 배열의 모든 요소가 0일 때입니다. 따라서 "0"을 반환합니다.
• return sb.toString();
  StringBuilder에 추가된 모든 요소를 문자열로 변환하여 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

최댓값과 최솟값을 효율적으로 관리 및 구하기 위해 최소 힙과 최대 힙을 두개 선언하고 연산에 맞게 관리합니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> min = new PriorityQueue<>();
        
        for (String operation : operations) {
            String[] split = operation.split(" ");
            String command = split[0];
            int number = Integer.parseInt(split[1]);

            switch (command) {
                case "I":
                    min.add(number);
                    max.add(number);
                    break;
                case "D":
                    if (number == 1 && !max.isEmpty()) {
                        int maxNum = max.poll();
                        min.remove(maxNum);
                    } else if (number == -1 && !min.isEmpty()) {
                        int minNum = min.poll();
                        max.remove(minNum);
                    }
                    break;
            }
        }
        
        int[] answer = {0, 0};
        if (!min.isEmpty() && !max.isEmpty()) {
            answer[0] = max.poll();
            answer[1] = min.poll();
        }
        
        return answer;
    }
}

코드 설명

• PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
  PriorityQueue<Integer> min = new PriorityQueue<>();
  최대 힙 max와 최소 힙 min을 초기화합니다. 이는 최소 값 및 최대 값을 빠르게 가져오거나 삭제하기 위해 사용됩니다.

• for (String operation : operations)
  operations 배열의 각 명령어를 순차적으로 탐색합니다. 각 명령어는 삽입 또는 삭제 작업을 나타냅니다.
  • String[] split = operation.split(" ");
    명령어를 공백으로 나누어 split 배열에 저장합니다. 첫 번째 요소는 명령어(I 또는 D), 두 번째 요소는 숫자를 나타냅니다.
  • String command = split[0];
    명령어(I 또는 D)를 command에 저장합니다.
  • int number = Integer.parseInt(split[1]);
    명령어의 숫자 값을 정수로 변환하여 number에 저장합니다.
  • switch (command)
    명령어(command)에 따라 조건문을 통해 동작을 결정합니다.
    • case "I":
      number를 min과 max 두 큐 모두에 추가합니다.
    • case "D":
      • if (number == 1 && !max.isEmpty())
        number가 1이면 최대값 삭제 명령어입니다. max에서 최대값을 poll()로 제거하고, min에서도 동일한 값을 remove()로 삭제합니다.
      • else if (number == -1 && !min.isEmpty())
        number가 -1이면 최소값 삭제 명령어입니다. min에서 최소값을 poll()로 제거하고, max에서도 동일한 값을 remove()로 삭제합니다.
  • int[] answer = {0, 0};
    • 결과를 담을 배열 answer를 선언하고 초기화합니다.
  • if (!min.isEmpty() && !max.isEmpty())
    • min과 max가 모두 비어 있지 않으면, answer[0]에 max의 최대값, answer[1]에 min의 최소값을 할당합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

가장 최소의 처리량 평균 시간을 구하는 문제였습니다. 요청시간이 빠른 순대로 정렬을 하면 짧은 작업시간을 가지는 일들에 대해서는 너무 오래 기다리게 되고, 짧은 작업시간 순대로 정렬을 하면 요청이 먼저 온 작업을 처리를 하지 못하게 됩니다. 

따라서 현재 시간에 따라 처리 가능한 작업을 구하고 그 중에서 요청시간이 짧은 것을 먼저 처리합니다.

소스코드

import java.util.*;

class Solution {
    
    static class Job implements Comparable<Job> {
        int requestTime, workingTime;
        
        public Job(int requestTime, int workingTime) {
            this.requestTime = requestTime;
            this.workingTime = workingTime;
        }
        
        @Override
        public int compareTo(Job j) {
            if (this.requestTime == j.requestTime) {
                return this.workingTime - j.workingTime;
            }
            return this.requestTime - j.requestTime;
        }
    }
    
    public int solution(int[][] jobs) {
        PriorityQueue<Job> disk = new PriorityQueue<>();
        int len = jobs.length;
        
        for(int[] job: jobs) {
            disk.add(new Job(job[0], job[1]));
        }
        
        int time = 0; // 현재 시간
        int ans = 0; // 처리량 평균 구하기
        List<Job> execList = new ArrayList<>();
        
        while (!disk.isEmpty() || !execList.isEmpty()) {
            // 현재 시간에 요청된 작업을 모두 execList에 추가
            while (!disk.isEmpty() && time >= disk.peek().requestTime) {
                execList.add(disk.poll());
            }

            // 작업을 소요 시간 기준으로 정렬
            if (!execList.isEmpty()) {
                Collections.sort(execList, Comparator.comparingInt(job -> job.workingTime));
                Job exec = execList.remove(0);
                if (time < exec.requestTime) {
                    time = exec.requestTime;
                }
                time += exec.workingTime;
                ans += time - exec.requestTime;
            } else if (!disk.isEmpty()) {
                time = disk.peek().requestTime;
            }
        }
        
        return ans / len;
    }
}

코드 설명

Job 클래스

• Job 클래스는 Comparable 인터페이스를 구현하며, 작업의 요청 시간(requestTime)과 소요 시간(workingTime)을 필드로 가지고 compareTo 메서드는 Job 객체를 요청 시간 순서로 정렬합니다. 요청 시간이 동일할 경우, 소요 시간 기준으로 정렬하도록 조건을 설정할 수 있습니다.

• PriorityQueue<Job> disk = new PriorityQueue<>();
  작업 요청 시간 기준으로 정렬되는 우선순위 큐를 초기화합니다. Job 객체를 담아 요청 시간이 빠른 순서대로 작업을 처리할 수 있습니다.
• while문 내부 변수 사용부분
  • time은 현재 시각을 나타내며, ans는 작업 완료까지 걸린 총 시간을 누적합니다.
  • execList는 현재 처리 가능한 작업 목록입니다.
• while (!disk.isEmpty() || !execList.isEmpty()) { ... }
  • disk 큐의 작업 중 현재 time에 요청된 작업을 execList로 이동합니다.
  • execList에 작업이 있으면 소요 시간 기준으로 정렬하고, 가장 짧은 작업을 선택하여 실행합니다.
  • time이 해당 작업의 요청 시간보다 작으면, time을 그 요청 시간으로 맞춥니다.
  • time을 해당 작업의 소요 시간만큼 증가시키고, 요청부터 종료까지 걸린 시간(time - requestTime)을 ans에 더합니다.
  • 만약 execList가 비어 있고 disk에 작업이 남아 있다면, time을 다음 작업의 요청 시간으로 설정하여 작업을 진행할 수 있게 합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

최솟값을 찾기 위해 정렬을 사용해도 되지만 가장 효율적인 자료 구조 Heap을 이용하여 스코빌 지수의 최솟값을 찾도록 코드를 구현하였습니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> scovilles = new PriorityQueue<>();
        
        for (int level: scoville) {
            scovilles.add(level);
        }
        
        int mix = -1;
        int ans = 0;
        while (scovilles.peek() < K) {
            if (scovilles.size() < 2) {
                return -1;
            }
            int first = scovilles.poll();
            int second = scovilles.poll();
            mix = first + second * 2;
            scovilles.add(mix);
            ans++;
        }
        
        return ans;
    }
}

코드 설명

• PriorityQueue<Integer> scovilles = new PriorityQueue<>();
  스코빌 지수를 저장하는 Heap을 생성합니다. 해당 힙은 최소 힙으로 구현합니다.
• 섞은 음식의 스코빌 지수
  • while 루프는 큐의 최솟값(scovilles.peek())이 K 미만인 동안 반복됩니다.
  • 이때 큐의 크기가 2 미만이 되면, 더 이상 결합할 수 없으므로 -1을 반환하여 목표를 달성할 수 없음을 나타냅니다.
  • 최솟값 두 개를 꺼내어(poll() 메서드 사용) 결합하여 새로운 스코빌 지수(first + second * 2)를 계산합니다.
  • 새로 만든 스코빌 지수를 큐에 다시 추가하고, 결합 횟수 ans를 증가시킵니다.
• 섞은 횟수를 반환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

다리를 큐로 표현해 각 트럭의 상태를 관리하며, 트럭이 다리를 건너는 동안의 시간과 다리의 무게 제한을 고려해 순차적으로 트럭을 다리에 올리고 내립니다. 반복문은 트럭이 모두 다리를 건널 때까지 계속됩니다.

소스코드

import java.util.*;

class Solution {
    static class Truck {
        int weight, position;

        public Truck(int weight) {
            this.weight = weight;
            this.position = 0;
        }

        public Truck(int weight, int position) {
            this.weight = weight;
            this.position = position;
        }
    }
    
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0; // 경과 시간
        int bridgeWeight = 0; // 현재 다리 위의 트럭 총 무게
        Queue<Truck> bridge = new LinkedList<>(); // 다리 위의 트럭 큐
        int idx = 0; // 대기 트럭 인덱스

        while (idx < truck_weights.length || !bridge.isEmpty()) {
            time++;

            if (!bridge.isEmpty()) {
                Truck frontTruck = bridge.peek(); // 맨 앞의 트럭
                if (time - frontTruck.position >= bridge_length) { // 다리를 다 건넜을 경우
                    bridgeWeight -= frontTruck.weight; // 다리 무게에서 제외
                    bridge.poll(); // 트럭 다리에서 내림
                }
            }

            if (idx < truck_weights.length) {
                if (bridgeWeight + truck_weights[idx] <= weight && bridge.size() < bridge_length) {
                    bridge.add(new Truck(truck_weights[idx], time)); // 트럭 다리에 올림
                    bridgeWeight += truck_weights[idx]; // 현재 다리 무게 갱신
                    idx++; // 대기 트럭 인덱스 증가
                }
            }
        }
        return time;
    }
}

코드 설명

• Truck 클래스
  • weight: 트럭의 무게.
  • position: 트럭이 다리를 건너기 시작한 시점(시간).
• 변수 초기화:
  • time: 전체 시뮬레이션의 경과 시간을 나타냅니다.
  • bridgeWeight: 현재 다리 위에 있는 트럭들의 총 무게입니다.
  • bridge: 현재 다리를 건너고 있는 트럭들을 저장하는 큐입니다.
  • idx: 대기 중인 트럭을 가리키는 인덱스입니다.
• 메인 로직:
  • 시간 증가: 매 반복마다 time이 증가합니다. 이는 시뮬레이션의 한 단계를 의미합니다.
  • 트럭 이동:
    • bridge 큐에서 맨 앞에 있는 트럭(frontTruck)의 위치를 확인합니다.
    • time - frontTruck.position이 bridge_length보다 크거나 같다면, 트럭은 다리를 건넜으므로 bridge.poll()로 큐에서 제거하고, bridgeWeight에서 트럭의 무게를 뺍니다.
  • 새 트럭 추가:
    • 아직 다리를 건너지 않은 트럭이 있을 경우(idx < truck_weights.length), 현재 다리의 무게(bridgeWeight + truck_weights[idx])가 제한을 초과하지 않고 다리 길이 조건을 만족하면 새 트럭을 bridge에 추가합니다.
    • 새 트럭이 다리에 추가되면 bridgeWeight를 업데이트하고 idx를 증가시켜 다음 트럭을 가리킵니다.
• 종료 조건:
  • 대기 중인 트럭이 더 이상 없고(idx >= truck_weights.length), bridge에 남아 있는 트럭도 없을 때 시뮬레이션이 종료됩니다.
• 결과 반환:
  • 최종적으로 경과된 time을 반환합니다. 이는 모든 트럭이 다리를 건너기까지 걸린 총 시간입니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

시간 복잡도 O(N^2)으로 잘 관리하면 문제가 패스하는 것을 확인했습니다. 하지만 시간복잡도를 줄이고 싶어 Stack을 이용하였고, O(N)의 시간 복잡도를 갖는 코드를 구현하였습니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int len = prices.length;
        int[] ans = new int[len];
        Stack<Integer> stack = new Stack<>();
        
        // 각 시간의 인덱스를 스택에 저장
        for (int i = 0; i < len; i++) {
            // 현재 가격이 스택의 마지막 가격보다 낮으면, 하락 시간 계산
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                int idx = stack.pop();
                ans[idx] = i - idx; // 하락 시간 계산
            }
            stack.push(i); // 현재 인덱스를 스택에 추가
        }
        
        // 남아 있는 인덱스들은 끝까지 가격이 떨어지지 않음
        while (!stack.isEmpty()) {
            int idx = stack.pop();
            ans[idx] = len - 1 - idx;
        }
        
        return ans;
    }
}

코드 설명

• 루프를 통해 각 시점의 가격을 순회합니다.
  • 스택의 크기와 현재 가격이 마지막 주식 가격보다 낮으면
    • 스택에서 해당 인덱스를 꺼내고, 그 하락 시간을 i - idx로 계산하여 ans 배열에 저장.
  • 현재 시점 i를 스택에 추가하여 이후 가격 변화에 대해 추적.
• 스택에 남아있는 시점들은 가격이 떨어지지 않은 것이므로 전체 크기에 대해 배열에 저장합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

프로세스의 최댓값과 그 갯수를 효율적으로 관리하는게 포인트였습니다. Map으로도 관리할 수 있고, 리스트로도 관리할 수 있겠지만
저는 이 문제에서 우선순위 큐를 사용하였습니다.

소스코드

import java.util.*;

class Solution {
    
    static class Process {
        int priority, index;
        public Process(int priority, int index) {
            this.priority = priority;
            this.index = index;
        }
    }
    
    public int solution(int[] priorities, int location) {
        Queue<Process> processes = new LinkedList<>();
        PriorityQueue<Integer> remainPriority = new PriorityQueue<>(Collections.reverseOrder());
        
        int len = priorities.length;
        
        for(int i = 0; i < len; i++) {
            int priority = priorities[i];
            remainPriority.add(priority);
            processes.add(new Process(priority, i));
        }
        
        int order = 1;
        while(true) {
            Process ready = processes.poll();
            int maxPriority = remainPriority.poll();
            if (maxPriority == ready.priority) {
                if (location == ready.index) {
                    return order;
                } else {
                    order++;
                }
            } else {
                remainPriority.add(maxPriority);
                processes.add(ready);
            }
        }
    }
}

코드 설명

• static class Process
  우선순위와 고유번호를 저장하기 위해 static class Process를 선언합니다.
• PriorityQueue<Integer> remainPriority = new PriorityQueue<>(Collections.reverseOrder());
  priority를 저장할 우선순위 큐를 선언합니다.
  
  • 해당 우선순위큐는 최소 힙이 아닌 최대 힙으로 선언하기 위해 Collections.reverseOrder()을 사용합니다.
• processes 큐에서 프로세스를 하나씩 꺼내 처리합니다.
• remainPriority에서 가장 높은 우선순위를 가져옵니다.
• 현재 프로세스의 우선순위가 가장 높은 우선순위와 같으면:
  • location에 있는 프로세스인지 확인합니다.
  • 맞다면 현재 순서(order)를 반환합니다.
  • 아니라면 실행 순서를 증가시킵니다.
• 현재 프로세스의 우선순위가 가장 높지 않으면:
  • 프로세스를 다시 큐에 넣고 remainPriority에 추가하여 다음 순서를 준비합니다.