백준 1806 부분합 (JAVA 자바 풀이)

백준 6236 용돈 관리 (JAVA 자바 풀이)

 

 

 

---

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

 

 

 

---

 

 

💡 풀이 과정

 

투 포인터를 사용한 예제로 대표적인 문제이다. 

 

먼저 예제 입력을 살펴보자.

 

5 1 3 5 10 7 4 9 2 8 중에 연속되는 값들 중에 15보다 큰 수열 중 가장 작은 값을 구해야 한다. 

0번째 부터 살펴보면 5 + 1+ 3+ 5 = 14이므로 그 다음 값인 10이 포함되면 5 + 1 + 3 + 5 + 10 = 24가 된다. 

즉, 4번째 값까지 포함할 때 조건을 만족한다.

이때의 길이는 4 - 0  + 1 => 4이다. 즉 인덱스에 +1을 해준 값에서 가장 첫번째 인덱스를 빼준 값이다. 

 

포인터로 생각해보면 마지막 값을 가리킨 뒤 포인터를 뒤로 이동시키는 경우이므로 마지막 포인터 - 처음 포인터라고 볼 수 있을 것이다. 

따라서 다음과 같은 식이 도출된다. 

 

가장 짧은 길이 = end pointer - start pointer 

 

계속해서 로직을 살펴보자. 

 

4번째 인덱스인 10이상의 범위를 볼 필요가 있을까? 없다. 그 이상 더하는 값들은 모두 15이상 보다 클 것이기 때문이다. 

 

그렇다면 그 전 항목들은 어떨까? 현재 더한 값이 24이므로, 0 ~ 4 사이의 5개의 값들 중에 연속하는 어떤 수들은 15보다 크면서 24보다 작을 수 있다. 그 항목들은 어떻게 찾을까? 

 

처음 시작하는 지점, 즉 가장 왼쪽 값부터 하나씩 빼면 된다. 

 

예를 들어 첫 번째 값인 5를 빼고 계산해보자. 1 + 3 + 5 + 10 = 19이므로 만족한다. 이렇게 하나씩 옮겨보다보면 3, 4 인덱스인 5 + 10 만으로도 15를 만족하는 것을 볼 수 있다. 

 

이렇게 만족하는 시점마다 답을 갱신해주면 모든 수를 탐색한 뒤에 답을 얻을 것이므로 답을 갱신해주는 로직이 필요함을 알 수 있다. 

 

이제 10부터 다시 카운트를 똑같이 위에서의 과정을 반복한다. 

예를 들어 10 + 7 = 17이다. 

 

투포인터로 위의 로직을 코드로 짜보자. 

 

int start = 0; // 초기 포인터는 둘 다 0으로 시작하고 같은 방향으로 간다.
int end = 0;
int sum = 0;
int minLength = Integer.MAX_VALUE; // 최소값을 구해야 하므로 가장 큰 값으로 초기화 한다.

 

먼저 시작과 끝점을 0으로 잡는다. 

 

이후 같은 방향으로 움직이는 반복문과 조건문을 구현하면 된다. 

 

break이 걸리기 전까지 도는 반복문에서 아래와 같은 절차에 따라 코드를 구현한다. 

// 1. end 기준으로 summation을 한다.
// 2. 만약 해당 값이 requiredSummation 보다 같거나 크다면
//  2-1. 만족시킨 것이므로 길이를 구한다.
//     2-2. 구한 길이가 최소값인지를 판단하고 갱신한다.
//  2-3. 값을 구했으므로 다음 연산을 수행한다 -> 작은 값을 올려서 여전히 requiredSummation을 만족하는지 판단해야 한다.
// 3. 해당 값이 작다면 숫자가 더 필요하므로 end를 올린다.
// 4. 종료 조건은 end가 범위를 넘어가는 시점이다.

while (true) {
   if (sum >= requiredSummation) {
      minLength = Math.min(minLength, end - start);
      sum -= numbers[start++];
   } else if (end == numberCounts) {
      break;
   } else {
      sum += numbers[end++];
   }
}

 

 

while문으로 풀지 않고 for문으로 왼쪽 인덱스를 정해놓고 돌려보는 방식도 생각해보자. 

 

int rightIndex = 0;
int currentSum = arr[0];

for (int i =0; i< N; i++){
  while (currentSum < S && rightIndex < N - 1){
    currentSum += arr[++rightIndex];
  } 
  
  if (currentSume >= S){
  	ansLength = Math.min(ansLength, rightIndex - i + 1);
    currentSum -= arr[i];
  }
  

}

 

 

currentSum을 첫값이라고 초기화하고 i 가 left index일때, 

l~r의 합이 S 보다 작다면 포함하는 숫자를 늘려나간다. 

 

즉, 15인 S 값보다 같거나 커질 때까지 이동한다. 

만약 S보다 같거나 크다면 답을 최소값으로 갱신한다. 이후 start index를 올려서 다음 탐색을 진행하기 시작한다. 이때 다음 구간으로 이동하기 시작하면서 기존의 가장 첫번째 값을 제외한다. 

 

while문과 다르게 for문에서는 초기 범위가 N으로 주어지므로 별도의 종료 조건은 필요 없다. 

 

💡 코드 구현

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

   private static StringTokenizer receiveInput(BufferedReader bufferedReader) throws IOException {
      return new StringTokenizer(bufferedReader.readLine());
   }

   public static void main(String[] args) throws IOException {

      BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
      // BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));

      StringTokenizer stringTokenizer = receiveInput(bufferedReader);
      int numberCounts = parseInt(stringTokenizer.nextToken());
      int requiredSummation = parseInt(stringTokenizer.nextToken());

      int[] numbers = new int[numberCounts];
      stringTokenizer = receiveInput(bufferedReader);
      for (int i = 0; i < numberCounts; i++) {
         numbers[i] = parseInt(stringTokenizer.nextToken());
      }

      int start = 0; // 초기 포인터는 둘 다 0으로 시작하고 같은 방향으로 간다.
      int end = 0;
      int sum = 0;
      int minLength = Integer.MAX_VALUE; // 최소값을 구해야 하므로 가장 큰 값으로 초기화 한다.

      // 1. end 기준으로 summation을 한다.
      // 2. 만약 해당 값이 requiredSummation 보다 같거나 크다면
      //  2-1. 만족시킨 것이므로 길이를 구한다.
      //     2-2. 구한 길이가 최소값인지를 판단하고 갱신한다.
      //  2-3. 값을 구했으므로 다음 연산을 수행한다 -> 작은 값을 올려서 여전히 requiredSummation을 만족하는지 판단해야 한다.
      // 3. 해당 값이 작다면 숫자가 더 필요하므로 end를 올린다.
      // 4. 종료 조건은 end가 범위를 넘어가는 시점이다.

      while (true) {
         if (sum >= requiredSummation) {
            minLength = Math.min(minLength, end - start);
            sum -= numbers[start++];
         } else if (end == numberCounts) {
            break;
         } else {
            sum += numbers[end++];
         }
      }
      System.out.println(minLength == Integer.MAX_VALUE ? 0 : minLength);
   }

}

 

 

 

 

---

 

참고자료: 패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java