인프런 커뮤니티 질문&답변

함승찬

작성한 질문수

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

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

해결된 질문

작성

293

수정됨

[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);
    }
}

코테 준비 같이 해요! java

답변 1

김태원

지식공유자

안녕하세요^^

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

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);
    }
}

함승찬

작성한 질문수

전체 Q&A

질문하기