도로에 가로등 전구 달기

흠 프로그래머스 모의테스트 문제를 풀어보는데

주로 효율성 검사에서 항상 문제가 생기네요 ㅠㅠ

효율성 생각해서 문제 푸는건 항상 어려운것 같습니다 ㅋㅋ

아무튼 오늘 문제는 도로에 가로등 전구 달기!

[문제]

서울시에 일직선 모양의 새로운 도로가 생겼습니다. 새로운 도로의 전체 길이는 L이고 도로에는 총 n개의 가로등이 세워졌습니다. 이 도로의 모든 가로등에 전구를 사서 달려고 합니다.

 *  전구를 선택하는 기준은 다음과 같습니다.

- 전구는 길의 좌측, 우측 방향으로 각각 d 길이만큼 길을 밝힐 수 있고, d는 자연수입니다.

- 모든 가로등에는 같은 종류(d 값이 같은)의 전구를 달아야 합니다.

- 안전을 위하여 도로위에 어두운 부분이 있어서는 안 됩니다.

- 이때, d 값이 충분히 크다면 전체 도로를 밝게 비출 수 있지만, d 값이 작아진다면 도로 위에 빛이 닿지 않는 부분이 생길 수도 있습니다. 

- 따라서, 도로 위에 어두운 부분이 생기지 않도록 하는 d 값 중 최솟값을 구하려고 합니다.

- 전체 도로의 길이 L, 가로등이 세워져 있는 위치가 들어있는 배열 v가 매개변수로 주어질 때, 위의 모든 조건을 만족하는 d 의 최솟값을 return 하도록 solution 함수를 완성해주세요.

[제한사항]

- L은 1 이상 1,000,000,000 이하의 자연수입니다.

- v에는 가로등의 위치정보가 들어있습니다.

- 가로등의 위치는 0 이상 l 이하의 정수이며, 같은 위치에 2개 이상의 가로등이 있는 경우는 주어지지 않습니다.

- 가로등의 개수는 1이상 1,000 이하의 자연수입니다.

[문제 풀이]

제가 생각한 풀이법은 무식하게 다음과 같이 풀었습니다....

(사실 풀면서 이거 효율성 문제 걸릴거같은데 라고 생각했지만 딱히 다른 방법이 생각안나서 ㅋㅋ)

1. 배열을 정렬한다.

2. 배열의 첫번째 위치(가로등 첫번째 위치)가 0인지 확인한다.

3. 배열의 끝의 위치(가로등 마지막 위치)가 L(길이 값)인지 확인한다.

4. 2) or 3)의 경우가 false라면 둘 중에 큰 값 max를 구한다.

5. 정렬된 배열을 i+1 ,i를 비교해서 가장 큰 차 max_arr를 구한다.

6. max 값과 max_arr를 비교한다.

7. max가 클 경우 answer = max

8. max_arr가 클 경우 짝수일 경우 answer = max/2  홀수일 경우 answer = max/2+1

그럼 코딩해봅시다.

public class mock_test02 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int[] v = {2,9,3,6};
        int answer;
        int l = 11;
        
        //배열 정렬하기
        Arrays.sort(v);  
        int max = 0;
        int max_arr=0;
        
        //가로등 첫번째 위치와 끝 위치가 0,L인지 확인하기
        if(v[0]-0 < l-v[v.length-1]) {
            max = l-v[v.length-1];
            answer = max;
            System.out.println("l과의 거리 "+max);
        }
        else {
            max = v[0]-0;
            answer = max;
            System.out.println("0과의 거리 "+max);
        }
        
        //배열 내 최댓값 구하기
        for(int i=0; i<v.length-1; i++){
            if(max_arr<v[i+1]-v[i]){
                max_arr = v[i+1]-v[i];
            }
        }
        //홀수 짝수 구분하기 ->이유 : d는 정수이기 때문에 max_arr이 1.5이면 최솟값은 2이기 때문
        if(max_arr%2==0) {
            max_arr = max_arr/2;
        }
        else {
            max_arr = (max_arr/2)+1;
        }
        
 
        //마지막 max값과 max_arr값 구해서 큰것이 최솟값이 된다.
        if(max<max_arr) {
            answer = max_arr;
        }
        else
            answer = max;
 
        System.out.print(answer);
    }
 
}

음.. 정확성 테스트는 통과 했지만 효율성 검사에서 실패했네요 ㅠㅠ

Arrays.sort()만 써도 효율성에서 런타임아웃되던데 

다른 라이브러리를 사용하는 방법이 있거나 다른 간단한 솔루션이 있을것 같습니다.

생각나거나 나중에 문제풀다 생각나면 해결해보기로 ㅎㅎ