개발해요

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

유형

누적합, Map 자료구조

풀이 과정

1. 누적합을 저장할 배열(accSum[])과 각 누적합의 개수를 카운트 할 Map(accSumMap)을 선언한다.
2. 누적합을 모두 구한다.
3. 누적합을 차례대로 확인한다. (accSum[1..n])
   1. 누적합(accSum[i])이 k(target)와 일치하면 정답 카운트를 증가시킨다
   2. accSum[i]에서 뺀 값이 k가 되는 누적합의 개수 즉, 앞에서 기록했던 누적합 카운트에서 accSumMap[accSum[i] - k]의 개수만큼 정답 카운트를 증가시킨다. (answer += accSumMap[accSum[i] - k])
   3. accSumMap에 accSum[i]의 개수를 반영한다. (accSumMap[accSum[i]] += 1)

코드1

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, target) = readLine().split(" ").map(String::toInt)
    val nums = IntArray(n + 1)
    val accSum = IntArray(n + 1)        // accSum[i]: nums[1] + ... + nums[i]
    val accSumMap = HashMap<Int, Int>() // 누적합의 개수 저장
    var answer = 0L

    // 누적합 계산
    val st = StringTokenizer(readLine())
    for (i in 1..n) {
        nums[i] = st.nextToken().toInt()
        accSum[i] = accSum[i - 1] + nums[i]
    }

    for (i in 1..n) {
        if (accSum[i] == target) answer++ // 0~i번째 까지의 누적합이 target과 같은지 검사

        // 앞서 저장한 누적합 중 accSum[i]에서 빼면 target이 되는 것의 개수
        val prevSumCount = accSumMap.getOrDefault(accSum[i] - target, 0)
        answer += prevSumCount
        accSumMap[accSum[i]] = accSumMap.getOrDefault(accSum[i], 0) + 1 // 누적합 개수 추가
    }

    println(answer)
}

코드2 (간결한 버전)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, target) = readLine().split(" ").map(String::toInt)
    val nums = IntArray(n + 1)
    val accSum = IntArray(n + 1) // num[1..i]까지의 누적합 저장
    val accSumMap = HashMap<Int, Int>() // 누적합의 개수 저장
    var answer = 0L

    // 누적합 계산
    val st = StringTokenizer(readLine())
    for (i in 1..n) {
        nums[i] = st.nextToken().toInt()
        accSum[i] = accSum[i - 1] + nums[i]
    }

    accSumMap[0] = 1 // accSum[i] == target인 경우를 대비
    for (i in 1..n) {
        // 앞서 저장한 누적합 중 accSum[i]에서 빼면 target이 되는 것의 개수를 더한다
        answer += accSumMap.getOrDefault(accSum[i] - target, 0)
        accSumMap[accSum[i]] = accSumMap.getOrDefault(accSum[i], 0) + 1
    }

    println(answer)
}

피드백

배열에 음,양수가 함께 있을 때는 특정 부분합을 찾기 위한 알고리즘으로 투포인터를 사용하지 않는다. 왜냐하면, 포인터를 움직였을 때 합이 증가할지 감소할지 알 수 없기 때문이다.  

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

문제 유형

그래프 - 다익스트라, BFS

비슷한 문제: https://programmers.co.kr/learn/courses/30/lessons/72413

풀이

문제에 오타가 좀 있고 지문이 불친절했다.

• 선택 가능한 땅의 위치: 정수 1 ~ n
• 구하고자 하는 것: 가장 가까운 친구(A, B, C) 집까지의 거리 기준 가장 먼 곳의 위치
• 가장 먼 곳이란? - 임의의 위치 X에서 A,B,C까지의 거리 중 가장 가까운 거리, 그리고 그 가까운 거리들 중 가장 먼 거리에 있는 곳
• 각 위치 ~ A,B,C의 거리 중 가장 가까운 거리를 찾아야 하므로 모든 거리는 최단거리 기준으로 생각한다. -> 다익스트라 알고리즘 사용

풀이 과정

1. A ~ (1..n), B ~ (1..n), C ~ (1..n)의 최단거리를 각각 구한다 (다익스트라 3번). -> 모든 위치마다 각 점까지의 최단거리를 구하지 않아도 된다. 그러면 시간복잡도가 O(N^2)이 된다.

2. 모든 위치마다 A,B,C까지의 거리 중 가장 짧은 거리와 장소를 계산한다. 

3. 그 중 가장 먼 거리의 장소를 구한다.

for (i in 1..n) {
    var tempMinDist = min(minDist[0][i], minDist[1][i]) // i ~ A,B 중 가까운 거리
    tempMinDist = min(tempMinDist, minDist[2][i])       // 그것과 i ~ C까지의 거리 비교

    // 이전까지의 가장 먼 거리보다 더 멀면 정답 갱신
    if (maxOfMinDist < tempMinDist) {
        maxOfMinDist = tempMinDist
        answerLand = i
    }
}

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

data class Edge(val from: Int, val to: Int, val dist: Int)

lateinit var graph: Array<MutableList<Edge>> // 인접 리스트

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val (a,b,c) = readLine().split(" ").map(String::toInt)
    val m = readLine().toInt()
    graph = Array(n+1) { mutableListOf<Edge>() }
    val minDist = Array(3){
        IntArray(n+1) { -1 }
    } // a,b,c에서 모든 지점까지의 최단 거리

    repeat(m) {
        val st = StringTokenizer(readLine())
        val land1 = st.nextToken().toInt()
        val land2 = st.nextToken().toInt()
        val dist = st.nextToken().toInt()
        graph[land1].add(Edge(land1, land2, dist)); graph[land2].add(Edge(land2, land1, dist))
    }

    // a,b,c에서 모든 위치까지의 최단거리를 각각 구한다 (다익스트라)
    calculateMinDist(minDist[0], a)
    calculateMinDist(minDist[1], b)
    calculateMinDist(minDist[2], c)

    var maxOfMinDist = 0 // 최단 거리중 가장 먼 거리
    var answerLand = 0   // 그에 연결되는 땅 - 정답
    
    for (i in 1..n) {
        var tempMinDist = min(minDist[0][i], minDist[1][i]) // i ~ A,B 중 가까운 거리
        tempMinDist = min(tempMinDist, minDist[2][i])		// 그것과 i ~ C까지의 거리 비교

        // 이전까지의 가장 먼 거리보다 더 멀면 정답 갱신
        if (maxOfMinDist < tempMinDist) {
            maxOfMinDist = tempMinDist
            answerLand = i
        }
    }

    println(answerLand)
}

// 다익스트라
fun calculateMinDist(minDist: IntArray, src: Int) {
    val q: Queue<Int> = LinkedList()
    q.offer(src)
    minDist[src] = 0

    while (q.isNotEmpty()) {
        val currentLand = q.poll()

        for (nextEdge in graph[currentLand]) {
            val nextDist = minDist[currentLand] + nextEdge.dist
            // 첫 방문 or 기존 거리보다 짧으면 갱신
            if (minDist[nextEdge.to] == -1 || nextDist < minDist[nextEdge.to]) {
                minDist[nextEdge.to] = nextDist
                q.offer(nextEdge.to)
            }
        }
    }
}

https://leetcode.com/problems/3sum-closest/

유형

투 포인터

해결 과정

- 구하고자 하는 것

정수 배열에서 세 수의 합 가운데 target에 가장 가까운 것

- 쉽게 떠올릴 수 있는 방법

완전 탐색: 삼중 반복문으로 세 수의 합을 모두 확인한다.

==> 문제: O(n^3)으로 시간 내에 해결함을 보장할 수 없다.

- 시간 복잡도 개선한 방법

1. 배열에서 하나의 숫자(num1)를 선택해서 고정한다. -> O(n)
2. 나머지 수 가운데 num1과 더했을 때 target에 가장 가까운 두 수(num2, num3)를 찾는다.
3. 1번 과정을 모든 숫자에 적용해본다.

2번에서 투 포인터 방법을 사용하면 O(n)으로 두 수를 찾을 수 있다. 따라서 위 과정을 따르기 전에 우선 배열을 정렬한다. 따라서 시간 복잡도 = nlogn(정렬) * n(1번) * n(2번) = O(n^2)

- 투 포인터 사용 과정

기준): target에 가까운 정도

정답) target에 가장 가까운 합 -> 꼭 필요한 변수

과정)

1. 포인터를 오름차순 정렬된 배열의 가장 왼쪽(start)과 오른쪽(end)에 하나씩 둔다.

2-1) if 절대값(target - answer) > 절대값(target - num1 + num2 + num3) -> 정답 갱신

2-2)

if (target > num1 + num2 + num3) -> start++

else if (target > num1 + num2 + num3) -> end--

else -> 정답: num1 + num2 + num3

3. start < end일 때까지 2번 과정 반복

코드 (Kotlin)

import kotlin.math.abs

class Solution {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        var answerDiffer = Int.MAX_VALUE // 절대값(target - target에 가장 가까운 합)
        var answerSum = 0 // target에 가장 가까운 합
        nums.sort() // 투 포인터로 해결하기 위해 정렬
        
        for (i in 0 until nums.size - 2) {
            var start = i + 1
            var end = nums.lastIndex
            
            while (start < end) {
                val tempSum = nums[i] + nums[start] + nums[end]
                val tempDiffer = abs(target - tempSum)
                
                // target과 차이가 더 작은 합을 발견하면 정답을 갱신
                if (tempDiffer < answerDiffer) {
                    answerDiffer = tempDiffer
                    answerSum = tempSum
                }
                
                if (tempSum > target) {
                    end--
                } else if (tempSum < target) {
                    start++
                } else {
                    return tempSum // 정답은 꼭 하나라고 했으므로 리턴
                }
            }
        }
        
        return answerSum
    }
}

피드백

투 포인터는 정렬된 배열있고 특정 기준이 있을 때, 기준에 가장 부합하는 최적의 두 수를 빠르게 찾을 때 사용할 수 있다. 이분 탐색과 조건이 아주 유사하다.

https://programmers.co.kr/learn/courses/30/lessons/67258

과정

1. 이분 탐색 * 투 포인터 알고리즘: O(logn) * O(n) = O(nlogn)

1. 보석 종류의 개수를 센다 (HashSet 사용)
2. 구간 길이를 기준으로 이분 탐색을 한다. 
   1. 모든 보석을 포함하는 구간(mid)을 찾았다 -> 정답을 비교,갱신하고 최소 값을 찾기 위해 end = mid - 1
   2. 모든 보석을 포함하는 구간이 없다 -> 길이를 늘려서 (이분 탐색 구간을 오른쪽으로 이동) 확인하기 위해 start = mid + 1
3. 보석 포함 구간을 찾는 과정은 투 포인터(슬라이딩 윈도우) 알고리즘과 Map을 활용한다. (Map 활용법은 아래를 참고해주세요)

2. 슬라이딩 윈도우만 적용하는 알고리즘: O(n)

1. 보석 종류를 센다.

2. 투 포인터로 모든 보석을 포함하는 가장 짧은 구간을 찾는다.

      2-1) 모든 보석을 포함시킬 때까지 end 포인터를 증가시키며 보석을 담는다. (map의 value 증가)

      2-2) 모든 보석을 포함하면,

            2-2-1) 이전에 구했던 구간 길이와 비교해서 정답을 갱신한다.

            2-2-2) start 포인터를 증가시키면서 보석을 버린다.

            2-2-3) 여전히 모든 보석을 포함하고 있으면, 2-2) 의 로직을 반복한다.

💡 Map을 활용해서 구간 내 보석 종류의 개수 관리하는 방법

val countMap = HashMap<String, Int>() // 범위 내 보석 개수 저장, key: 보석, value: 개수
var countInRange = 0 // 범위 내 보석 종류의 개수

// 보석이 새로 추가된 경우 (0 -> 1)
if (countMap[addedGem]!! == 1) {
    countInRange++
}

// 포함됐던 보석이 범위 이동으로 제거된 경우 (1 -> 0)
if (countMap[removedGem]!! == 0) {
    countInRange--
}

전체 코드1 (이분 탐색 + 투 포인터)

import java.util.*

class Solution {
    val gemSet = HashSet<String>() // 모든 보석
    
    fun solution(gems: Array<String>): IntArray {
        
        for (gem in gems) {
            gemSet.add(gem)
        }
        
        var answer = IntArray(2)
        var start = gemSet.size
        var end = gems.size
        
        // 이분 탐색
        while (start <= end) {
            val mid = (start + end) / 2
            val range = findRange(gems, mid)
            
            // 해당 길이로는 모든 보석을 포함시킬 수 없다 -> 길이를 늘린다
            if (range == null) {
                start = mid + 1
            } else { // 포함시킬 수 있다 -> 정답을 갱신하고, 최소 길이를 탐색한다
                answer[0] = range.first
                answer[1] = range.second
                end = mid - 1
            }
        }
            
        return answer
    }
    
    // 투 포인터(or 슬라이딩 윈도우)
    fun findRange(gems: Array<String>, rangeLength: Int): Pair<Int, Int>? {
        val countMap = HashMap<String, Int>() // 범위 내 보석 count
        var countInRange = 0 // 범위 내 보석 종류의 개수
        
        var start = 0
        var end = 0
        
        // [start, end)로 투 포인터 탐색
        // end가 가리키는 보석을 추가하고, end를 증가시키는 구조
        while (end < gems.size) {
            val addedGem = gems[end++]
            countMap[addedGem] = countMap.getOrDefault(addedGem, 0) + 1
            // 보석이 새로 추가된 경우 (0 -> 1)
            if (countMap[addedGem]!! == 1) {
                countInRange++
            }
            
            // rangeLength가 될 때까지는 범위를 늘리기만 한다
            if (end - start < rangeLength) continue
            
            // 모든 보석을 포함하는 구간을 찾았으면 바로 반환
            // why? 가장 왼쪽 범위를 원하고 있기 때문이다
            if (countInRange == gemSet.size) {
                return Pair(start + 1, end) // 진열대 번호: 1 ~ gems.size
            }
            
            val removedGem = gems[start++]
            countMap[removedGem] = countMap[removedGem]!! - 1

            // 포함하던 보석이 범위 이동으로 제거된 경우
            if (countMap[removedGem]!! == 0) {
                countInRange--
            }
        }
        
        return null
    }
}

전체 코드2 (슬라이딩 윈도우 or 투 포인터)

import java.util.*

class Solution {
    
    fun solution(gems: Array<String>): IntArray {
        var answer = IntArray(2)
        val gemSet = HashSet<String>()
        var countMap = HashMap<String, Int>() // 범위 내 보석 개수 저장, key: 보석, value: 개수 
        var countInRange = 0 // 범위 내 보석 종류 수
        var minLength = gems.size + 1 // 모든 보석 포함하는 최소 구간 길이
        
        for (gem in gems) {
            gemSet.add(gem)
        }
        
        var start = 0
        var end = 0
        
        // [start, end) 형태로 구간 탐색
        // end가 가리키는 곳까지 범위를 늘리고, end를 증가시키는 구조
        // 전체 보석을 포함할 때까지 end를 증가시키고, 
        // 보석 하나가 전부 제거될 때까지 start를 증가시키면서 정답을 비교, 갱신한다 
        while (end < gems.size) {
            val addedGem = gems[end++]
            countMap[addedGem] = countMap.getOrDefault(addedGem, 0) + 1
            if (countMap[addedGem]!! == 1) {
                countInRange++
            }
            
            // start를 오른쪽으로 한 칸 옮겼는데도 여전히 모든 보석을 포함하는 경우가 존재한다.
            // ex) 범위 내에 start 보석을 2개 이상 갖고 있는 경우
            // 따라서, 보석 하나가 0이 될 때까지 start를 증가시키면서 정답 갱신 조건을 확인한다
            while (countInRange == gemSet.size) {
                if (minLength > end - start) {
                    minLength = end - start
                    answer[0] = start + 1
                    answer[1] = end
                }
                
                val removedGem = gems[start++]
                countMap[removedGem] = countMap[removedGem]!! - 1
                if (countMap[removedGem]!! == 0) {
                    countInRange--
                }
            }
        }
            
        return answer
    }
}