Computer Science Knowledge Storage

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

포인트

BFS를 활용한 문제였습니다. BFS/DFS 문제들은 중복 방문에 대한 처리를 확인해주셔야하며 OutOfRange가 나지 않기 위해
validation 체크를 진행해주셔야 합니다.

소스코드

import java.util.*;

class Solution {
    
    class Pair {
        int x, y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    int n, m;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    int[][] s;
    boolean[][] visited;
    int[][] globalMaps;
    Queue<Pair> q = new LinkedList<>();
    
    public void init() {
        s = new int[n][m];
        visited = new boolean[n][m];
        q.add(new Pair(0, 0));
        s[0][0] = 1;
        visited[0][0] = true;
    }
    
    public boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }
    
    public boolean canGo(int x, int y) {
        if(!inRange(x, y)) return false;
        if(visited[x][y] || globalMaps[x][y] == 0) return false;
        return true;
    }
    
    public void bfs() {
        while(!q.isEmpty()) {
            Pair cur = q.poll();
            for(int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(canGo(nx, ny)) {
                    q.add(new Pair(nx, ny));
                    visited[nx][ny] = true;
                    s[nx][ny] = s[cur.x][cur.y] + 1;
                }
            }
        }
    }
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        globalMaps = new int[n][m];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                globalMaps[i][j] = maps[i][j];
            }
        }
        
        init();
        bfs();
        
        if(s[n-1][m-1] == 0) {
            return -1;
        }
        return s[n-1][m-1];
    }
}

코드 설명

• 변수 설명
  • n: maps의 행
  • m: maps의 열
  • globalMaps: 다른 메소드에서 접근하기 위한 maps의 복사본
  • s: 각 위치까지의 이동 거리를 저장하는 2차원 배열입니다.
  • visited: i행 j열 방문했는지 확인하기위한 배열
  • q: BFS 탐색을 위한 큐로, 탐색해야 할 좌표를 저장합니다.

public void init() {
    s = new int[n][m];
    visited = new boolean[n][m];
    q.add(new Pair(0, 0));
    s[0][0] = 1;
    visited[0][0] = true;
}

public boolean inRange(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

public boolean canGo(int x, int y) {
    if(!inRange(x, y)) return false;
    if(visited[x][y] || globalMaps[x][y] == 0) return false;
    return true;
}

• init 메소드
  전역 변수 초기화 메소드
• inRange 메소드
  다음 탐색해야하는 좌표가 배열 내부인지 확인하기 위한 메소드
• canGo 메소드
  다음 탐색해야하는 좌표로 이동이 가능한지 확인하기 위한 메소드(배열 내인지, 방문한 좌표인지, 다음 좌표가 벽인지)

public void bfs() {
    while(!q.isEmpty()) {
        Pair cur = q.poll();
        for(int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if(canGo(nx, ny)) {
                q.add(new Pair(nx, ny));
                visited[nx][ny] = true;
                s[nx][ny] = s[cur.x][cur.y] + 1;
            }
        }
    }
}

• dx와 dy 테크닉을 통해 다음 탐색 좌표로 이동할 수 있으면 방문 처리 후 스텝을 1 증가시킵니다.

if (s[n-1][m-1] == 0) {
    return -1;
}
return s[n-1][m-1];

• s배열이 0이면 -1을 아니면 그 값을 반환합니다.

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

포인트

연결되어 있는 노드를 DFS로 이동하면서 트리의 갯수를 찾는 문제입니다.

union-find로도 문제를 풀 수 있겠지만 DFS를 통해 문제를 해결했습니다. 

소스코드

import java.util.ArrayList;

class Solution {
    boolean[] visited;
    int answer = 0;
    
    public void dfs(int n, int start, int[][] computers) {
        visited[start] = true;
        for(int i = 0; i < n; i++) {
            if (i == start) continue;
            if (!visited[i] && computers[start][i] == 1) {
                dfs(n, i, computers);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        visited = new boolean[n];
        for(int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(n, i, computers);
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

public void dfs(int n, int start, int[][] computers) {
    visited[start] = true; // 현재 컴퓨터를 방문 처리
    for(int i = 0; i < n; i++) { // 모든 컴퓨터를 탐색
        if (i == start) continue; // 자기 자신과의 연결은 무시
        if (!visited[i] && computers[start][i] == 1) { // 방문하지 않았고 연결된 경우
            dfs(n, i, computers); // 재귀 호출로 탐색
        }
    }
}

• visited[start] = true;
  현재 컴퓨터는 방문 처리합니다
• for문
  자기 자신과의 연결은 무시한 후 방문하지 않았고 연결된 경우 재귀 호출로 탐색합니다.

public int solution(int n, int[][] computers) {
    visited = new boolean[n]; // 방문 여부를 초기화
    for(int i = 0; i < n; i++) { // 모든 컴퓨터를 순회
        if (!visited[i]) { // 방문하지 않은 컴퓨터를 발견하면
            dfs(n, i, computers); // 해당 컴퓨터에서 연결된 네트워크 탐색
            answer++; // 네트워크 개수 증가
        }
    }
    return answer;
}

• visited 배열을 초기화 한 후 방문하지 않은 네트워크 중 연결된 네트워크의 갯수를 for문을 통해 순회합니다.

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

포인트

DFS를 활용하여 재귀함수를 통해 타겟 넘버를 찾는 코드입니다. 익숙하면 금방 풀리겠지만, 저는 재귀와 같은 부분이 많이 헷갈려 조금 헤맸던 문제였습니다. 재귀함수를 통해 문제를 풀 때에는 종료 조건을 제일 중요하게 생각해야합니다.

소스코드

class Solution {
    int[] arr;
    int targetNumber, answer = 0;
    
    public void findTargetNum(int num, int cnt) {
        if (num == targetNumber && cnt == arr.length) {
            answer++;
            return;
        }
        if (cnt >= arr.length) return;
        
        findTargetNum(num - arr[cnt], cnt + 1);
        findTargetNum(num + arr[cnt], cnt + 1);
    }
    
    public int solution(int[] numbers, int target) {
        int n = numbers.length;
        arr = new int[n];
        targetNumber = target;
        
        for(int i = 0; i < n; i++) {
            arr[i] = numbers[i];
        }
        
        findTargetNum(-1 * arr[0], 1);
        findTargetNum(arr[0], 1);
        
        return answer;
    }
}

코드 설명

public void findTargetNum(int num, int cnt) {
    if (num == targetNumber && cnt == arr.length) {
        answer++;
        return;
    }
    if (cnt >= arr.length) return;

    findTargetNum(num - arr[cnt], cnt + 1);
    findTargetNum(num + arr[cnt], cnt + 1);
}

• num은 현재까지 계산된 합계이며, cnt는 현재 탐색중인 배열의 인덱스 입니다.
• 종료조건
  • num == targetNumber && cnt == arr.length:
    현재까지 계산된 값이 targetNumber와 같고, 배열의 모든 원소를 사용했다면 경우의 수를 1 증가시킵니다.
  • cnt >= arr.length
    배열의 끝까지 도달했지만 targetNumber에 도달하지 못하면 탐색을 종료합니다.
• 재귀 호출
  • findTargetNum(num - arr[cnt], cnt + 1):
    현재 숫자를 빼는 경우를 탐색합니다.
  • findTargetNum(num + arr[cnt], cnt + 1):
    현재 숫자를 더하는 경우를 탐색합니다.

public int solution(int[] numbers, int target) {
    int n = numbers.length;
    arr = new int[n];
    targetNumber = target;

    for(int i = 0; i < n; i++) {
        arr[i] = numbers[i];
    }

    findTargetNum(-1 * arr[0], 1);
    findTargetNum(arr[0], 1);

    return answer;
}

• 배열을 복사하고 타겟 넘버를 복사합니다. 전역변수로 사용해서 findTargetNum에서 사용하기 위함입니다.
• findTargetNum(-1 * arr[0], 1)
  첫 번째 숫자를 빼는 경우부터 시작합니다.
• findTargetNum(arr[0], 1)
  첫 번째 숫자를 더하는 경우부터 시작합니다.

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

포인트

원형으로 이루어진 집들에서 이웃집 체크를 할 때에 첫번째 집과 마지막 집을 체크하는 것이 문제였습니다. 이를 위해 동적 계획법을 두가지로 나누어 두 부분의 최댓 값중 더 큰 값을 반환하는 로직으로 문제를 해결하였습니다.

소스코드

class Solution {
    
    public int solution(int[] money) {
        int n = money.length;
        /* 
         * 첫번째 집을 포함하고 마지막 집을 빼는 경우
         * n까지 고려했을 때의 돈의 최댓값
         */ 
        int[] dp_includeFirst = new int[n]; 
        dp_includeFirst[0] = money[0];
        dp_includeFirst[1] = Math.max(money[1], money[0]);
        for(int i = 2; i < n-1; i++) {
            dp_includeFirst[i] = Math.max(money[i] + dp_includeFirst[i-2], dp_includeFirst[i-1]);
        }
        
        /* 
         * 첫번째 집을 제외하고 마지막 집을 선택하는 경우
         * n까지 고려했을 때의 돈의 최댓값
         */ 
        int[] dp_excludeFirst = new int[n]; 
        dp_excludeFirst[0] = 0;
        dp_excludeFirst[1] = money[1];
        for(int i = 2; i < n; i++) {
            dp_excludeFirst[i] = Math.max(money[i] + dp_excludeFirst[i-2], dp_excludeFirst[i-1]);
        }
        
        return Math.max(dp_excludeFirst[n-1], dp_includeFirst[n-2]);
    }
}

코드 설명

첫 번째 집을 포함하고 마지막 집은 제외.

• dp_includeFirst[i]: 0번째 집부터 i번째 집까지 고려했을 때, 훔칠 수 있는 최대 금액.
• 초기값:
  • 첫 번째 집(money[0])은 반드시 포함됨: dp_includeFirst[0] = money[0].
  • 두 번째 집은 첫 번째 집과 비교해 더 큰 금액 선택: dp_includeFirst[1] = Math.max(money[1], money[0]).
• for (int i = 2; i < n-1; i++) { dp_includeFirst[i] = Math.max(money[i] + dp_includeFirst[i-2], dp_includeFirst[i-1]); }
  • i번째 집을 포함하거나 포함하지 않는 경우 중 최대값 계산:
    • money[i] + dp_includeFirst[i-2]: 현재 집(i)을 포함하고, i-2번째 집까지의 최대값을 더함.
    • dp_includeFirst[i-1]: 현재 집을 포함하지 않고, i-1번째 집까지의 최대값.
  • 마지막 집(n-1)은 포함되지 않으므로 제외.

첫 번째 집을 제외하고 마지막 집을 포함.

• dp_excludeFirst[i]: 첫 번째 집을 제외하고, 1번째 집부터 i번째 집까지 고려했을 때의 최대 금액.
• 초기값:
  • 첫 번째 집은 제외되므로, dp_excludeFirst[0] = 0.
  • 두 번째 집은 money[1]으로 초기화: dp_excludeFirst[1] = money[1].
• for (int i = 2; i < n; i++) { dp_excludeFirst[i] = Math.max(money[i] + dp_excludeFirst[i-2], dp_excludeFirst[i-1]); }
  • 마지막 집(n-1)까지 포함.
• return Math.max(dp_excludeFirst[n-1], dp_includeFirst[n-2]);
  • 최대값 반환합니다.

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

포인트

어렸을 때에 수학 문제를 풀 때에 가장자리에 1씩 두고 중간 값은 같은 열 위의 행과 같은 행 왼쪽 열의 합을 더해주는 방식을 사용했습니다.

소스코드

import java.util.*;

class Solution {
    private final int MOD = 1000000007;
    private final int DISABLE = -1;

    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n][m];
        for(int[] puddle: puddles) {
            dp[puddle[1]-1][puddle[0]-1] = DISABLE;
        }
        
        // init
        dp[0][0] = 1;
        for(int i = 1; i < m; i++) { // 가로
            if (dp[0][i] == DISABLE || dp[0][i-1] == DISABLE) {
                break;
            } else {
                dp[0][i] = 1;
            }
        }
        for(int i = 1; i < n; i++) { // 세로
            if (dp[i][0] == DISABLE || dp[i-1][0] == DISABLE) {
                break;
            } else {
                dp[i][0] = 1;
            }
        }
        
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(dp[i][j] == DISABLE) continue;
                
                if (dp[i-1][j] == DISABLE) {
                    dp[i][j] = dp[i][j-1];
                } else if (dp[i][j-1] == DISABLE) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = (dp[i-1][j] % MOD + dp[i][j-1] % MOD) % MOD;
                }
            }
        }
        
        return dp[n-1][m-1] % MOD;
    }
}

코드 설명

• int[][] dp = new int[n][m]; for(int[] puddle: puddles) { dp[puddle[1]-1][puddle[0]-1] = DISABLE; }
  
  • dp배열을 초기화합니다.
  • 웅덩이 위치에는 상수로 정의한 DISABLE로 설정합니다.
• 가장자리 초기화
  
  • 가로와 세로의 값을 초기화합니다.
  • 만약 웅덩이가 있다면 그 이후로는 처리를 하지 않습니다.

for(int i = 1; i < n; i++) {
    for(int j = 1; j < m; j++) {
        if(dp[i][j] == DISABLE) continue;
        
        if (dp[i-1][j] == DISABLE) {
            dp[i][j] = dp[i][j-1];
        } else if (dp[i][j-1] == DISABLE) {
            dp[i][j] = dp[i-1][j];
        } else {
            dp[i][j] = (dp[i-1][j] % MOD + dp[i][j-1] % MOD) % MOD;
        }
    }
}

• 현재 칸 (i, j)는 위 칸(dp[i-1][j])과 왼쪽 칸(dp[i][j-1])에서 올 수 있습니다.
• 웅덩이(DISABLE)가 있는 경우
  • 위 칸이 웅덩이면 왼쪽 경로만 고려합니다.
  • 왼쪽 칸이 웅덩이면 위쪽 경로만 고려합니다.
• dp[i][j]=(dp[i-1][j]%MOD+dp[i][j-1]%MOD)%MOD
  • 위와 왼쪽 모두 웅덩이가 아니라면 두 경로의 합을 계산합니다.
• return dp[n-1][m-1] % MOD;
  • 결과를 반환합니다.

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

포인트

삼각형 형태로 있는 숫자를 이차원 배열로 생각하여 문제를 풀었습니다. 현재 행의 i-1에 j열 또는 j-1의 합으로 문제를 풀었습니다.

여기에서 ArrayIndexOutOfBoundsException이 나오지 않게 체크를 해줍니다.

소스코드

int solution(int[][] triangle) {
        int len = triangle.length;
        int[][] ans = new int[len][len];
        for(int i = 0; i < len; i++) {
            for(int j = 0; j <= i; j++) {
                ans[i][j] = triangle[i][j];
            }
        }

        // init
        for(int i = 1; i < len; i++) {
            ans[i][0] = ans[i - 1][0] + triangle[i][0];
            ans[i][i] = ans[i - 1][i - 1] + triangle[i][i];
        }

        for(int i = 2; i < len; i++) {
            for(int j = 1; j < i; j++) {
                ans[i][j] = Math.max(ans[i-1][j-1], ans[i-1][j]) + triangle[i][j];
            }
        }

        int answer = Integer.MIN_VALUE;
        for(int i = 0; i < len; i++) {
            answer = Math.max(answer, ans[len-1][i]);
        }

        return answer;
    }
}

코드 설명

• 초기화
  
  • len: 삼각형의 높이.
  • ans: 각 위치까지의 최대 합을 저장하는 2차원 DP 배열.
  • 삼각형의 값을 그대로 ans 배열에 복사합니다.

for (int i = 1; i < len; i++) {
    ans[i][0] = ans[i - 1][0] + triangle[i][0]; // 삼각형 맨 왼쪽 경로
    ans[i][i] = ans[i - 1][i - 1] + triangle[i][i]; // 삼각형 맨 오른쪽 경로
}

삼각형의 왼쪽 끝 경로와 오른쪽 끝 경로는 고정된 값만 참조하므로 초기화합니다.

• 왼쪽 끝 경로는 위쪽 요소에서만 내려옵니다.
• 오른쪽 끝 경로도 마찬가지입니다.

for (int i = 2; i < len; i++) {
    for (int j = 1; j < i; j++) {
        ans[i][j] = Math.max(ans[i - 1][j - 1], ans[i - 1][j]) + triangle[i][j];
    }
}

• 중간 경로 계산
  
  • 위치 ans[i][j]는 위에서 내려올 수 있는 두 가지 경로 중 더 큰 값을 선택합니다:
    • ans[i-1][j-1]: 왼쪽 대각선 위에서 내려오는 경로.
    • ans[i-1][j]: 바로 위에서 내려오는 경로.
  • 이 중 더 큰 값을 선택해 현재 위치의 값을 갱신합니다.
• 마지막 행에서 가장 큰 값을 조회 후 반환합니다.

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

포인트

이 주어진 숫자 N을 여러 번 사용하여 특정 숫자 number를 만들기 위해 필요한 최소 사용 횟수를 찾는 문제를 해결합니다.
이것은 동적 계획법(Dynamic Programming, DP)을 활용하여 숫자 N을 점진적으로 조합해 나가는 방식입니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        // N을 i번 사용해서 나온 수 => dp[i] 에 저장
        List<Set<Integer>> dp = new ArrayList<>();
        
        for(int i = 0; i <= 8; i++) {
            dp.add(new HashSet<>());
        }
        
        for(int i = 1; i <= 8; i++) {
            // 5, 55, 555 ....
            int repeatN = Integer.parseInt(String.valueOf(N).repeat(i));
            dp.get(i).add(repeatN);
            
            // 사칙연산으로 찾기
            for (int j = 1; j < i; j++) {
                for (int a: dp.get(j)) {
                    for (int b : dp.get(i - j)) {
                        // +
                        dp.get(i).add(a + b);
                        // -
                        dp.get(i).add(a - b);
                        dp.get(i).add(b - a);
                        // *
                        dp.get(i).add(a * b);
                        // /
                        if (b != 0) dp.get(i).add(a / b);
                        if (a != 0) dp.get(i).add(b / a);
                    }
                }
            }
            
            if (dp.get(i).contains(number)) {
                return i;
            }
        }
        
        return -1;
    }
}

코드 설명

• 입력값 및 변수 초기화
  • dp[i]: 숫자 N을 정확히 i번 사용해서 만들 수 있는 모든 숫자의 집합입니다.
  • 문제에 나왔던대로 답은 8보다 클 수 없기에 dp는 최대 8번까지 숫자를 사용한 결과를 저장할 수 있도록 초기화합니다.
• int repeatN = Integer.parseInt(String.valueOf(N).repeat(i)); dp.get(i).add(repeatN);
  String.valueOf(N).repeat(i)를 통해 N을 i번 반복합니다.
  
  • String.valueOf(N).repeat(i): 숫자 N을 i번 반복한 문자열을 생성합니다.
  • 숫자 repeatN을 dp[i]에 추가합니다.
• 사칙연산으로 숫자 조합
  
  • j와 i - j로 숫자 N을 각각 j번, i-j번 사용해서 만든 숫자들을 조합하여 dp[i]를 채웁니다.
  • 각 숫자 쌍 (a, b)에 대해 사칙연산을 수행하고 결과를 dp[i]에 추가:
    • 덧셈: a + b
    • 뺄셈: a - b, b - a
    • 곱셈: a * b
    • 나눗셈: a / b, b / a (0으로 나누는 경우를 제외).
• if (dp.get(i).contains(number)) { return i; }
  
  • targetNumber가 있으면 현재 i를 반환합니다.

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