[JAVA] 프로그래머스 LEVEL3 등산코스 정하기

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

코딩테스트 연습 > 2022 KAKAO TECH INTERNSHIP > 등산코스 정하기

문제 분석

난이도: LEVEL3

 

문제분석

이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity

출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 한다.

등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 한다. 

 

풀고 보니까 다익스트라 같기도..? 

 

틀린 코드(51.6)

import java.util.*;
class Solution {
    static ArrayList<int[]>[] graph;
    static int [][] start;
    static int [][] end;
    static int min_intensity = Integer.MAX_VALUE;
    static int min_point = Integer.MAX_VALUE;
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        start = new int [n+1][n+1];
        end   = new int [n+1][n+1];
        for(int i = 0; i <= n; i++){
            Arrays.fill(start[i], Integer.MAX_VALUE);
            Arrays.fill(end[i], Integer.MAX_VALUE);
        }
        // 그래프 초기화 
        graph = new ArrayList[n+1];
        for(int i = 0; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        makeGraph(paths); // 양방향 그래프 만들기 
        up(n, gates, summits);   // 시작 위치 -> 산봉우리 
        down(n, gates, summits); // 산봉우리 -> 시작 위치 
        
        calculate(gates, summits); // 계산 
        
        return new int [] {min_point, min_intensity};
    }
    public static void calculate(int [] gates, int [] summits){
        for(int i = 0; i < gates.length; i++){
            int gate = gates[i];
            for(int j = 0; j < summits.length; j++){
                int summit = summits[j];
                int max = Math.max(start[gate][summit], end[summit][gate]);
                if(min_intensity > max){
                    min_intensity = max;
                    min_point = summit;
                }
                else if(min_intensity == max & min_point > summit){
                    min_point = summit;
                }
            }
        }
    }
    public static void makeGraph(int [][] paths){ // 양방향 그래프 만들기 
        for(int i = 0; i < paths.length; i++){
            int v1 = paths[i][0];
            int v2 = paths[i][1];
            int cost = paths[i][2];
            graph[v1].add(new int []{v2, cost});
            graph[v2].add(new int []{v1, cost});
        }
    }
    public static void down(int n, int [] gates, int [] summits){ // 산봉우리 -> 시작 위치
        Queue<int[]> q = new LinkedList<>();
        int [] visited = new int [n+1];
        for(int i = 0; i < summits.length; i++){
            int st = summits[i];
            Arrays.fill(visited, Integer.MAX_VALUE);
            visited[st] = 0;
            q.add(new int []{st, 0});
            while(!q.isEmpty()){
                int [] cur = q.poll();
                boolean flag = false;
                for(int j = 0; j < gates.length; j++){ // 시작 위치 도착 
                    if(gates[j] == cur[0]){
                        if(end[st][gates[j]] > cur[1]){
                            end[st][gates[j]] = cur[1];
                        }
                        flag = true;
                        break;
                    }    
                }
                if(flag) continue;
                for(int j = 0; j < graph[cur[0]].size(); j++){
                    int [] next = graph[cur[0]].get(j);
                    int max = Math.max(cur[1], next[1]);
                    if(max < visited[next[0]]){
                        visited[next[0]] = max;
                        q.add(new int []{next[0], max});
                    }
                }
            }    
        }    
    }
    public static void up(int n, int [] gates, int [] summits){ // 시작 위치 -> 산봉우리 
        // 0: 현재 정점 1: 최대 intensity 
        Queue<int[]> q = new LinkedList<>();
        int [] visited = new int [n+1];
         
        for(int i = 0; i < gates.length; i++){
            int st = gates[i];
            Arrays.fill(visited, Integer.MAX_VALUE);
            visited[st] = 0;
            q.add(new int []{st, 0});
            while(!q.isEmpty()){
                int [] cur = q.poll();
                boolean flag = false;
                for(int j = 0; j < summits.length; j++){ // 산봉우리 도착 
                    if(summits[j] == cur[0]){
                        if(start[st][summits[j]] > cur[1]){
                            start[st][summits[j]] = cur[1];
                        }
                        flag = true;
                        break;
                    }
                }
                if(flag) continue;
                for(int j = 0; j < graph[cur[0]].size(); j++){
                    int [] next = graph[cur[0]].get(j);
                    int max = Math.max(cur[1], next[1]);
                    if(max < visited[next[0]]){
                        visited[next[0]] = max;
                        q.add(new int []{next[0], max});
                    }
                }
            }
        }
    }
}

 

시간초과가 4개 

메모리초과가 5개 

 

원인 파악하기 

 

메모리 초과의 원인은 2가지로 예상된다. 

1. Queue에 데이터가 너무 많이 쌓여서 

2. n이 최대 50000인데 2차원 배열이니까 2500000000 크기의 배열 2개 총 5000000000 메모리를 엄청 잡아 먹어서 

 

2차원 배열을 사용하는 부분을 주석 처리하니까 메모리 초과는 발생하지 않는다. 

메모리 부분은 역시 2차원 배열이 문제였다. 

하지만 2차원 배열을 계산하는 부분이 없어도 시간 초과도 발생하는 거 보니까 등산 코스를 계산하는 부분도 고쳐야

할듯하다.

 

틀린 코드2(67.7)

import java.util.*;
class Solution {
    static ArrayList<int[]>[] graph;
    static ArrayList<int[]> result = new ArrayList<>();
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        // 그래프 초기화 
        graph = new ArrayList[n+1];
        for(int i = 0; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        makeGraph(paths); // 양방향 그래프 만들기 
        up(n, gates, summits);   // 시작 위치 -> 산봉우리 
        calculate(); // 계산 
        return new int [] {result.get(0)[1], result.get(0)[0]};
    }
    public static void calculate(){
        Collections.sort(result, (o1,o2) -> {
            if(o1[0] != o2[0]) return o1[0] - o2[0];
            return o1[1] - o2[1];
        });
    }
    public static void makeGraph(int [][] paths){ // 양방향 그래프 만들기 
        for(int i = 0; i < paths.length; i++){
            int v1 = paths[i][0];
            int v2 = paths[i][1];
            int cost = paths[i][2];
            graph[v1].add(new int []{v2, cost});
            graph[v2].add(new int []{v1, cost});
        }
    }
    public static void up(int n, int [] gates, int [] summits){ // 시작 위치 -> 산봉우리 
        // 0: 현재 정점 1: 최대 intensity 
        PriorityQueue <int[]> q = new  PriorityQueue<>((o1, o2) -> { return o1[1] - o2[1];});
        int [] visited = new int [n+1];
         
        for(int i = 0; i < gates.length; i++){
            int st = gates[i];
            Arrays.fill(visited, Integer.MAX_VALUE);
            visited[st] = 0;
            q.add(new int []{st, 0});
            while(!q.isEmpty()){
                int [] cur = q.poll();
                boolean flag = false;
                for(int j = 0; j < summits.length; j++){ // 산봉우리 도착 
                    if(summits[j] == cur[0]){
                        result.add(new int[]{cur[1], summits[j]});
                        flag = true;
                        break;
                    }
                }
                if(flag) continue;
                for(int j = 0; j < graph[cur[0]].size(); j++){
                    int [] next = graph[cur[0]].get(j);
                    int max = Math.max(cur[1], next[1]);
                    if(max < visited[next[0]]){
                        visited[next[0]] = max;
                        q.add(new int []{next[0], max});
                    }
                }
            }
        }
    }
}

 

틀린코드1에서 개선사항

 

1. 큐 → 우선순위 큐 사용 

intensity가 낮은 값이 먼저 큐에서 빠져나오도록 우선순위 큐를 사용 

그래프에서 다음 경로로 이동하는 과정에서 많은 데이터가 필터링되어 큐에 추가되지 않도록 할 수 있었다.  

 

2. 출발지  → 산봉우리 / 산봉우리 → 출발지

2번 계산을 1번으로 바꿈

어차피 출발지 → 산봉우리 / 산봉우리 → 출발지 모두 같은 intensity 값이 나오게 된다. 

 

3. intensity, 산봉우리 기록을 2차원 배열 → ArrayList 

25/0000/0000 이라는 큰 크기의 배열에 기록보단 산봉우리에 도착했을 때 intensity와 산봉우리를 리스트에 기록하고 정렬해서 꺼내는 게 더 메모리 효율성이 좋겠다는 판단 

 

 

이제 시간 초과만 5개 ...

틀린 코드3(67.7)

import java.util.*;
class Solution {
    static ArrayList<int[]>[] graph;
    static int min_point = Integer.MAX_VALUE; // 산봉우리 
    static int min       = Integer.MAX_VALUE; // intensity
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        // 그래프 초기화 
        graph = new ArrayList[n+1];
        for(int i = 0; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        makeGraph(paths); // 양방향 그래프 만들기 
        up(n, gates, summits);   // 시작 위치 -> 산봉우리 
        
        return new int [] {min_point, min};
    }
    
    public static void makeGraph(int [][] paths){ // 양방향 그래프 만들기 
        for(int i = 0; i < paths.length; i++){
            int v1 = paths[i][0];
            int v2 = paths[i][1];
            int cost = paths[i][2];
            graph[v1].add(new int []{v2, cost});
            graph[v2].add(new int []{v1, cost});
        }
    }
    public static void up(int n, int [] gates, int [] summits){ // 시작 위치 -> 산봉우리 
        // 0: 현재 정점 1: 최대 intensity 
        PriorityQueue <int[]> q = new  PriorityQueue<>((o1, o2) -> { return o1[1] - o2[1];});
        int [] visited = new int [n+1];
         
        for(int i = 0; i < gates.length; i++){
            int st = gates[i];
            Arrays.fill(visited, Integer.MAX_VALUE);
            visited[st] = 0;
            q.add(new int []{st, 0});
            while(!q.isEmpty()){
                int [] cur = q.poll();
                boolean flag = false;
                for(int j = 0; j < summits.length; j++){ // 산봉우리 도착 
                    if(summits[j] == cur[0]){
                        if(min > cur[1]){
                            min = cur[1];
                            min_point = summits[j];
                        }
                        else if(min == cur[1] && min_point > summits[j]){
                            min_point = summits[j];
                        }
                        flag = true;
                        break;
                    }
                }
                if(flag) continue;
                for(int j = 0; j < graph[cur[0]].size(); j++){
                    int [] next = graph[cur[0]].get(j);
                    int max = Math.max(cur[1], next[1]);
                    if(max < visited[next[0]]){
                        visited[next[0]] = max;
                        q.add(new int []{next[0], max});
                    }
                }
            }
        }
    }
}

 

근데 결과를 보자마자 딱 드는 생각이 굳이 리스트에 넣고 정렬을 해야 하나? 

매번 결과가 나올 때마다 if else 문으로 intensity와 산봉우리 비교를 통한 결과 도출을 하면 되겠다는 아이디어가 떠올랐다. 

 

하지만 결과는 동일

이러면 출발지에서 산봉우리로 올라가는 로직에서 개선을 해야 하는구나를 알 수 있다.

 

틀린 코드4(93.5)

import java.util.*;
class Solution {
    static ArrayList<int[]>[] graph;
    static int min_point = Integer.MAX_VALUE; // 산봉우리 
    static int min       = Integer.MAX_VALUE; // intensity
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        // 그래프 초기화 
        graph = new ArrayList[n+1];
        for(int i = 0; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        makeGraph(paths); // 양방향 그래프 만들기 
        up(n, gates, summits);   // 시작 위치 -> 산봉우리 
        return new int [] {min_point, min};
    }
    
    public static void makeGraph(int [][] paths){ // 양방향 그래프 만들기 
        for(int i = 0; i < paths.length; i++){
            int v1 = paths[i][0];
            int v2 = paths[i][1];
            int cost = paths[i][2];
            graph[v1].add(new int []{v2, cost});
            graph[v2].add(new int []{v1, cost});
        }
    }
    public static void up(int n, int [] gates, int [] summits){ // 시작 위치 -> 산봉우리 
        // 0: 현재 정점 1: 최대 intensity 
        PriorityQueue <int[]> q = new  PriorityQueue<>((o1, o2) -> { return o1[1] - o2[1];});
        int [] visited = new int [n+1];
        
        Arrays.fill(visited, Integer.MAX_VALUE);
        for(int i = 0; i < gates.length; i++){
            q.add(new int []{gates[i], 0});
            visited[gates[i]] = 0;
        }
        while(!q.isEmpty()){
            int [] cur = q.poll();
            boolean flag = false;
            for(int j = 0; j < summits.length; j++){ // 산봉우리 도착 
                if(summits[j] == cur[0]){
                    if(min > cur[1]){
                        min = cur[1];
                        min_point = summits[j];
                    }
                    else if(min == cur[1] && min_point > summits[j]){
                        min_point = summits[j];
                    }
                    flag = true;
                    break;
                }
            }
            if(flag) continue;
            for(int j = 0; j < graph[cur[0]].size(); j++){
                int [] next = graph[cur[0]].get(j);
                int max = Math.max(cur[1], next[1]);
                if(max < visited[next[0]]){
                    visited[next[0]] = max;
                    q.add(new int []{next[0], max});
                }
            }
        }
    }
}

 

이전 로직들은 for문에서 각 출발지마다 비교를 했는데

이번엔 for문으로 출발지들을 먼저 넣어주고 다익스트라를 돌리도록 개선했다. 

 

결과는 21번 테스트케이스 빼고 전부 통과하였다

 

정답 코드

import java.util.*;
class Solution {
    static ArrayList<int[]>[] graph;
    static int min_point = Integer.MAX_VALUE; // 산봉우리 
    static int min       = Integer.MAX_VALUE; // intensity
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        // 그래프 초기화 
        graph = new ArrayList[n+1];
        for(int i = 0; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        makeGraph(paths); // 양방향 그래프 만들기 
        up(n, gates, summits);   // 시작 위치 -> 산봉우리 
        return new int [] {min_point, min};
    }
    
    public static void makeGraph(int [][] paths){ // 양방향 그래프 만들기 
        for(int i = 0; i < paths.length; i++){
            int v1 = paths[i][0];
            int v2 = paths[i][1];
            int cost = paths[i][2];
            graph[v1].add(new int []{v2, cost});
            graph[v2].add(new int []{v1, cost});
        }
    }
    public static void up(int n, int [] gates, int [] summits){ // 시작 위치 -> 산봉우리 
        
        Arrays.sort(summits);
        
        // 0: 현재 정점 1: 최대 intensity 
        PriorityQueue <int[]> q = new  PriorityQueue<>((o1, o2) -> { 
            if(o1[1] != o2[1]) return o1[1] - o2[1];
            return o1[0] - o2[0]; });
        
        int [] visited = new int [n+1];
        Arrays.fill(visited, Integer.MAX_VALUE);
        
        for(int i = 0; i < gates.length; i++){
            q.add(new int []{gates[i], 0});
            visited[gates[i]] = 0;
        }
        while(!q.isEmpty()){
            int [] cur = q.poll();
            // 만약 이미 산봉우리에 도착한 최소 intensity 보다 현재까지 등산한 intensity 가 많으면 의미없다.
            if(cur[1] > min) continue;
            
            boolean flag = false;
            for(int j = 0; j < summits.length; j++){ // 산봉우리 도착 
                if(summits[j] == cur[0]){
                    if(min > cur[1]){
                        min = cur[1];
                        min_point = summits[j];
                    }
                    else if(min == cur[1] && min_point > summits[j]){
                        min_point = summits[j];
                    }
                    flag = true;
                    break;
                }
            }
            if(flag) continue;
            
            for(int j = 0; j < graph[cur[0]].size(); j++){
                int [] next = graph[cur[0]].get(j);
                int max = Math.max(cur[1], next[1]);
                if(visited[next[0]] > max){
                    visited[next[0]] = max;
                    q.add(new int []{next[0], max});
                }
            }
        }
    }
}

 

해당 코드를 추가하여 통과했다. 

 // 만약 이미 산봉우리에 도착한 최소 intensity 보다 현재까지 등산한 intensity 가 많으면 의미없다.
 if(cur[1] > min) continue;