[알고리즘] 프로그래머스 연속된 부분 수열의 합 :: 투포인터 with JAVA

처음엔 그냥 생각나는대로 이중포문써서 다 더해보고 제일 작은거 찾기 했더니 역시나 시간초과,,ㅎㅎ

오늘 만난 친구가 코테를 다 풀었는데도 싸피를 떨어졌다고 하는거보니

문제를 맞혀도 시간이 짧게, 공간 낭비가 적은 코드를 작성하는게 중요한 것 같다. 

 

해결법은 투 포인터!!!!

 

이중 for 문은 어떻게 해서든지 복잡도가 최소 N^2이다.

하지만 투 포인터를 쓰면 복잡도가 O(N)으로 시간 효율이 아주 크게 작동한다. 

 

투포인터를 이용해서 작성해보았다. 

자꾸 out of index 오류가 나서 생각해보니 

end pointer가 배열의 마지막 인덱스에 있을 때 1을 더하고 나서 배열을 접근해서 그런거였다. 

그래서 마지막 인덱스일때는 스킵하도록 코드 두 줄 추가...! (효율적인 방법인지는 모르겠다,,,)

 

class Solution {
    public int[] solution(int[] sequence, int k) {
        
        int[] answer = {0,0};
        
        //투포인터//
        int s_pointer = 0; 
        int e_pointer = 0;
        
        
        int sum = sequence[0]; 
        
        while(e_pointer<sequence.length){
            if(sum<k){
                if(e_pointer==sequence.length-1) break; //out of index 방지
                sum+=sequence[++e_pointer];
            }
            else if(sum>k){
                sum-=sequence[s_pointer++];
            }
            else if(sum==k){
                if((answer[0]==0 && answer[1]==0) || answer[1]-answer[0]>e_pointer-s_pointer){ 	//첫 답일 때 || 길이가 이전 답보다 짧을 때 ==> 답 갈아치우기 
                    answer[0] = s_pointer;
                    answer[1] = e_pointer;
                }else if(answer[1]-answer[0] == e_pointer-s_pointer){ //길이는 같은데 인덱스가 더 이전일때 ==> 답 갈아치우기 
                    if(answer[0]>s_pointer){
                        answer[0] = s_pointer;
                        answer[1] = e_pointer;
                    }
                }
                
                if(e_pointer==sequence.length-1) break; //out of index 방지
                sum+=sequence[++e_pointer];
            }
            
        }
         
        
        
      
        return answer;
    }
}

 

 

이제 다 된 줄 알았는데 33케이스에서만 실패했다. 

 

 

이것이 반례,,,,, 

내 코드는 answer가 {0,0}이면 무작정 답이 되는 인덱스를 넣게 해놨는데 

만약 답이 [0, 0] 이라면 절대 [0,0]이 asnwer가 될 수 없는 상황..!

 

 

 

 

 

그래서 고친 코드 

class Solution {
    public int[] solution(int[] sequence, int k) {
        
        int[] answer = {0,sequence.length};
        
        //투포인터//
        int s_pointer = 0; //start pointer
        int e_pointer = 0; //end pointer
        
        
        int sum = sequence[0]; 
        
        while(e_pointer<sequence.length){
            if(sum<k){ 
                if(e_pointer==sequence.length-1) break; //out of index 방지
                sum+=sequence[++e_pointer];
            }
            else if(sum>k){
                sum-=sequence[s_pointer++];
            }
            else if(sum==k){
                if(answer[1]-answer[0]>e_pointer-s_pointer){
                    answer[0] = s_pointer;
                    answer[1] = e_pointer;
                }else if(answer[1]-answer[0] == e_pointer-s_pointer){
                    if(answer[0]>s_pointer){
                        answer[0] = s_pointer;
                        answer[1] = e_pointer;
                    }
                }
                
                if(e_pointer==sequence.length-1) break; //out of index 방지
                sum+=sequence[++e_pointer];
            }
            
        }
      
        return answer;
    }
}

 

 

히히 해결! 😊😊