• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

[3-4]연속 부분수열 오답 질문드립니다..

23.01.20 10:35 작성 23.01.20 10:36 수정 조회수 211

0

[3-4] 연속 부분수열 이제 공부를 시작한지 얼마안된 코린이입니다.. 어디가 잘못되었는지 모르겠어요.. 케이스 3,5 에서 리턴값 1차이로 틀리네요..

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int lt = 0, rt = 0, sum = 0, answer = 0;
        int count = sc.nextInt();
        int target = sc.nextInt();
        int[] arr = new int[count];

        for (int i = 0;  i < count; i++) {
            arr[i] = sc.nextInt();
        }

        while (rt < count) {
            if (sum == target) {
                answer++;
                sum -= arr[lt++];
            } else if (sum < target) {
                sum += arr[rt++];
            } else {
                sum -= arr[lt++];
            }
        }

        while(lt < count) {
            sum -= arr[lt++];
            if(sum == target) {
                answer++;
            }
            if(sum < target) break;
        }
        System.out.println(answer);
    }
}

답변 1

답변을 작성해보세요.

0

안녕하세요^^

위에 코드는 다음과 같은 입력이라면

5 3

1 1 1 1 1

수열의 끝부분 3개의 합이 3이 되는 경우를 카운트하지 못합니다.

첫 번째 while(rt < count) 문이 끝나면

if(sum == target) answer++;

해주면 해결됩니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int lt = 0, rt = 0, sum = 0, answer = 0;
        int count = sc.nextInt();
        int target = sc.nextInt();
        int[] arr = new int[count];

        for (int i = 0;  i < count; i++) {
            arr[i] = sc.nextInt();
        }

        while (rt < count) {
            if (sum == target) {
                answer++;
                sum -= arr[lt++];
            } else if (sum < target) {
                sum += arr[rt++];
            } else {
				sum -= arr[lt++];
            }
        }
		if(sum == target) answer++;

       while(lt < count) {
            sum -= arr[lt++];
            if(sum == target) {
                answer++;
            }
            if(sum < target) break;
        }
        System.out.println(answer);
    }
}