[codeSignal] avoidObstacles

You are given an array of integers representing coordinates of obstacles situated on a straight line.

Assume that you are jumping from the point with coordinate 0 to the right. You are allowed only to make jumps of the same length represented by some integer.

Find the minimal length of the jump enough to avoid all the obstacles.

Example

For inputArray = [5, 3, 6, 7, 9], the output should be
avoidObstacles(inputArray) = 4.

Check out the image below for better understanding:

 

문제를 간단히 설명하면 장애물에 걸리지 않고 점프할 수 있는 최소값을 구하는게 문제다.

여기서 장애물이란 배열 5 3 6 7 9이다.

그리고 max값은 설정되지 않았다.

그리 어렵지 않는 문제지만... 많은걸 배울 수 있었다. 어떻게 하면 문제를 해결할 수 있는가에 대한 감을 잡은 것 같다.

제일먼저 배열을 정렬시켜줬다.

어차피 0부터 n까지 값을 구하는 것이기 때문에 정렬시키주는 편이 좋을 거라 생각했다.

 

그 다음으로는

어떻게 하면 장애물을 걸치지 않는지 생각해봤다.

간단히 생각해서 나눠지지 않는 값을 구하면 되는 문제였다.

즉, 3 5 6 7 9 는 불가능하다 왜냐하면 자기자신은 무조건 나누어 떨어지기 때문이다.

그러면 2같은 경우는  6에서 걸린다.

4같은 경우는 모든 경우의 수가 통과된다.

왜냐하면 0 4 8 으로 뛰어가는데 여기에 걸리는게 단 한개도 존재하지 않기 때문이다.

근데 만약에 장애물안에 범위로는 해결이 불가능하다면

가장 큰 장애물에 1을 더한 값이 정답이다.

왜냐하면 예를들어 2 와 3이 장애물이라고 했을때

0에서 4로 점프할시 아무것도 걸치지 않기 때문이다.

int avoidObstacles(int[] inputArray) {
    Arrays.sort(inputArray);
    int size = inputArray.length;
    int limit = inputArray[size-1]+1;
    
    boolean[] checking = new boolean[limit];
    
    for(int i = 1;i<limit;i++) {
        for(int j = 0 ; j< size;j++) {
            if (inputArray[j]%i == 0) {
                checking[i] = true;
                break;
            }
        }
    }
    
    List<Integer> list = new ArrayList<>();
    for(int i = 1; i<limit;i++) {
        if (!checking[i]) list.add(i);
    }
    
    if (list.isEmpty()) {
        return inputArray[size-1]+1;
    }
   
    
    return list.get(0);
}

 

이것만 30분이 넘다니 ㅜㅜ ;; 그래도 어떻게 코딩을 해야할지 알것 같다.

int avoidObstacles(int[] inputArray) {

    int jump = 1;
    boolean fail = true;
    
    while(fail) {
        jump++;
        fail = false;
        for(int i=0; i<inputArray.length; i++)
            if(inputArray[i]%jump==0) {
                fail = true;
                break;
            }
    }
    
    return jump;
}

복사되네... 하 그냥 jump변수를 만들고 더해주면 되는구나..ㅡㅡ;;;