[A&I Code Camp] Day32

✍   Kotlin을 PS 문제 풀기

소속중인 A&I 동아리에서 코딩역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 kotlin을 기반으로 작성합니다.

투 포인터

이번 주 주제는 투 포인터 알고리즘이며
백준에 하루 한 문제를 풀어가며 작성할 것입니다.
투 포인터
해당 내용은 위 포스트에 작성하였습니다.

1940번

https://www.acmicpc.net/problem/1940

이 문제는 n의 크기에 배열을 하나 받고 그 배열 안 두 가지를 조합하여 m을 몇 개 만들 수 있는지에 대한 문제입니다.

Solve

1. 먼저 배열의 크기 n, 조합해서 만들 m 의 수를 받아줍니다.
2. 그 뒤 n 크기의 배열을 받아주고 정렬해줍니다.
3. 투 포인터를 사용하기 위해 left, right를 각각 처음과 끝으로 지정해 주고 답을 받을 ans를 만들어 주었습니다.
4. while문으로 left의 범위가 right를 넘어갈 때 까지 sum으로 m이 같다면 두 개의 조합이 m을 만들 수 있다는 것이니 ans에 1을 더해주는 식으로 풀어줍니다.

• sum 값이 m 보다 크다면 right의 인덱스 범위를 1 줄여줍니다.
• sum 값이 m 보다 작다면 left의 인덱스 범위를 1 올려줍니다.

import java.io.StreamTokenizer

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())){
    fun nextInt() : Int {
        nextToken()
        return nval.toInt()
    }

    val n = nextInt(); val m = nextInt()
    val arr = IntArray(n){
        nextInt()
    }
    arr.sort()

    var left = 0; var right = n - 1
    var ans = 0
    while(left < right){
        val sum = arr[left] + arr[right]
        if(sum == m){ ans += 1 }
        if (sum < m) { left += 1 }
        else { right -= 1 }
    }
    println(ans)
}

📌 결론

투 포인터를 사용하면 2중 순회를 하지 않고 두 수를 조합하여 값을 구해줄 수 있습니다.