[Codility] Lesson4 - FrogRiverOneFind (Java)

문제

Find the earliest time when a frog can jump to the other side of a river.

 

FrogRiverOne coding task - Learn to Code - Codility

풀이

O(N^2)(A배열 하나를 확인할 때마다 모든 위치에 나뭇잎이 놓였는지 확인하는 방법)으로 풀면 성능 테스트에서 medium_range부터 Fail을 받기 때문에 O(N)으로 리팩토링했다.

import java.util.*;

class Solution {
    public int solution(int X, int[] A) {
        int answer = 0;

        int[] visited = new int[X+1];
        Arrays.fill(visited, Integer.MAX_VALUE);
        
        for(int i=0; i< A.length; i++) {
            visited[A[i]] =  Math.min(visited[A[i]], i);
        }

        for(int i=1; i< visited.length; i++) {
            if(visited[i] == Integer.MAX_VALUE) return -1;
            answer = Math.max(visited[i], answer);
        }
        return answer;
    }
}

 

• visited에는 Bank 까지 가기 위한 거리 1부터 X까지 위치에 나뭇잎이 놓인 제일 빠른 시간을 저장한다. 
• A배열을 모두 확인해서 해당하는 visited를 다 채운 후, visited를 한바퀴 돌며 확인한다.
  • 만약 visited에 초기값인 Integer.MAX_VALUE가 저장되어 있다면, 이는 나뭇잎이 놓이지 않았다는 것으로 개구리가 건널 수 없어 -1을 반환한다.
  • 그렇지 않다면, 모든 visited[i](i번째 위치에 나뭇잎이 놓인 최초의 시간)값 중 가장 큰 값이 모든 위치에 나뭇잎이 놓인 시간을 의미하기 때문에 answer을 계속해서 큰값으로 갱신하여 반환한다.

Codility를 처음 풀어봤는데 문제가 영어로 되어있어서 괜히 문제가 어렵게 느껴졌다. 엄청 어려운 문제는 아니었다! 코드를 제출하면 아래 사진처럼 정확도와 성능 테스트의 결과가 나온다.

Analysis 창에서 내 코드의 시간 복잡도를 알려주는게 좋았다. Performance tests 모두 OK 받기 위해 코드를 리팩토링하는 재미(?)가 있을 거 같다.