[프로그래머스] 퍼즐게임챌린지 , 여행경로 (java)

퍼즐게임챌린지

문제설명

난이도, 현재시간이 입력값으로 주어진다.

그때 가지고 있는 숙련도가 있는데 숙련도보다 난이도가 높다면 (이전시간+현재시간) * 차이나는 횟수 + 현재 시간을 총 더했을 때 제한 시간보다 작아야한다. 그때의 숙련도의 최소값을 구하면 된다

문제

 

해결 방법

나는 처음에 단순 구현으로 숙련도를 1부터 늘려가서 총 시간이 제한시간보다 작을 때까지 while문을 돌렸다.

그랬더니 시간초과가 났다... 그래서 숙련도의 최솟값을 찾는것, 그리고 1부터 늘려나가는건 비효율 적이라고 생각해서 그럴 때는 이진탐색 방법을 사용해야 한다고 깨달았다.

 

start와 end 는 최솟값이랑 최대값으로 설정을 해준다.

int start = Integer.MAX_VALUE;
int end = Integer.MIN_VALUE;
//처음 점이랑 끝점
for(int i=0; i<n; i++) {
    start = Math.min(start, diffs[i]);
    end = Math.max(end, diffs[i]);
}

 

 

그리고 이진탐색을 돌려준다.

제한 시간을 넘지 않는 한에서 숙련도를 계속해서 줄여 나가는 방법이다.

int answer = end; //기본은 가장 큰 값
while(start <= end ) {
    int mid = (start+end)/2;
    //mid가 숙련도가 됨
    //limit이 넘는지 넘지 않는지
    long time = 0; //총 시간
    int preTime =0; //그 전 시간
    for(int i=0; i<n; i++) { 
        if(mid >= diffs[i]) {
            time += times[i];
        }
        else {
           time += (times[i] + preTime)*(diffs[i] - mid)+ times[i];
        }
        preTime = times[i];
    }
    //총 시간이 리밋을 넘으면 mid +1을 해주기
    //최소값을 찾기 위해서 mid-1을 해주기
    if(time > limit) {
        start = mid +1;
    }
    else {
        answer = mid;
        end = mid-1;
    }
}

 

 

전체코드

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {

        int n = diffs.length;
        
        int start = Integer.MAX_VALUE;
        int end = Integer.MIN_VALUE;
        //처음 점이랑 끝점
        for(int i=0; i<n; i++) {
            start = Math.min(start, diffs[i]);
            end = Math.max(end, diffs[i]);
        }
        int answer = end; //기본은 가장 큰 값
        while(start <= end ) {
            int mid = (start+end)/2;
            //mid가 숙련도가 됨
            //limit이 넘는지 넘지 않는지
            long time = 0; //총 시간
            int preTime =0; //그 전 시간
            for(int i=0; i<n; i++) { 
                if(mid >= diffs[i]) {
                    time += times[i];
                }
                else {
                   time += (times[i] + preTime)*(diffs[i] - mid)+ times[i];
                }
                preTime = times[i];
            }
            //총 시간이 리밋을 넘으면 mid +1을 해주기
            //최소값을 찾기 위해서 mid-1을 해주기
            if(time > limit) {
                start = mid +1;
            }
            else {
                answer = mid;
                end = mid-1;
            }
        }
        
        
        return answer;
    }
}

 

깨달은점

n의 범위라던지 diff와 times의 범위가 딱 봐도 많은데..

완탐 방법은 분명 시간 초과가 날 것이라고 생각은 했지만 좋은 아이디어가 떠오르지 않았다. ㅜ_ㅜ

앞으로 범위가 고민되면 이진탐색을 사용해보자.

 

 

여행경로

문제설명

ICN공항에서 출발해서 주어진 항공을 모두 방문할 때, 방문하는 공항 경로를 return 해야한다.

단, 경로가 여러개일 경우 알파벳 순서가 앞서는 경로를 return 해야 한다.

해결방법

dfs를 이용해서 방문한 경로를 계속해서 담는다. 그리고 경로가 여러개 나올 수 있으니까 방문처리를 false함으로써 백트레킹을 해준다.

 

여기서 새롭게 알게 된 점은 정렬 방법이다.

나는 List<String[]> 타입으로 경로를 모두 담고 알파벳 순서가 앞서는 경로를 찾아야 하니까 Collections.sort를 해주고 싶었는데 List의 안에 타입이 배열이므로 저렇게 정렬을 해주면 오류가 난다.

Collections.sort(ans, Comparator.comparing(a->a[0]));

 

그때 이 방법을 사용해주었다.

이 방법은 a->a[0] 람다 표현식으로 정렬 기준을 설정하는 것이다.

Comparator.comparing은 지정된 키를 기준으로 비교해준다.

a는 내가 설정한 List의 각 요소인 String[]타입의 배열을 나타낸다. 그리고 a[0]는 첫번째 문자열 a[0]를 기준으로 정렬하는 것을 의미한다.

 

정리하자면 Comparator.comparing(a->a[0])로 정렬하면 ans 리스트는 알파벳 순으로 정렬된다.

 

전체코드

import java.util.*;

class Solution {
    static List<String[]> ans;
    static int n,idx;
    static boolean visited[];
    
    public String[] solution(String[][] tickets) {
        ans = new ArrayList<>();
        n = tickets.length;
        visited = new boolean[n];
        
        dfs(0, "ICN", "ICN", tickets);
        
                for(int i=0; i<idx; i++) {
            System.out.println(Arrays.toString(ans.get(i)));
        }
        
        
        // 경로 정렬 (알파벳 순)
        Collections.sort(ans, Comparator.comparing(a->a[0]));
        //Collections.sort(ans, Comparator.comparing(a -> a[0]));
        
        // 정렬된 첫 번째 경로를 answer로 반환
        return ans.get(0)[0].split(",");
    }

    // cnt: 현재 방문한 길이
    // path: 총 경로
    // t: 현재 방문한 티켓의 출발지
    static void dfs(int cnt, String path, String t, String[][] tickets) {
        if (cnt == n) {
            idx++;
            ans.add(new String[] {path});
            return;
        }
        
        // 현재 위치 t에서 출발하는 미방문 티켓 찾기
        for (int i = 0; i < n; i++) {
            if (t.equals(tickets[i][0]) && !visited[i]) {
                visited[i] = true;
                dfs(cnt + 1, path + "," + tickets[i][1], tickets[i][1], tickets);
                visited[i] = false;
            }
        }
    }
}

 

깨달은점

List가 sting배열을 포함할 때 정렬방법을 알았다.

dfs를 유연하게 사용하는 방법을 알았다.

path을 지정해서 계속해서 호출때마다 더해주는 것!

 

 

 

---

 

티스토리가 이런 이벤트를 하다니.. 작심 삼주 도전하실분 ㅎ_ㅎ

https://www.tistory.com/event/write-challenge-2024