developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 코테파이썬
  • 시계열
  • 카카오코테java풀이
  • 통계분석
  • SW역량테스트파이썬풀이
  • 시계열분석
  • MA모형
  • 삼성코테구현풀이
  • 삼성코테자바꿀팁
  • c++디자인패턴
  • 삼성코테기출자바풀이
  • AR모형
  • 운영체제인터럽트
  • 삼성코테파이썬준비
  • 삼성코테기출
  • c++ 빌더 패턴
  • 삼성코테자바준비
  • BOJ파이썬풀이
  • 삼성코테자바풀이
  • 삼성코테구현문제추천
  • 삼성코테파이썬
  • 삼성코테준비
  • 카카오코테
  • SW역량테스트파이썬
  • Arima
  • 백준파이썬풀이
  • ARIMA모형
  • 데이터분석
  • 삼성코테파이썬풀이
  • 통계학

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

2022 KAKAO TECH INTERNSHIP - 등산코스 정하기 (JAVA)
알고리즘/알고리즘문풀

2022 KAKAO TECH INTERNSHIP - 등산코스 정하기 (JAVA)

2022. 12. 1. 16:47

❓ 문제 - 2022 KAKAO TECH INTERNSHIP 등산코스 정하기- JAVA 풀이법

출처

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

📝 문제해결법

1. 문제

  • 출발구 ~ 산봉우리 ~ 출발구 까지의 하나의 등산 코스에서 각 지점을 지날 때 cost 중 최대 값을 그 등산코스의 intensity이다.
  • 여러 등산 코스 중 최소의 intensity 산봉우리 번호를 구하고, 만약 intensity가 같다면 최소 산봉우리를 구하여라. 

 

2. 해결 방법

  • 제한 사항이 n이 최대 50000이고, paths의 길이가 최대 200,000이므로 일반 dfs로 풀면 시간초과가 걸린다. 따라서 다익스트라와 intensity를 저장할 수 있는 dp를 이용해서 답을 구해야 한다.
  • 문제에서 등산 코스에서는 출발구 ~ 산봉우리 ~ 출발구까지를 하나의 등산코스로 보지만, 출발구 ~ 산봉우리까지의 최소 intensity를 구하면 산봉우리 ~ 출발구를 구해도 똑같이 최소 intensity 구해지므로 출발구 ~ 산봉우리까지만 구하면 된다.
  • 우선 일반 다익스트라 처럼 ArrayList를 배열로 만들어서 i번째 인덱스에는 i의 지점에 연결된 다른 노드의 지점의 번호와 cost를 저장한다.
    • 이때, 만약 paths의 s -> e 갈 때 들어갈 비용을 c라고 하면, 출발구 ~ 산봉우리로 구해야하고, 중간에 출발구나 산봉우리가 있으면 안되고, 출발구나 산봉우리가 아닌 경우 양방향 이동이 가능하다.
    • 따라서 다음과 같이 s가 출발이거나 e가 산봉우리이면 s -> e로, e가 산봉우리이거나 s가 출발지점이면 e -> s의 단방향의 path만 list에 넣고, 그 외의 경우라면 양방향 이동이 가능하도록 list에 넣어준다.
  • 일반 다익스트라로 구현하며 intensity에 distance처럼 값을 저장한다.
  • queue에 값을 넣을 때 연결되어 있고 만약 현재 노드 지점을 거쳐 연결된 지점으로 이동할 때 계산된 intensity가 원래 연결된 지점에 저장된 intensity[next.a]보다 작다면 작은 값으로 갱신해준다.
  • 마지막에 intensity가 같은 경우도 있으므로,  산봉우리 숫자를 기준으로 오름차순으로 정렬하고 intensity가 작은 경우로 answer에 산봉우리 숫자, 최소 intensity를 구한다.

3. 느낀점

  • 처음에 DFS+DP로만 구했는데 이게 DP를 잘 활용하지 못 해서 자꾸 시간초과랑 메모리 초과가 났다..
  • 그래서 카카오 해설을 봤는데 다익스트라 + DP로 해결한다는 것을 보고 빨리 수정을 했는데 자꾸 이상한 값이 나왔다.
  • 내가 우려했던 부분은 출발구 ~ 산봉우리 사이에 만약 출발구나 산봉우리가 있다면 어떻게 처리하지 였는데... 다른 사람의 코드를 보니 list에 path에 대한 정보를 넣을 때 a지점 -> b지점의 path를 경우를 나누어서 저장한다는 것을 보고 의문이 해결이 되었다..
  • 출발구 -> 산봉우리라는 명확한 출발지와 도착지에 cost를 구하는 문제이므로 다익스트라로 풀어도 되는 구나라고 깨달았다..!!!
  • 2일 동안 끙끙 거렸는데 정말 좋은 문제를 푼 것 같다..

 

💻 소스코드 (JAVA)

import java.util.*;

class Solution {
    public static class Node {
        public int a;
        public int cost;
        public Node(int a, int cost){
            this.a = a;
            this.cost = cost;
        }
    }
    public static ArrayList<Node>[] list;
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        list = new ArrayList[n+1];
        for(int i=0;i<=n;i++){
            list[i] = new ArrayList<Node>();
        }
        
        for(int[] path:paths){
            int s = path[0];
            int e = path[1];
            int c = path[2];
            if(isGate(s, gates) || isSummit(e, summits)){
                list[s].add(new Node(e, c));
            } else if(isGate(e, gates) || isSummit(s, summits)){
                list[e].add(new Node(s, c));
            } else {
                list[s].add(new Node(e, c));
                list[e].add(new Node(s, c));
            }
        }
                      
                      
        return dijkstra(n, gates, summits);
    }
                      
    public static int[] dijkstra(int n, int[] gates, int[] summits){
        Queue<Node> q = new LinkedList<>();
        int[] intensity = new int[n+1];
        
        Arrays.fill(intensity, Integer.MAX_VALUE);
        for(int g:gates){
            intensity[g] = 0;
            q.add(new Node(g, 0));
        }
        
        while(!q.isEmpty()){
            Node node = q.poll();
            
            if(node.cost > intensity[node.a]) continue;
            for(int i=0;i<list[node.a].size();i++){
                Node next = list[node.a].get(i);
                int temp = Math.max(intensity[node.a], next.cost);
                if(intensity[next.a] > temp){
                    intensity[next.a] = temp;
                    q.add(new Node(next.a, temp));
                }
            }   
        }

        int[] answer = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
        Arrays.sort(summits);
        for(int s:summits){
            if(intensity[s] < answer[1]){
                answer[0] = s;
                answer[1] = intensity[s];
            }
        }
        
        return answer;
    }
    
    
    public static boolean isGate(int g, int[] gates){
        for(int gate:gates){
            if(g == gate) return true;
        }
        
        return false;
    }
    
    public static boolean isSummit(int s, int[] summits){
        for(int summit:summits){
            if(s == summit) return true;
        }
        return false;
    }
    
}

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 수들의 합4 2015번 (JAVA)  (7) 2022.12.07
BOJ - 거짓말 1043번 (JAVA)  (0) 2022.12.06
프로그래머스 코딩테스트 연습 - 여행경로 (JAVA)  (0) 2022.11.29
프로그래머스 코딩테스트 연습 - 카펫 (JAVA)  (0) 2022.11.22
프로그래머스 코딩테스트 연습 - 디스크컨트롤러 (JAVA)  (0) 2022.10.30
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 수들의 합4 2015번 (JAVA)
    • BOJ - 거짓말 1043번 (JAVA)
    • 프로그래머스 코딩테스트 연습 - 여행경로 (JAVA)
    • 프로그래머스 코딩테스트 연습 - 카펫 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바