글 읽기 - 자바) 투포인터 조건문의 순서관련 질문

qlsdud0604 2년 전 0

투포인터로 알고리즘을 짜서 성공을 했습니다. 근데 같은 방식의 알고리즘인데 조건문의 순서를 바꾸니 인덱스 범위 오류가 나는데 대체 왜 그런건가요?

47~55번 라인의 코드를 다음과 같이 바꾸었는데 오류가 납니다.

if (sum < S) {
sum += arr[right];
right++;
} else if (S <= sum) {
sum -= arr[left];
result = Math.min(result, right - left);
left++;
} else if (right == N)
break;

import java.io.*;
import java.util.*;

public class BOJ_1806 {
	static int N;
	static int S;
	static int[] arr;

	static int result;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());

		result = N + 1;

		arr = new int[N];

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(st.nextToken());

		twoPointers();

		if (result == N + 1)
			bw.write(0 + "\n");
		else
			bw.write(result + "\n");

		bw.close();
	}

	static void twoPointers() {
		int left = 0;
		int right = 0;

		int sum = 0;

		while (true) {
			if (S <= sum) {
				sum -= arr[left];
				result = Math.min(result, right - left);
				left++;
			} else if (right == N)
				break;
			else {
				sum += arr[right];
				right++;
			}
		}
	}
}

dldyddlwl 2년 전 1

if (sum < S) {        // S가 sum보다 큰 경우
     sum += arr[right];
     right++;
} else if (S <= sum) {    // S가 sum보다 작거나 같은 경우
     sum -= arr[left];    // 반드시 두 조건 중 하나에 걸림
     result = Math.min(result, right - left);
     left++;                // 그래서, 아래 조건까지 올 수가 없지 않을까요?
} else if (right == N)           
     break;

sb123s 2년 전 1

만약 if(sum < S) 조건문에 걸려서 right++을 수행했으나

right가 범위를 벗어나게 된다면 잘못된 index를 접근하게 됩니다.

1 2 3 <- 만 주어진 문제에서 합이 10이상을 찾는다면

right가 3을 가리키고 있음에도 합이 최대 6이므로 right가 증가하게 되고 잘못된 index를 접근하게 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

자바) 투포인터 조건문의 순서관련 질문

qlsdud0604 2년 전 0

dldyddlwl 2년 전 1

sb123s 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말