FrogRiverOne

HashSet을 이용한 문제 풀이

Codility에서 내가 푼 문제를 못보는줄 알고있었는데
결과창 링크가 따로 생성되서 그 링크에 들어가면 결과를 볼 수 있는걸
어제 알았다 :(

문제를 요약하자면 징검다리를 건너려는
개구리가 1초마다 특정 위치에 떨어지는 나뭇잎을 밟고 갈때
X지점으로 가기위해 건널수 있는 가장 빠른 길을 반환하는거였다.

내가 생각한 방법은 이렇게 생각했다.

배열 A[i]에서 중복되는 값은 모두 0으로 만들었다.

문제에서는 원소가 같을 경우 같은 징검다리에 나뭇잎이 떨어지는 것을 의미하기 때문에 의미가 없기 때문이다.

그 다음 목표지점 X에 건널경우 개구리는 1 -> 2 -> 3 … -> X 로 이동경로를 지나쳐 도달하게되는데
이걸 1부터 X까지의 합으로 생각해서 sum을 계산했다. (이전의 포스팅인 PermMissingElem 에서 배운걸 이용해봤다.)

계산된 sum에서 배열 원소를 처음부터 하나씩 빼고 sum이 0이 되면 해당 i값을 반환한다.

import java.util.*;
 
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
 
class Solution {
    public int solution(int X, int[] A) {
        // write your code in Java SE 8
        for (int i=0 ; i<A.length; i++){
            for(int j=0; j<A.length; j++){
                if(A[i]==A[j] && i!=j && A[i]!=0)
                {
                    A[j] = 0;
                }
            }
        }
        
        int sum = (X*(X+1))/2;
        int flag = 0;
        
        for (int i=0; i<A.length; i++){
 
            sum -= A[i];
            if (sum == 0){
                flag = i;
                i = A.length;
            }
        }
        if(sum >0)
        {
            return -1;
        }
        
        return flag;
    }
}

결과는 54점 퍼포먼스 부분 점수가 낮았다.
중복을 없애는 과정에서 배열의 길이가 클 경우에는 시간이 오래걸려 그런것이었다.

100% 예제를 봤는데 HashSet을 이용한 예제 였다.

import java.util.*;
 
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
 
class Solution {
    public int solution(int X, int[] A) {
    Set<Integer> marks = new HashSet<>();
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] <= X) {
            marks.add(A[i]);
            if (marks.size() == X) {
                return i;
            }
        }
    }
 
    return -1;
}
 
}

HashSet을 이용해 X보다 자거나 같은 원소들을 추가해
중복이 없는 marks를 만들고 marks의 사이즈와 X값이 일치할때!
i값을 반환하는 것이다.

HashSet은 처음 사용해 봤는데 Hash에 관한 정리를 다시해봐야 겠다.

FrogRiverOne

JIHUN HONG