백준 1940 주몽, 코틀린, 투포인터

문제

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

1940번: 주몽

 

 

풀이

입력이 아래와 같을 경우를 풀어 봅시다

6

9

2 7 4 1 5 3

 

재료 개수 n : 6

갑옷을 만드는데 필요한 수 m : 9

갑옷 재료 번호 배열 arrNum : 2 7 4 1 5 3

 

갑옷 재료 2가지를 조합하여 숫자 9가 충족되는 조합은 몇가지 인지를 출력하면 됩니다.

 

투포인터로 쉽게 풀수 있는데요 이전에 배열 원소 값들을 오름차순 정렬 해줍니다.

 

그림 1

 

그림 1과 같이 배열을 오름차순으로 정렬후에 인덱스 low 0 값과 high 5값에 대한 배열 값을 더해줍니다. 

1+7 값은 m값의 9보다 작으므로 왼쪽의 포인터를 한칸 오른쪽으로 이동하여 줍니다. 

만약 두 값의 합이 조건 값보다 크다면 인덱스 high값을 한칸 왼쪽으로 이동하여 줍니다.

 

그리고 인덱스 1값과 5값인 2+7을 해줘 m값과 비교 해줍니다. m값인 9 값과 같기 때문에 조건에 충족합니다.

충족되면 인덱스 low값과 high을 각각 +1, -1을 하여 원소값을 다시 m과 비교 하여 줍니다. 

 

이같은 방식으로 두 포인터를 이동 시켜 결과값을 출력합니다.

 

위 방식대로 코드를 구현하여 보겠습니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main(args: Array<String>) {
    // 투포인터

    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    // n: 재료의 갯수
    var n = br.readLine().toInt()

    // m: 갑옷을 만드는데 필요한 숫자
    var m = br.readLine().toInt()

	// arrNum : 재료값 배열
    var arrNum = br.readLine().split(" ").map { it.toInt() }.sorted()

    var result_1940 = 0

    var low = 0
    var high = arrNum.size-1
    // 투포인터
    while (low<high) {
        if (arrNum[low] + arrNum[high] > m) high--
        else if (arrNum[low] + arrNum[high] < m) low++
        else {	// 조건값과 같을때
            low++
            high--
            result_1940++
        }
    }

    bw.write(result_1940.toString())
    bw.flush()
    bw.close()

}