[A&I Code Camp] Day31

✍   Kotlin을 PS 문제 풀기

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

투 포인터

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

3273번

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

이 문제는 수열 n개 에서 자연수 x가 주어졌을 때,
$a_i + a_j$ = x (1 ≤ i < j ≤ n)을 만족하는 $(a_i, a_j)$ 쌍의 수를 구하는 문제입니다.

Solve

1. 이 문제는 수열 하나를 받고 정렬을 해줘야 투 포인터를 사용할 수 있습니다.
2. 방향을 left와 right를 나눠 두개를 더해 sum이
   x가 맞았을 때 ans에 +1을 합니다.
3. 만약 sum이 x보다 크다면 left에 1을 더해줘서 범위를 늘려줍니다.
4. 만약 sum이 x보다 작다면 right에 1을 빼줘서 범위를 줄여줍니다.
5. left가 right보다 커지면 수열의 모든 경우를 체크한다는 것을 의미하므로
   반복을 종료시키고 정답 ans를 출력합니다.

import java.io.StreamTokenizer

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

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

    val x = nextInt()
    var left = 0; var right = arr.size - 1
    var ans = 0

    while (left < right){
        val sum = arr[left] + arr[right]
        if(sum == x) { ans += 1 }
        if(sum < x) { left += 1 }
        else{ right -= 1 }
    }
    println(ans)
}

📌 결론

투 포인터를 사용하면 이중 for문으로 모두 확인해야 하는 문제를 O(N) 의 순회만으로
문제를 풀 수 있으니 잘 활용합시다.