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

www.acmicpc.net/problem/1806

1806번: 부분합

 

 

 

백준 알고리즘 분류에서 투포인터 유형의 두 번째 문제인 부분합을 풀어봤습니다. ㅎㅎ 

투포인터 유형인 만큼 완탐으로 풀면 시간초과가 나게됩니다.

 

N개의 수열이 있는데 연속된 수들의 합(부분합) S 이상인 것 중 가장 짧은 길이를 구하는 문제였습니다.

투포인터는 다음과 같이 나눴습니다. 부분합이 S보다 적은 경우는 right를 오른쪽으로 이동 더 큰 경우는 left를 왼쪽으로 이동시킴으로써 더 적은 길이가 될 수 있는 기회를 갖게됩니다.

(예시)

오랜만에 투포인터 문제를 풀었는데 복습할 수 있는 시간이었습니다. 

주석으로 풀이를 작성해놨습니다.

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

class Main {
    private static int N; // 10 ≤ N < 100,000
    private static int S;
    private static int left = 0;
    private static int right = 0;
    private static int answer = 100001;
    private static int sum = 0;
    private static int[] nums;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();
        nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        while (true) {
            if (sum >= S) { //조건 만족
                sum -= nums[left];
                answer = Math.min(answer, (right - left)); // 부분합 최소 길이 갱신
                left++; // 왼쪽 포인터 오른쪽으로 이동
            } else if (right == N) { //끝 도달
                break;
            } else { // right포인터 오른쪽으로 이동
                sum += nums[right++];
            }
        }
        if (answer == 100001) {
            System.out.println(0);
        } else {
            System.out.println(answer);
        }
    }
}

 

 

[Kotlin]

import java.util.*

private var N // 10 ≤ N < 100,000
        = 0
private var S = 0
private var left = 0
private var right = 0
private var answer = 100001
private var sum = 0
private lateinit var nums: IntArray

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    S = sc.nextInt()
    nums = IntArray(N)
    for (i in 0 until N) {
        nums[i] = sc.nextInt()
    }
    while (true) {
        if (sum >= S) { //조건 만족
            sum -= nums[left]
            answer = Math.min(answer, right - left) // 부분합 최소 길이 갱신
            left++ // 왼쪽 포인터 오른쪽으로 이동
        } else if (right == N) { //끝 도달
            break
        } else { // right포인터 오른쪽으로 이동
            sum += nums[right++]
        }
    }
    if (answer == 100001) {
        println(0)
    } else {
        println(answer)
    }
}

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다 !!!