250x250
Notice
12-08 02:11
관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 백준 2003 수들의 합2 -투포인터- 자바 코틀린 본문

알고리즘/투포인터

[알고리즘] 백준 2003 수들의 합2 -투포인터- 자바 코틀린

막무가내막내 2020. 10. 3. 16:37
728x90

www.acmicpc.net/problem/2003

 

2003번: 수들의 합 2

첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

www.acmicpc.net

 

 

 

완전탐색으로 하는 경우 시간초과가 날때가 있었습니다. 그 경우 투포인터 방법을 사용하면 시간초과를 해결할 확률이 높아집니다.

투 포인터의 대표 샘플 문제로 불리는 수들의 합2를 풀어보았습니다.

 

 

 

[Java]

import java.util.Scanner;

public class Main {
    private static int[] num;
    private static int left = 0;
    private static int right = 0;
    private static int result = 0;
    private static int sum = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        num = new int[n];
        for (int i = 0; i < num.length; i++) {
            num[i] = sc.nextInt();
        }
        while (true) {
            if (sum >= m) {
                sum -= num[left++];
            }else if(right == n){
                break;
            } else {
                sum += num[right++];
            }
            if (sum == m) {
                result++;
            }
        }
        System.out.println(result);


    }
}

 

 

[Kotlin]

import java.util.*

private lateinit var num: IntArray
private var left = 0
private var right = 0
private var result = 0
private var sum = 0


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val m = sc.nextInt()
    num = IntArray(n)
    for (i in num.indices) {
        num[i] = sc.nextInt()
    }
    while (true) {
        if (sum >= m) {
            sum -= num[left++]
        } else if (right == n) {
            break
        } else {
            sum += num[right++]
        }
        if (sum == m) {
            result++
        }
    }
    println(result)
}

 

 

 

 

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

728x90
0 Comments
댓글쓰기 폼