백준 1208 부분수열의 합 2 Kotlin (해시,투 포인터, 이분 탐색)

문제 출처 : https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

알고리즘 분류

• 이분 탐색
• 중간에서 만나기

풀이

일반적인 완전 탐색은 O(2^N)으로 시간 초과가 난다.

따라서 어떠한 아이디어가 필요하다.

 

풀이의 핵심은 다음과 같다.

1. 주어진 배열을 반으로 나눈다.

2. 나눠진 배열 중 하나의 배열에서 더해서 나올 수 있는 모든 값들을 hashmap에 나온 횟수를 저장한다. O(2^(N/2))

3. 나머지 배열에서 모든 값들을 더하고O(2^(N/2))  (S-더한 값)들을 위에서 구한 hashmap의 키 값으로 사용하여 횟수를
   카운트한다.
4. 배열의 요소들의 합들을 구하는 과정의 시작에 임의로 0을 넣어줬기 때문에, s가 0이라면 전체 횟수에서 하나를 빼준
    다. 

 

위의 풀이가 가장 간편하고 빠르다.

이외에도, 똑같이 배열을 나누고, 두 개의 sum 배열을 구한 다음 투 포인터 알고리즘으로 푸는 방법이 있는데,

아래 코드 중 두 번째 코드가 투 포인터 풀이다.

무엇으로 풀어도 상관없다. 편한 대로 풀자.

 

문제 알고리즘 분류를 보면 이분 탐색이 있는데,

c++언어의 upper_bound 와 lower_bound를 사용한 방법도 있다.

이분 탐색에 근거한 함수인 upper_bound와 lower_bound를 이용하면, 배열에서 어떠한 값이 나오는 횟수를 쉽고 빠르게

구할 수 있다. 하지만 Kotlin에선 직접 함수를 구현해야 하므로 패쓰~

 

코드1(HashMap)

val sumMap= mutableMapOf<Long,Long>()
var cnt=0L
fun preSum(idx : Int, n : Int, input : LongArray, sum : Long){
    if(idx==n){
        sumMap.put(sum,sumMap.getOrDefault(sum,0)+1)
        return
    }
    preSum(idx+1,n,input,sum+input[idx])
    preSum(idx+1,n,input,sum)
}

fun leftSum(idx : Int, n : Int, input : LongArray, sum : Long, s: Int){
    if(idx==n) {
        cnt += sumMap.getOrDefault(s - sum, 0)
        return
    }

    leftSum(idx+1, n, input, sum+input[idx],s)
    leftSum(idx+1, n, input, sum,s)
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,s) = br.readLine().split(' ').map{it.toInt()}
    val input = br.readLine().split(' ').map{it.toLong()}.toLongArray()

    preSum(n/2,n, input, 0)
    
    leftSum(0,n/2,input,0,s)
    if(s==0)cnt--
    write("$cnt")
    close()
}

코드2(투 포인터 ArrayList, 투 포인터 LongArray)

fun preSum(idx : Int, n : Int, input : LongArray, sum : Long, arr : ArrayList<Long>){
    if(idx==n){
        arr.add(sum)
        return
    }
    preSum(idx+1,n,input,sum+input[idx], arr)
    preSum(idx+1,n,input,sum, arr)
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,s) = br.readLine().split(' ').map{it.toInt()}
    val input = br.readLine().split(' ').map{it.toLong()}.toLongArray()


    val leftSum = ArrayList<Long>()
    val rightSum = ArrayList<Long>()
    //반으로 나눠서 두 수의 합 배열 생성
    preSum(0,n/2, input, 0, leftSum)
    preSum(n/2, n, input, 0, rightSum)

    //두 배열 정렬
    leftSum.sort()
    rightSum.sort()

    //투 포인터
    var answer=0L
    var p1 = 0
    var p2 = rightSum.size-1
    var cnt=1
    while(p1<leftSum.size && p2 >=0){
        if(leftSum[p1] + rightSum[p2]==s.toLong()){
            if(cnt==1){
                var idx=p2
                while(--idx>=0 && rightSum[idx]==rightSum[p2]){
                    cnt++
                }
            }
            answer+=cnt
            p1++
        }
        //s보다 작을 때
        else if(leftSum[p1] + rightSum[p2]<s.toLong()){
            p1++
            cnt=1
        }
        //s보다 클 때
        else{
            p2--
            cnt=1
        }
    }

    if(s==0)answer--
    write("$answer")
    close()
}