[백준/JAVA] 1806번: 부분합

🔺 문제

1806번: 부분합

 

 

 

🔺 코드

- 틀림

import java.util.*;
import java.io.*;
 
public class Main {
    public static int N, S;
    public static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 투 포인터
        int left = 0;
        int right = 1;
        
        int answer = 0;
        int min = Integer.MAX_VALUE;
        while(left < right) {
            if(sum(left, right) >= S) {
                min = Math.min(min, right - left + 1);
                left++;
            } else {
                right++;
            }
        }
        
        System.out.println(min);
    }
    
    public static int sum(int l, int r) {
        int total = 0;
        
        for(int i = l ; i <= r ; i++) {
            total += arr[i];
        }
        return total;
    }
}

sum() 메소드가 배열 인덱스를 벗어나는 상황에서 호출된다며

런타임 에러가 떴당... (right 때문인듯)

 

 

- 정답

import java.util.*;
import java.io.*;
 
public class Main {
    public static int N, S;
    public static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int left = 0;
        int right = 0;
        
        int sum = 0;
        int answer = Integer.MAX_VALUE;
        
        while(left <= right) {
            if(sum >= S) {
                answer = Math.min(answer, right - left);
                sum -= arr[left++];
            }
            else if(right == N) {
                break;
            }
            else {
                sum += arr[right++];
            }
        }
        
        System.out.println(answer == Integer.MAX_VALUE ? 0 : answer);
    }
}

✅ 해결 아이디어
✔ 투 포인터
- 시작과 종료 포인터를 모두 0에서부터 시작.
- 시작 위치부터 종료 위치까지의 합이 S보다 크거나 같다면, 현재 칸 값 뺌 & 시작 포인터 위치를 오른쪽으로 한 칸 이동
- 시작 위치부터 종료 위치까지의 합이 S보다 작다면,            현재 칸 값 더함 & 종료 포인터 위치를 오른쪽으로 한 칸 이동

 

💥 유의사항

• right 포인터는 항상 N보다 작거나 같아야 함.

 

---

🔺 다른 풀이들

- 과정 설명 굿..

[백준]1806: 부분합 - JAVA

 

 

- while문 안의 조건식을 아예 right <= N 으로 잡으셨다. 나도 이렇게 했어야 더 좋았을 것 같다.

[백준 1806] - 부분합(JAVA)

 

 

- 왜 right - left + 1이 아니라 right- left하는거지? 했는데 여기에 대한 해답을 얻을 수 있었다!!!

[알고리즘] 백준 1806 부분합 -투포인터- 자바 코틀린

 

 

- right - left + 1 하고 싶으면 이렇게.. (위 아래 순서만 바꾸면 된다.)

[백준/자바] 1806 부분합

---

💬 느낀 점

조건을 놓치지 말고 잘 풀자!

 

 

1회독	2회독	3회독	4회독	5회독
V