[코딜리티/Java] FrogRiverOne

index가 시간이고, 그 index에 값이 낙엽이 떨어진 위치인 배열 A이 주어지고, X 위치까지 가는데 가능한 시간은 몇 초인지 구하는 문제.

class Solution {
    public static int[] map = new int[100001];
    public int solution(int X, int[] A) {
        Arrays.fill(map, -1);
        for (int i = 0; i < A.length; i++) {
            if (map[A[i]] == -1) {
                map[A[i]] = i;
            }
        }
        int result = 0;
        for (int i = 1; i <= X; i++) {
            if (map[i] == -1) {
                return -1;
            } else {
                result = Math.max(result, map[i]);
            }
        }
        return result;
    }
}

우선 N의 범위가 최대 10만이므로, 0 ~ 10만의 위치를 갖는 배열 map을 하나 선언한다.

그리고 -1로 초기화를 한 뒤, A의 값을 보면서 map의 index에 해당하는 최초시간을 넣어준다. 그리고 나서 map 배열을 1부터 X까지 loop하면서 중간에 만약 -1이 있으면 불가한 경우니 -1을 return하고, 아닌 경우 result값과 비교해서 max값을 result에 계속 세팅한다.

그리고 나서 result를 반환하는 식으로 해결했다.

아래는 다른 사람들이 주로 푼 풀이법이다. 최초에 HashSet에 1 ~ X까지 다 넣어두고, A를 loop하면서 A의 값을 하나씩 remove하면서 set이 size가 0이 되는 i를 반환하는 식으로 푸는 방법도 있다. 

class Solution {
    public int solution(int X, int[] A) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 1; i <= X; i++){
            set.add(i);
        }
        for(int j = 0; j < A.length; j++){
            set.remove(A[j]);
            if(set.size() == 0){
                return j;
            }
        }
        return -1;
    }
}

 이 코드는 아마 hash를 써서 조금은 시간은 더 걸릴 거 같긴하나, 내가 짠 코드에 비해 공간복잡도는 훨씬 효율적이긴 하다.