[프로그래머스] Lv.2 연속된 부분 수열의 합(Java)

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

 

코딩테스트는 Lv2부터 시작해서 Lv5까지 올려보고 싶다는 생각에 하게 되었습니다!

사실,,,

취업 전 코딩테스트 보는 회사가 많아서 시작한감이 있는데 좀 많이 늦어버렸네요..

취업 문이 닫히기 전에 취업하고 싶어요,,,

 

일단 적고 싶어서ㅎㅎ 이렇게라도 적으면 '내 생각을 티스토리에 올렸다'는 생각만으로도 더 열심히 할거 같아서요!

 

---

문제 설명

비 내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

 

제한 사항

• 5 ≤ sequence의 길이 ≤ 1,000,000
  • 1 ≤ sequence의 원소 ≤ 1,000
  • sequence는 비내림차순으로 정렬되어 있습니다.5 ≤ k ≤ 1,000,000,000
• k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.
  • k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

 

---

예시

첫번째 입력값으로 [1,2,3,4,5]라는 수열이 있습니다.

k가 7이면,

위에 있는 수열의 값 중에 연속된 부분 수열의 합이 7인 것을 찾으면 됩니다.

해당 수열에서 7이 될 수 있는 부분 수열은

[3,4] 뿐입니다!

그러므로 수열의 시작 인덱스인 2와 마지막 인덱스인 3을 담은

배열이 [2,3]이 출력되는 것입니다.

* 만약에 수열에 7이 들어가 있으면, 즉 [1,2,3,4,5,6,7]이라는 수열 중에 7인 값, 찾으려는 값이 있으면

시작 인덱스도 마지막 인덱스도 6이므로 [6,6]을 반환합니다.

 

 

 

첫번째 시도 - 오답

입력된 수열에서 만들 수 있는 연속 부분 수열을 구하는 반복문을 만듭니다.

예를 들어 이중 반복문을 만들어서 순서로 입력하면

(1), (1,2), (1,2,3), (2,3) ...

위와 같이 만들어질 수 있습니다.

이렇게 수열을 만들어 합이

k의 값보다 크면, 반복문을 종료 break

k의 값보다 작으면, 계속 이어서 하도록 continue해줍니다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int[] answer = new int[2];
        int seqlen = sequence.length;
        answer[0] = seqlen;
        answer[1] = seqlen;

        
        int sum = 0; // 부분 수열의 합
        
        for (int i = 0; i<sequence.length; i++){
            sum = sequence[i];
            if(sum==k){ // 만약 동일한 값이 있으면 종료하고 인덱스 값을 넣어야 함
                answer[0] = i;
                answer[1] = i;
            }
            else{ // 아니면 인덱스 찾아야 함
                for (int j = i+1; j < sequence.length; j++){
                    
                    sum += sequence[j]; // 합을 구하기
                    
                    if (sum>k) break; // 만약 커버리면 for문 종료하고 다음 값 확인
                    else if (sum == k) {// 합이 같으면 종료하고 원래 있던 값과 비교해야함
                        // 길이가 짧은 수열을 찾아야함
                        int alen = answer[0]-answer[1];
                        int forlen = j-i; 
                        
                        if (answer[0]!= sequence.length && alen<forlen){
                        }else{
                            answer[0]=i;
                            answer[1]=j;
                        }
                        
                    }
                }
                
            }
        }
        
        
        return answer;
    }
}

이렇게 작성했는데

중간중간마다 뭔가 빠지고 좋은 알고리즘은 아닌것 같다..

결국 테스트 해보니 테스트 케이스 중 정답이 아니거나 시간초과도 많았습니다.. 

좀더 좋은 알고리즘을 구현해야합니다!

 

---

두번째 시도

위와 비슷한 방법인데 더 간단한 알고리즘 입니다

for문으로 전체 수열을 확인하는 건데

합을 구하는 내용은 동일합니다. 대신 for문이 아니라 단순 합이기 때문에 while문으로 더 빠르게 처리합니다.

제가 했던 내용과 비슷하지만 더 간단하게 처리하는 방식이죠!

코드 리뷰 겸 코드 주석 처리해서 알려드리겠습니다.

import java.util.*;

class Solution {
    public int[] solution(int[] sequence, int k) {
        int len = sequence.length; // 수열의 길이
        int first = 0; // 첫번째 값
        int second = len; // 두번째 값
        int sum = 0; // 합
        
        for (int f = 0, s = 0; f<len; f++){ 
            // 값을 k와 비교하면서 넣어야 함
            while(s<len && sum<k){ // while문을 활용하여 마지막 값까지 확인(sum이 k값보다 작을 때만 반복함)
                sum += sequence[s++]; // sum값에 값을 더함.
            }
            
            if(sum==k){ // 만약에 k와 동일하다면
                int a = s - f - 1; // 두 인덱스값의 차이를 확인해야 함.(상단의 while문에서 s++를 해줬기 때문에 -1을 해줘야한다.)
                if((second - first) > a ){ // 두 인덱스 차이가 정답의 인덱스 차이보다 작으면
                    first = f ; // 첫번째 값
                    second = s-1; // 두번째 값(상단의 while문에서 s++를 해줬기 때문에 -1을 해줘야한다.)
                }
            }
            sum-=sequence[f]; // 연속된 부분 수열이기 때문에 맨 앞에 있는 값을 빼고 반복문의 다음으로 넘어가면 되기 떄문에!            
        }
        
        int[] answer = {first, second};
        
        return answer;
    }
}

 

참고

https://velog.io/@seowj0710/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Level-2-%EC%97%B0%EC%86%8D%EB%90%9C-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4%EC%9D%98-%ED%95%A9-Java

[프로그래머스 Level 2] 연속된 부분 수열의 합 (Java)