[코딩연습_JAVA] 연속 부분수열

(김태원님의 알고리즘 문제풀이 강의(JAVA)를 들으며 공부중이다.)

 

공부하다가 '이건 꼭 새겨둬야지' 하는 사항이 있어 오랜만에 기록을 남긴다. (오답노트)

이미 잘하는 사람들에게는 시시한 사항이겠지만, 나는 한참 배우는 중이니까..!

 

[문제 설명]

'N개의 수로 이루어진 수열에서, 합했을 때 특정 값이 나오는 부분 수열의 개수를 출력'하는 문제이다.

 

두 개의 포인터로 슬라이딩 윈도우를 구현하면 쉽게 풀 수 있는 문제다.  

 

문제 풀이 아이디어 자체는 좋았는데, 간단한 부분에서 막혔다.

자꾸 부분 수열의 카운팅 개수가 정답보다 1적게 나오는 것. 무엇이 문제 였을까? 아래 잘못된 코드를 보자.

#첫 번째 코드

   public int solution(int n, int m, int[] arr){
        int cnt=0;
        int i=0,k=0,sum=0; //i는 끝, k는 시작을 가리키는 인덱스
       while(i<n){
           if(sum==m) cnt++;
           sum+=arr[i++]; 
           while(sum>m){
               sum-=arr[k++];// 윈도우 크기 오른쪽 방향으로 1씩 줄이기
           }
       }

        return cnt;
   }

(무엇이 문제인지 단번에 알아차렸다면, 축하합니다! 그동안 열심히 피땀눈물을 흘리셨군요! 앞으로도 화이팅👍)

 

문제는 if(sum==m) cnt++; 이 조건문의 위치에 있다.

아래는 위 조건문의 위치를 바로잡은 코드이다. 위의 코드와 어떤 차이가 있는지 알겠는가?

나는 못 찾아서 결국 스터디원에게 SOS를 요청했는데, 4분만에 해결됐다. 웜메...

#두 번째 코드

   public int solution(int n, int m, int[] arr){
        int cnt=0;
        int i=0,k=0,sum=0; //i는 끝, k는 시작을 가리키는 인덱스
       while(i<n){
           sum+=arr[i++];
           while(sum>m){
               sum-=arr[k++];// 윈도우 크기 오른쪽 방향으로 1씩 줄이기
           }
           if(sum==m) cnt++; //조건문의 올바른 위치
       }

        return cnt;
   }

 

두 코드 모두 i<n-1 일 때는 문제가 없다. 문제는 i==n-1이 되었을 때 생긴다. 

잘못된 첫번째 코드를 다시 보자.

↓↓↓

   public int solution(int n, int m, int[] arr){
        int cnt=0;
        int i=0,k=0,sum=0; //i는 끝, k는 시작을 가리키는 인덱스
       while(i<n){
           if(sum==m) cnt++; //문제의 코드
           sum+=arr[i++]; //6번째 줄
           while(sum>m){
               sum-=arr[k++];// 윈도우 크기 오른쪽 방향으로 1씩 줄이기
           }
       }

        return cnt;
   }

첫 번째 코드에서는 i==n-2까지는 문제없이 카운팅된다. 하지만 i==n-1(i가 마지막 인덱스를 가리킬 때)이 되면 6번째 줄에서 마지막 값이 변수 sum에는 더해지지만 동시에 i의 값이 n이 되면서 반복문의 조건(i<n)에 맞지 않게되어 반복문을 탈출하게 된다.

 

결과적으로 마지막 부분수열의 합은 5번째 줄에 있는  if(sum==m) cnt++; 이 조건문을 거치지 못하게 되면서 정답으로 카운팅되지 못한 것이다..

 

그래서 윈도우의 크기가 줄어들거나 늘어날 때 마다 조건에 부합하는지 바로바로 검사할 수 있도록 코드를 수정 해주면 간단하게 해결할 수 있다! :> (두 번째 코드 참조)

 

 

 

 

 

 

 

+)여담

이 문제를 풀기 바로 전의 문제에서도 조건문의 위치가 잘못돼서 고생하는 바람에 이번에는 신경썼는데도 또 같은 문제가 발생했다. 아직 실력&경험 부족인걸로🥹..

그래도 이번에 스스로 생각해낸 솔루션이 강사님과 같아서 나름 뿌듯한 점도 있었다!