Computer Science Knowledge Storage

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
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에 추가하여 다음 순서를 준비합니다.

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

포인트

유명한 스택 문제입니다. ')'이 있으면 '('가 스택에 존재해야합니다. 또 마지막 스택에는 아무런 원소가 없어야합니다.

소스코드

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        Stack<Character> bracketValidator = new Stack<>();
        
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == ')') {
                if (bracketValidator.isEmpty() || bracketValidator.peek() != '(') {
                    return false;
                }
                bracketValidator.pop();
            } else {
                bracketValidator.add('(');
            }
        }
        
        return bracketValidator.isEmpty() ? true : false;
    }
}

코드 설명

• Stack<Character> bracketValidator = new Stack<>();
  Character를 원소로 갖는 Stack을 선언합니다.
• if (s.charAt(i) == ')') { if (bracketValidator.isEmpty() || bracketValidator.peek() != '(') { return false; } }
  • ')'가 되었을 때 Stack에 (이 없거나 empty이면 false를 리턴합니다.
  • 이후 Stack의 원소를 pop해줍니다.
• else { bracketValidator.add('('); }
  • '(' 값을 만났을 때에는 Stack에 add 해줍니다.
• return bracketValidator.isEmpty() ? true : false;
  • Stack의 원소가 없으면 true를 리턴 그렇지 않으면 false를 리턴합니다.

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

포인트

선행 작업이 끝나야 뒤에 작업을 배포할 수 있습니다. 따라서 이전 기능 개발이 끝나는 날을 기록하여 해당 기간까지 다음 기능개발을 끝내는 수 있는지 확인하여 분기처리를 진행합니다.

소스코드

import java.util.*;

class Solution {
    
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> production = new ArrayList<>();
        
        int len = progresses.length;
        int curDay = 0;
        int features = 0;
        
        for (int i = 0; i < len; i++) {
            // 남은 작업일 계산
            int remainDay = (100 - progresses[i]) / speeds[i];
            if ((100 - progresses[i]) % speeds[i] != 0) {
                remainDay++;
            }
            
            // 현재 기능이 배포 가능일보다 오래 걸리면 새로운 배포
            if (curDay < remainDay) {
                if (features > 0) {
                    production.add(features); // 이전에 쌓인 기능 수를 추가
                }
                curDay = remainDay; // 현재 배포 일자 갱신
                features = 1; // 새 기능 초기화
            } else {
                // 현재 기능이 이전 배포 일자 내에 완성되면 함께 배포
                features++;
            }
        }
        
        // 마지막에 남은 기능 수 추가
        if (features > 0) {
            production.add(features);
        }
        
        // 결과 배열로 변환
        return production.stream().mapToInt(Integer::intValue).toArray();
    }
}

코드 설명

• remainDay = 현재 기능을 완료하기까지 걸리는 일 수.
  curDay = 지난 일자
  features = 배포 기능 개수
• int remainDay = (100 - progresses[i]) / speeds[i];
  • 남은 작업 일을 계산합니다. 나누어 떨어지지 않는다면 하루가 더 필요합니다.

// 현재 기능이 배포 가능일보다 오래 걸리면 새로운 배포
if (curDay < remainDay) {
    if (features > 0) {
        production.add(features); // 이전에 쌓인 기능 수를 추가
    }
    curDay = remainDay; // 현재 배포 일자 갱신
    features = 1; // 새 기능 초기화
} else {
    // 현재 기능이 이전 배포 일자 내에 완성되면 함께 배포
    features++;
}

// 마지막에 남은 기능 수 추가
if (features > 0) {
    production.add(features);
}

• 지금까지 걸린 기간에서 남은 일보다 작으면 현재 기능을 배포할 수 없습니다. 
  따라서 현재 기간까지 배포 가능한 기능 수(features)를 add해주고
  현재 배포 일자와 새 기능 수를 갱신합니다.
• 반대로 걸린 기간이 남은 일자보다 더 크면 배포 기능 수를 추가해줍니다.
• 이후 마지막에 남은 기능 수를 추가해줍니다.
• return production.stream().mapToInt(Integer::intValue).toArray();
  • 결과를 int[] 배열로 반환합니다.

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

포인트

연속적으로 나타나는 숫자를 파악하기 위해 list나 배열에 index를 통해 확인할 수 있지만
LIFO구조의 Stack이라는 자료구조를 통해 더 효율적으로 문제를 풀 수 있다.

소스코드

import java.util.*;

public class Solution {
    
    public int[] solution(int[] arr) {
        Stack<Integer> ans = new Stack<>();
        
        for (int num: arr) {
            if (ans.isEmpty() || ans.peek() != num) {
                ans.add(num);
            } 
        }
        
        return ans.stream().mapToInt(Integer::intValue).toArray();
        
    }
}

코드 설명

• Stack<Integer> ans = new Stack<>();
  • Integer 타입을 저장하는 스택을 선언한다.
• if (ans.isEmpty() || ans.peek() != num)
  • 스택이 비어있거나 마지막으로 넣은 값과 연속적이지 않으면 스택에 값을 넣는다.
• return ans.stream().mapToInt(Integer::intValue).toArray();
  • int[] 배열로 반환한다.