[백준] 3273. 두 수의 합 (Kotlin)

문제

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

3273번: 두 수의 합

풀이

0. 문제 해석

주어지는 정수들은 서로 다르므로

HashSet을 이용하는 방법과 정렬 후 투 포인터 알고리즘을 이용하는 방법 두가지로 풀 수 있다.

 

1. 전체 코드 (HashSet)

// [백준] 3273. 두 수의 합 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    val n = readLine().toInt()
    val list = readLine().split(" ").map { i -> i.toInt() }.toHashSet()
    val x= readLine().toInt()
    var count = 0

    for(i in list){
        // 합해서 x를 만들 수 있는 다른 원소가 있으면
        if(list.contains(x - i)){
            count++
        }
    }

    // 쌍이므로 나누기 2
    println(count / 2)
}

HashSet의 contains을 활용하면 빠른속도로 원소의 포함여부를 알 수 있기 때문에

HashSet의 모든 원소를 탐색하면서 그 원소와 합해서 x를 만들 수 있는 원소를 탐색하여 찾을 때마다 카운트한다.

탐색 결과는 쌍이므로 결과값을 2로 나눠주면 된다.

 

2. 전체 코드 (투 포인터)

// [백준] 3273. 두 수의 합 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    val n = readLine().toInt()
    val list = readLine().split(" ").map { i -> i.toInt() }.toMutableList()
    val x= readLine().toInt()
    var count = 0

    var start = 0 // 앞 쪽 포인터
    var end = n - 1 // 뒤 쪽 포인터

    list.sort() // 정렬

    // 더 이상 탐색하지 못할 때 까지
    while(start < end){
        val sum = list[start] + list[end]

        // 쌍을 찾으면 카운트
        if(sum == x){
            count++
        }

        // x보다 작으면 sum 을 늘려야하므로 start++
        if(sum <= x){
            start++
        }

        // x보다 크다면 sum 을 줄여야하므로 end--
        else{
            end--
        }
    }

    println(count)
}

리스트를 오름차순으로 정렬해주고

맨 앞쪽에서 시작하는 포인터 start, 맨 뒤쪽에서 시작하는 포인터 end 를 선언한다.

그리고 오름차순이므로 sum이 x보다 작거나 같으면 start를 키우고, sum이 x보다 크면 end를 키워가면서 쌍을 찾는다.