[투포인터] 백준 3649번 로봇 프로젝트 - JAVA

 

오늘 이분탐색 구현 방식에 따라 성능에 차이가 있다는 사실을 알았다.

왜 for문으로 투포인터 구현하면 시간 초과가 나고,

while로 구현하면 통과인지

사실 아직도 모르겠다... 아는 고수 있으면 답변 주세요 ㅠㅠ

 

---

1. 출처

---

 

 

3649번: 로봇 프로젝트

 

 

---

2. 설계

---

 

 

1. 자바에서 불가능한 설계

처음에는 레고 조각 길이가 10cm = 10 * 10^7nm를 넘지 않는다고 해서 int[10*10^7+1]만큼 배열 공간을 확보해 갯수를 세주고

구멍의 너비 - 레고 조각의 길이가 있는지 인덱스로 바로 접근해 확인해주려고 했다.

 

근데 자바에서는 int[10*10^7+1]에 범위로 배열을 만들 수 없었다. 나는 int 21억의 범위가 저장소 안에 들어갈 수 있는 숫자이지, 배열의 크기를 결정짓지 않는다는 차이를 인지하게 되었다... 이제서야... ^^

 

 

2. 성공 설계

결국 투포인터를 이용해 구멍의 너비에 맞는 레고 2개를 찾고자 했다.

근데 여러 개의 쌍이 있을 경우 | l1-l2 |가 큰 값을 정답으로 하기 때문에 레고 조각들을 길이로 sort 해주고, 시작점은 0부터 끝점은 N-1부터 진행하며 쌍을 찾아나갔다.

 

1   2   3   8   9   14

위 숫자가 있을 때 17을 찾는다고 하면 (8, 9) (3, 14)를 찾을 수 있다.

큰 수에서 짝을 찾을수록 작은 수가 나올 확률이 높기 때문에 (3, 14)가 나왔을 때 바로 종료하고 결과를 출력해도 되는 것이다.

 

근데 나는 투포인터 설계에서 난항을 겪었다. 왜 똑같은 로직인데 for문으로 구현하면 시간초과가 나고 while로 구현하면 통과가 되는 것일까? 난 세윤이 덕분에 해답을 찾았다.

 

 

좌측이 정답코드이고, 우측이 시간초과 코드이다.

나는 같은 로직이어서 시간 복잡도도 같겠거니 했는데, 아니었다. 최악의 상황일 때 시간 복잡도는 확연히 차이가 났다.

두 코드 모두 레고 쌍이 존재하지 않을 때 정답 코드(while)는 N개의 데이터만 확인하고 끝이 난다. 즉, O(N)이다.

하지만 시간 초과 코드(for)는 N*N개의 데이터를 쌍이 맞을 때까지 반복적으로 확인한다. 즉, O(N^2)이다.

 

시간복잡도 계산에 아직 미숙하다니... 다시 공부했다.

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

 

 

---

3. 전체 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String testcase = "";
        while((testcase=br.readLine())!=null){
            int cmTnm = Integer.parseInt(testcase)* 10000000;
            int N = Integer.parseInt(br.readLine());

            int[] lego = new int[N];
            for(int i=0;i<N;i++){
                lego[i] = Integer.parseInt(br.readLine());
            }
    
            //입력 끝
    
            //1. sort
            Arrays.sort(lego);
    
            //2. l1 <= l2를 찾아라
            boolean flag = false;
            int S = 0;
            int E = N-1;
            
            while(S<E){
                int sum = lego[S]+lego[E];
                if(sum==cmTnm){
                    flag=true;
                    break;
                }
                else if(sum<cmTnm) S++;
                else E--;
                
            }
    
            if(flag){
                if(flag) System.out.println("yes "+lego[S]+" "+lego[E]);
            }else{
                System.out.println("danger");
            }
        }//while
    }
}