Computer Science Knowledge Storage

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
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를 정방향으로 뒤집어 반환합니다.

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

포인트

커서의 위치를 찾는 것이 포인트였습니다. 아무리해도 정답이 안되어서 서치를 진행하였는데 전체 왕복 횟수를 계산하는 로직입니다.

소스코드

class Solution {
    public int solution(String name) {
        int answer = 0;
        int len = name.length();

        int index;
        int move = len;
        
        for(int i = 0; i < len; i++){
            answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
            
            index = i + 1;
            while(index < len && name.charAt(index) == 'A'){
                index++;
            }
            
            move = Math.min(move, i * 2 + len - index);
            move = Math.min(move, (len - index) * 2 + i);
        }
        
        return answer + move;
    }
}

코드 설명

• for(int i = 0; i < len; i++) { answer += Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1); }
  
  • name.charAt(i) - 'A'는 'A'부터 현재 문자까지 위쪽 방향으로 이동할 때의 이동 횟수입니다.
  • 'Z' - name.charAt(i) + 1은 'Z'에서 반대 방향으로 이동하여 현재 문자에 도달하는 경우의 이동 횟수입니다.
  • 이 두 값 중 최소값을 취해 answer에 더합니다.
• 좌우 이동 횟수 계산
  • index는 현재 위치 i에서 시작하여, 연속된 'A' 구간의 끝을 찾기 위해 사용됩니다.
  • index가 문자열의 끝(len)에 도달하거나 'A'가 아닌 문자를 만나면 반복문을 종료합니다.
• move = Math.min(move, i * 2 + len - index); move = Math.min(move, (len - index) * 2 + i);
  
  • move는 현재까지 구한 좌우 이동의 최소값을 유지합니다.
  • i * 2 + len - index는 첫 번째 위치에서 i까지 이동한 후 다시 돌아와 남은 부분을 탐색하는 경우의 이동 거리입니다.
  • (len - index) * 2 + i는 반대 방향으로 탐색하다가 다시 i까지 돌아오는 경우의 이동 거리입니다.
  • 두 가지 방식 중 최소 이동 횟수를 move에 갱신합니다.
• return answer + move;
  • answer는 상하 이동 횟수의 총합이고, move는 최소 좌우 이동 횟수입니다. 이 둘을 합하여 최소 조이스틱 조작 횟수를 반환합니다.

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

포인트

그리디접근법으로 문제를 풀었습니다. 그리디는 정렬을 필요로하는 문제가 많습니다. 최적의 해를 구해야하기 때문입니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int len = lost.length;
        int answer= n - len;
        Set<Integer> clothes = new HashSet<Integer>();
        boolean[] visited = new boolean[len];
        
        for(int num : reserve) {
            clothes.add(num);
        }
        
        Arrays.sort(lost);
        for(int i = 0; i < len; i++) {
            if(clothes.contains(lost[i])) {
                answer++;
                visited[i] = true;
                clothes.remove(lost[i]);
            }
        }


        for(int i = len - 1; i >= 0; i--) {
            if (visited[i]) continue;
            
            if(clothes.contains(lost[i] + 1)) {
                clothes.remove(lost[i] + 1);
                answer++;
            } else if(clothes.contains(lost[i] - 1)) {
                clothes.remove(lost[i] - 1);
                answer++;
            }
        }


        return answer;
    }
}

코드 설명

• 초기화
  • n: 전체 학생 수.
  • len: lost 배열의 길이 (즉, 체육복을 잃어버린 학생들의 수).
  • answer: 체육수업에 참여할 수 있는 학생의 수 (초기값은 전체 학생 수에서 체육복을 잃어버린 학생 수를 뺀 값으로 설정됨).
  • clothes: 여벌 체육복을 가진 학생들의 번호를 저장할 HashSet 객체.
  • visited: lost 배열의 각 학생들이 여벌 체육복을 빌려서 해결되었는지 확인하는 배열.
• Set<Integer> clothes = new HashSet<Integer>(); for(int num : reserve) { clothes.add(num); }
  • reserve 배열을 순회하여 여벌 체육복을 가진 학생들의 번호를 clothes HashSet에 추가합니다. 이로써 여벌 체육복을 가진 학생들을 빠르게 찾을 수 있게 됩니다.
• for(int i = 0; i < len; i++) { if(clothes.contains(lost[i])) { answer++; visited[i] = true; clothes.remove(lost[i]); } }
  • 체육복을 잃어버린 학생 중 여벌 체육복이 있는 학생을 처리합니다.
• 두번째 for문
  • 여벌 체육복을 빌려주지 않은 학생들에게 체육복을 빌려주는 부분입니다.
  • visited[i]가 false인 학생들에 대해 여벌 체육복을 빌려줄 수 있는지 확인합니다.
  • lost[i] + 1 또는 lost[i] - 1이 여벌 체육복을 가진 학생 목록(clothes)에 있으면 해당 학생에게 체육복을 빌려줍니다.
  • 이때 clothes.remove(lost[i] + 1) 또는 clothes.remove(lost[i] - 1)로 여벌 체육복을 빌려준 학생을 제거하고, answer를 증가시킵니다.

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

포인트

모음 배열의 사전순으로 정렬합니다. 그 이후 인덱스를 찾습니다.

소스코드

import java.util.*;

class Solution {
    ArrayList<String> dict = new ArrayList<>();
    String std = "AEIOU";
    
    public void init(int num, int cnt, String cmd) {
        if(num == cnt) {
            dict.add(cmd);
            return;
        }
        
        for(int i = 0; i < 5; i++){
            init(num, cnt + 1, cmd + Character.toString(std.charAt(i)));
        }
    }
    
    public int solution(String word) {
        int answer = 0;
        
        for(int i = 1; i <= 5; i++) {
            init(i, 0, "");
        }
        Collections.sort(dict);
        int idx = 1;
        for(String s: dict) {
            if(s.equals(word)){
                answer = idx;
                return answer;
            }
            idx++;
        }
        return answer;
    }
}

코드 설명

• 클래스 변수
  
  • dict: "AEIOU"로만 이루어진 단어들을 담을 리스트입니다. 이 리스트는 가능한 모든 단어를 사전 순으로 정렬한 후, 주어진 단어의 순서를 찾는 데 사용됩니다.
  • std: 사용될 알파벳들이 담긴 문자열입니다. 즉, 'A', 'E', 'I', 'O', 'U'입니다.
• init 메서드
  
  • 이 함수는 재귀적으로 호출되어 cmd라는 문자열을 구성해 나가면서 모든 가능한 단어를 dict 리스트에 추가합니다.
  • num은 현재 단어의 길이를 나타내며, cnt는 현재까지 구성된 문자열의 길이를 나타냅니다. num과 cnt가 같으면, 즉 cmd가 길이에 맞게 완성되면 그 단어를 dict에 추가합니다.
  • for 루프는 각 자리마다 'A', 'E', 'I', 'O', 'U' 중 하나의 문자를 선택하여, 해당 문자를 cmd에 붙여가며 재귀적으로 호출합니다.
  • 이 방식은 길이 1부터 길이 5까지의 모든 가능한 단어를 생성합니다.
• solution 메서드
  • init 메서드를 호출하여 길이가 1부터 5까지인 모든 단어를 dict에 추가합니다.
  • 그런 후 dict를 사전 순으로 정렬합니다. 이때 사전 순 정렬은 문자열의 알파벳 순서에 맞춰 자동으로 이루어집니다.
  • 정렬된 dict에서 주어진 word와 일치하는 단어를 찾아 그 순서(idx)를 반환합니다. idx는 1부터 시작하는 순번입니다.
  • word가 발견되면 즉시 answer에 해당 값을 할당하고 반환합니다.

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

포인트

union-find 함수를 사용하여 연결된 전선의 갯수를 구하는 문제를 사용합니다. 끊어진 전선에 대하여 완전탐색을 진행합니다. 

소스코드

class Solution {
    public int[] parent;
    
    public void init(int n) {
        for(int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }
    
    public int findParent(int n) {
        if (parent[n] != n) {
            parent[n] = findParent(parent[n]);
        }
        return parent[n];
    }
    
    public void union(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        
        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }
    
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        int len = wires.length;
        for(int i = 0; i < len; i++) {
            // i는 끊는
            parent = new int[n+1];
            init(n);
            
            for(int j = 0; j < len; j++) {
                if(i == j) {
                    continue;
                }
                if(findParent(wires[j][0]) != findParent(wires[j][1])) {
                    union(wires[j][0], wires[j][1]);
                }
            }
            
            // 각 송전탑의 최상위 부모 노드 갱신 및 개수 세기
            Map<Integer, Integer> connect = new HashMap<>();
            for (int j = 1; j <= n; j++) {
                int root = findParent(j);
                connect.put(root, connect.getOrDefault(root, 0) + 1);
            }
            
            // 두 개의 그룹으로 나뉘었는지 확인하고 차이 계산
            if (connect.size() == 2) {
                List<Integer> counts = new ArrayList<>(connect.values());
                int diff = Math.abs(counts.get(0) - counts.get(1));
                answer = Math.min(answer, diff);
            }
            
        }
        return answer;
    }
}

코드 설명

• 클래스 변수
  
  • parent: 각 노드의 부모를 나타내는 배열입니다. Union-Find에서 사용되는 핵심 배열입니다.
• init 메서드
  
  • 부모 배열을 초기화합니다. 각 노드의 부모를 자기 자신으로 설정하여, 초기에는 모두 독립적인 집합으로 시작합니다.
• findParent 메서드
  
  • 주어진 노드 n의 부모를 찾는 함수입니다. 경로 압축(Path Compression) 기법을 사용하여 부모를 재귀적으로 찾아, 트리의 높이를 낮추고 효율성을 높입니다.
• union 메서드
  • 두 집합을 합치는 함수입니다. findParent를 이용해 각 노드의 부모를 찾고, 더 작은 부모를 선택하여 큰 부모를 그 아래로 합칩니다. 이로써 두 집합이 하나로 결합됩니다.
• solution 메서드
  
  • 전선 끊기:
    • 전선이 여러 개 있는데, 각 전선에 대해서 하나씩 끊어보고 그 결과를 확인합니다. i == j일 때는 i번째 전선만 끊고 나머지 전선은 그대로 연결합니다.
  • 전선 연결:
    • 각 전선의 두 끝을 union으로 연결합니다. 즉, 전선들이 연결된 노드를 하나의 네트워크로 묶습니다.
  • 네트워크 크기 계산:
    • 연결된 네트워크의 부모 노드(parent[j])를 기준으로 각 네트워크의 크기를 계산합니다. 부모 노드별로 네트워크에 속한 노드의 개수를 connect 맵에 저장합니다.
  • 두 네트워크로 분리되었는지 확인:
    • connect.size()가 2일 때, 즉 두 개의 독립적인 네트워크로 나누어진 경우에만 그 크기 차이를 계산합니다.
    • counts.get(0)과 counts.get(1)을 비교하여 두 네트워크의 크기 차이를 diff로 구하고, 이 값이 최소가 되도록 answer를 갱신합니다.

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

포인트

던전의 순서를 지정한 후 단순히 피로도를 비교하여 탐험 가능한 최대 던전 수를 구합니다.

소스코드

import java.util.*;

class Solution {
    boolean[] visited = new boolean[9];
    List<Integer> list = new ArrayList<>();
    int ans = 0, K = -1;
    int[][] pDungeons;
    
    public void find(int cur, int size) {
        if (cur == size) {
            int pirodo = K, stage = 0;
            for(int num: list) {
                if (pirodo >= pDungeons[num][0]) {
                    pirodo -= pDungeons[num][1];
                    stage++;
                }
            }
            
            ans = Math.max(ans, stage);
            return;
        }
        
        for (int i = 0; i < size; i++) {
            if (visited[i]) continue;
            list.add(i);
            visited[i] = true;
            
            find(cur + 1, size);
            
            visited[i] = false;
            list.remove(list.size() -1);   
        }
    }
    
    public int solution(int k, int[][] dungeons) {
        int n = dungeons.length;
        pDungeons = new int[n][2];
        for(int i = 0; i < n; i++) {
            pDungeons[i][0] = dungeons[i][0];
            pDungeons[i][1] = dungeons[i][1];
        }
        K = k;
        
        find(0, n);
        
        return ans;
    }
}

코드 설명

• 클래스 변수 선언
  
  • visited: 방문 여부를 추적하는 배열로, 최대 9개의 던전을 탐색할 수 있다고 가정하여 크기가 9로 설정됩니다.
  • list: 현재 탐색 중인 던전 순서의 인덱스를 저장합니다.
  • ans: 탐험 가능한 최대 던전 수를 저장하는 변수입니다.
  • K: 초기 피로도를 저장하는 변수입니다.
  • pDungeons: 입력으로 받은 던전 배열을 저장하는 2차원 배열입니다.
• 탐색 메서드 (find)
  
  • cur는 현재 재귀 깊이(탐색 중인 단계)를 나타내며, size는 던전의 총 개수입니다.
  • 기저 조건: cur가 size와 같으면 현재 순열에 대해 탐험을 시도합니다.
  • 탐험 가능 여부 확인: list에 저장된 인덱스 순서대로 던전을 탐험하며, 탐험할 수 있으면 피로도를 차감하고 stage를 증가시킵니다.
  • 최대 탐험 가능한 던전 수(ans)를 업데이트합니다.
  • for 루프: 방문하지 않은 던전을 탐색하여 list에 추가하고 재귀적으로 다음 탐색을 진행합니다. 이후 방문 표시를 해제하고 마지막 요소를 제거하여 상태를 되돌립니다.