Computer Science Knowledge Storage

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

포인트

차량들의 진입점과 출구점이 주어졌을 때, 각 차량들이 겹치지 않도록 선택하는 것은 최대한 적은 공간을 차지하면서 차량들을 배치하는 문제입니다. 이를 해결하기 위해서는 먼저 고속도로를 나간 지점이 빠른 차량을 우선적으로 선택하는 것이 중요합니다.

소스코드

import java.util.*;

class Solution {
    static class Car implements Comparable<Car> {
        int src, desc;
        public Car(int src, int desc) {
            this.src = src;
            this.desc = desc;
        }
        
        @Override
        public int compareTo(Car c) {
            return this.desc - c.desc;
        }
    }
    
    public int solution(int[][] routes) {
        List<Car> cars = new ArrayList<>();
        for(int[] route: routes) {
            Car newCar = new Car(route[0], route[1]);
            cars.add(newCar);
        }
        
        Collections.sort(cars);
        
        int answer = 0;
        int last = -1;
        for(Car cur: cars) {
            if(last == -1) {
                last = cur.desc;
                answer++;
            } else if (cur.src <= last && cur.desc >= last) {
            } else {
                last = cur.desc;
                answer++;
            }
        }
        
        return answer++;
    }
}

코드 설명

• Car 클래스
  Car 클래스는 각 차량의 진입 구간(src)과 출구 구간(desc)을 나타냅니다.
  • 이 클래스는 Comparable<Car>를 구현하여 Car 객체들을 desc (출구 구간) 기준으로 오름차순 정렬하도록 정의됩니다.
  • compareTo 메서드는 출구 구간 desc 값 기준으로 비교하여 정렬 순서를 결정합니다.
• Car 객체 생성 및 리스트에 추가:
  • routes 배열을 순회하여 Car 객체를 생성하고, 각 차의 진입점(src)과 출구점(desc)을 Car 객체에 저장한 후 cars 리스트에 추가합니다.
• 정렬:
  • cars 리스트를 desc 값(출구 지점)을 기준으로 오름차순 정렬합니다.
  • 정렬 기준이 desc 값이므로, 먼저 출구가 빠른 차량부터 선택하게 됩니다. 이는 그리디 알고리즘에서 가장 중요한 부분입니다.
• 차량 선택:
  • 차량을 하나씩 순차적으로 살펴보면서, 겹치지 않도록 선택합니다.
  • last는 마지막으로 선택된 차량의 출구점을 추적하는 변수입니다. 처음에는 -1로 초기화합니다.
  • for문을 통해 각 차량의 구간을 확인하면서, 다음 조건에 맞는 차량만 선택합니다:
    • last == -1: 첫 번째 차량이므로 last를 그 차량의 출구점으로 설정하고 차량을 선택합니다.
    • cur.src <= last && cur.desc >= last: 현재 차량의 진입점이 last보다 작거나 같고, 출구점이 last보다 크거나 같은 경우는 이미 다른 차량이 선택된 구간과 겹친다는 의미입니다. 이 경우에는 차량을 선택하지 않고 넘어갑니다.
    • 그렇지 않으면, 현재 차량을 선택하고, last를 해당 차량의 출구점(desc)으로 갱신합니다.
• 결과 반환:
  • 최종적으로 선택된 차량의 수는 answer 변수에 저장됩니다.
  • 마지막에 answer++는 answer를 증가시키는 부분인데, 이 부분은 잘못된 코드입니다. return answer로 해야 합니다. answer++는 잘못된 값이 반환될 수 있습니다.

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

포인트

가장 최소의 코스트로 모든 다리를 연결하여야 하므로 최소 신장 트리를 구하는 문제입니다.

최소 신장 트리를 구하기 위한 크루스칼 알고리즘을 활용하여 문제를 풀어줍니다.

소스코드

import java.util.*;

class Solution {
    
    class Bridge implements Comparable<Bridge> {
        int src, dest, cost;
        
        public Bridge(int src, int dest, int cost) {
            this.src = src;
            this.dest = dest;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Bridge b) {
            if(this.cost == b.cost) {
                return this.src - b.src;
            }
            return this.cost - b.cost;
        }
    }
    int[] parents;
    
    public int findParent(int n) {
        if (parents[n] != n) {
            parents[n] = findParent(parents[n]);
        }
        return parents[n];
    }
    
    public void union(int a, int b){
        a = findParent(a);
        b = findParent(b);
        
        if (a < b) {
            parents[b] = a;
        } else {
            parents[a] = b;
        }
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int len = costs.length;
        List<Bridge> bridges = new ArrayList<>();
        
        for(int i = 0; i < len; i++){
            Bridge newBridge = new Bridge(costs[i][0], costs[i][1], costs[i][2]);
            bridges.add(newBridge);
        }
        Collections.sort(bridges);
        parents = new int[n+1];
        for(int i = 0; i <= n; i++) {
            parents[i] = i;
        }
        
        for(Bridge bridge: bridges) {
            if (findParent(bridge.src) != findParent(bridge.dest)) {
                union(bridge.src, bridge.dest);
                answer += bridge.cost;
            }
        }
        
        return answer;
    }
}

코드 설명

• Bridge 클래스
  섬 간의 다리를 나타내는 클래스입니다.
  • src: 다리의 출발 섬.
  • dest: 다리의 도착 섬.
  • cost: 다리의 건설 비용.
  • Comparable 인터페이스를 구현하여, 비용이 낮은 순서대로 정렬되도록 합니다. 비용이 같을 경우 src의 값을 기준으로 정렬됩니다.
• findParent 메서드
  findParent는 주어진 노드 n의 대표 부모 노드를 찾는 재귀 메서드입니다.
  • 경로 압축(Path Compression) 기법을 사용하여, 트리의 높이를 줄이고 효율성을 높입니다.
• union 메서드
  • 두 노드 a와 b를 하나의 집합으로 합칩니다. 두 집합의 대표 부모를 찾은 후, 더 작은 번호의 노드가 부모가 되도록 합니다.
  • 이를 통해, 서로 다른 집합을 병합하면서 트리 구조를 형성합니다.
• Solution 메서드
  • Bridge 객체 리스트 bridges에 다리 정보를 추가하고 비용 순으로 정렬합니다.
  • parents 배열을 초기화하여 각 섬의 부모를 자기 자신으로 설정합니다.
  • for 반복문을 통해 비용이 낮은 다리부터 탐색하여, 두 섬이 다른 집합에 속해 있을 경우 union 연산을 수행하고 다리 비용을 answer에 더합니다.
  • 최소 비용으로 모든 섬을 연결할 수 있는 다리들의 총 비용을 answer로 반환합니다.

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

포인트

그리디 문제는 대부분 정렬과 조합을 이룬 문제가 많습니다. 따라서 가장 무거운 사람과 가장 무게가 작은 사람을 태워야 최대 limit를 채울 수 있습니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int index = 0;
        
        for (int i = people.length - 1; i >= index; i--) {
            if (people[i] + people[index] <= limit) {
                index++;
            }
            answer++;
        }

        return answer;
    }
}

코드 설명

• 초기화
  • answer: 최소 보트 수를 저장하는 변수로 초기값은 0입니다.
  • index: 가장 가벼운 사람의 인덱스를 나타내는 변수로 초기값은 0입니다.
  • Arrays.sort(people): people 배열을 오름차순으로 정렬하여 무게가 가벼운 사람부터 무거운 사람 순으로 정렬합니다.
• for (int i = people.length - 1; i >= index; i--) { if (people[i] + people[index] <= limit) { index++; } answer++; }
  
  • i는 가장 무거운 사람의 인덱스를 가리킵니다. i는 배열의 끝에서 시작하여 index까지 감소합니다.
  • if (people[i] + people[index] <= limit): 가장 무거운 사람(people[i])과 가장 가벼운 사람(people[index])의 합이 limit 이하인지 확인합니다.
    • 조건이 true인 경우, 두 사람을 한 보트에 태울 수 있으므로 index를 1 증가시켜 다음으로 가벼운 사람을 가리키도록 합니다.
  • answer++: 보트를 사용한 횟수를 증가시킵니다. 무거운 사람(people[i])은 항상 보트에 태워지므로 answer는 무조건 증가합니다.
• return answer;
  • 최소 보트 수를 반환합니다.

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

포인트

연속된 숫자들 중에 가장 큰 수를 구하는 문제였습니다. 스택을 이용하여 나왔던 숫자들 중에 가장 큰 수를 구하였습니다.

소스코드

import java.util.*;

class Solution {
    public String solution(String number, int k) {
        int len = number.length();
        Stack<Character> answer = new Stack<>();
        
        for(int i = 0; i < len; i++) {
            char cur = number.charAt(i);
            while(!answer.isEmpty() && answer.peek() < cur && k-- > 0) {
                answer.pop();
            }
            answer.push(cur);
        }
        
        StringBuilder result = new StringBuilder();
        while (!answer.isEmpty()) {
            result.append(answer.pop());
        }
        
        if (k > 0) {
            return result.reverse().toString().substring(0, result.toString().length() - k);
        }
        
        return result.reverse().toString();
    }
}

코드 설명

• 변수 초기화
  
  • len: number 문자열의 길이.
  • answer: 각 문자를 저장하고, 조건에 따라 제거 및 추가하여 최종 결과를 만들기 위한 Stack.
  • cur: 현재 반복에서 number의 각 문자를 나타내는 변수.
  • result: 최종 결과를 역순으로 저장한 후, 다시 정방향으로 반환하기 위한 StringBuilder.
• while(!answer.isEmpty() && answer.peek() < cur && k-- > 0) { answer.pop(); } answer.push(cur);
  
  • answer 스택이 비어있지 않고 answer의 맨 위 문자(peek())가 현재 문자 cur보다 작고 k가 0보다 크면 스택의 맨 위 문자를 제거(pop())합니다.
  • 현재 문자인 cur을 answer 스택에 추가합니다.
• while (!answer.isEmpty()) { result.append(answer.pop()); }
  스택에 남아 있는 문자들을 result에 추가합니다. 이때 pop()을 사용하기 때문에 result는 역순으로 문자가 추가됩니다.
• if (k > 0) { return result.reverse().toString().substring(0, result.toString().length() - k); }
  
  • k가 남아 있는 경우, 결과 문자열에서 k개의 문자를 제거합니다.
  • result.reverse()를 통해 정방향으로 만든 후, substring()으로 마지막 k개의 문자를 잘라 반환합니다.
• return result.reverse().toString();
  • k가 0일 경우, result를 정방향으로 뒤집어 반환합니다.