Algorithm 2022 Kako

2022 Kakao 인턴십 오답노트

Posted by Neph's Blog on March 4, 2023

문제 링크: 2023 KAKAO TECH INTERNSHIP

1. 성격 유형 검사하기

풀이 설명이 필요없을 정도로 너무 간단한 문제여서 어떻게 하면 코드가 좀 깔끔해질까를 고민하면서 짰다.

사전순 배열은 나중가서 sorting 하기보다는 처음부터 사전순으로 넣을 방법을 고민하는 것이 좋다는걸 경험으로 익혔기에 해당 방법을 적용했다.

2. 두 큐 합 같게 만들기

queue1의 sum과 queue2의 sum을 비교해 같아지면 answer를 return, 한쪽의 sum이 0이되면 -1을 return하도록 했다.

하지만 계속 2개의 케이스에서 시간초과를 받았고, 성능상의 문제라기보단 무한루프에 빠지는 경우가 있다고 판단하고 찾기 시작했지만 무한루프에 빠지는 문제는 아니었다.

다른 블로그의 풀이를 보니 swift에서 지원하는 큐가 없어서 속도가 느린 것이 문제였다. (SwiftAlgorithm에서 구현한 Queue를 사용해도 마찬가지)

하나의 긴 배열을 사용해 index를 통해 움직이는 큐를 사용해도 실패했고, circular queue를 사용해도 실패했다.

이 블로그 글을 통해 실마리를 잡았는데

firstEnd가 배열의 최종 인덱스보다 커질때 (circular queue의 오버플로우 해결 연산시에) -1을 return 해주면 되는 문제였다.

이를 그림으로 풀어 설명하자면

image-20230304220611453

두개의 큐에서 한쪽에서 dequeue되면 한쪽은 그걸 그대로 enqueue하니 마치 땅따먹기 같은 모양새를 하게 되는 것까지는 이해를 했지만 어째서 End가 배열의 인덱스를 넘어간 것이 유망하지 않다는 근거가 되는지는 이해를 못했다. 🥲

아래는 기록을 위한 정답 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import Foundation

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var answer = 0
    var circularQueue = queue1 + queue2
    var firstStart = 0
    var firstEnd = queue1.count - 1

    var firstSum = 0
    var secondSum = 0

    for i in 0..<queue1.count {
        firstSum += queue1[i]
        secondSum += queue2[i]
    }
    var target = (firstSum + secondSum) / 2

    while firstSum != target {
        if firstSum > target {
            firstSum -= circularQueue[firstStart]
            firstStart += 1
        } else {
            firstEnd += 1
            if firstEnd > circularQueue.count - 1 {
                return -1
            }
            firstSum += circularQueue[firstEnd]
        }
        answer += 1
    }

    return answer
}

다른 사람들의 풀이를 보니 단순히 answer가 100만을 넘어갔을때 -1을 return 하는 경우도 있었는데

sum이 가질 수 있는 모든 경우의 수는 1칸짜리로 가질 수 있는 최대 경우의 수인 60만부터 60만칸짜리로 가질 수 있는 최대 경우의 수 1까지를 모두 더한 ((1+60만) * 60만) / 2가 되어야 할 것 같은데

100만이라는 매직넘버로 해결이 가능한것도 조금 이해가 가지 않는다

심지어 60만, 70만 같은 숫자는 런타임에러를 뿜고 오답처리가 되던데..

무엇이 잘못된건지 전혀 모르겠다 🥲

해결

첫 제출한 답안은 무한 루프에 빠지는 것이 맞았다.

Q1과 Q2의 sum이 1이 차이나는 경우 계속해서 계속해서 값을 주고받게 되면서 무한루프에 빠지던 것이었다.

이를 해결하기 위해선 “한바퀴”를 돌았는지 확인해서 한바퀴를 돌았다면 유망하지 않으니 -1을 리턴할 수 있던 것이었다.

3. 코딩 테스트 공부

처음 문제를 쭉 읽고 이거 DP인데? 하는 생각은 들었다.

하지만 그래서 dp 배열을 어떻게 채우지? 🧐 하는 생각이 해결되지 않았고

결국 공식 풀이를 읽고 dp로 푸는거 맞네 하면서 다시 돌아와 풀었다.

원인을 생각하다보니 아무래도 top-down 풀이만 생각하고 bottom-up을 통한 풀이를 생각하지 못했던게 제일 큰 원인이었던 것 같다.

풀이를 알고 나서도 꽤 헤맸는데 최대 알고력, 코딩력 이상으로 알고력과 코딩력이 올라갔을때의 처리가 미흡했었다.

4. 등산 코스 정하기

처음엔 아래와 같은 DFS로 접근했었다.

하지만 O(n^3)이나 되는 시간복잡도는 아무리 최적화를 해도 시간초과 실패만 맛보게 해줄 뿐이었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import Foundation

var graph: [[(dest: Int, weight: Int)]] = []
var gates = [Int]()
var summits = [Int]()
var answer = (Int.max, Int.max)

func solution(_ n:Int, _ paths:[[Int]], _ allGates:[Int], _ allSummits:[Int]) -> [Int] {
    gates = allGates
    summits = allSummits
    graph = Array(repeating: [], count: n + 1)
    paths.forEach {
        graph[$0[0]].append((dest: $0[1], weight: $0[2]))
        graph[$0[1]].append((dest: $0[0], weight: $0[2]))
    }
    allSummits.forEach {
        let visited = Array(repeating: false, count: n + 1)
        findPath(visited: visited, current: $0, intensity: -1, summit: $0)
    }

    return [answer.0, answer.1]
}

func findPath(visited: [Bool], current: Int, intensity: Int, summit: Int) {
    var visited = visited
    visited[current] = true
    if intensity > answer.1 { return }
    if gates.contains(current) {
        if intensity == answer.1 {
            answer = (min(answer.0, summit), intensity)
        } else if intensity < answer.1 {
            answer = (summit, intensity)
        }
        return
    }
    graph[current].forEach {
        if visited[$0.dest] {
            return
        }
        findPath(
            visited: visited,
            current: $0.dest,
            intensity: max(intensity, $0.weight),
            summit: summit
        )
    }
}

3번 문제와는 정반대로 이번엔 다익스트라라는 풀이를 전혀 떠올리지 못했다.

“최단거리, 최소시간” 등의 다익스트라와 익숙한 다익스트라와 달리

최대 구간 거리인 intensity가 등장했기에 더 떠올리기 어려웠던 것 같다.

추가

다익스트라로 바꿔서 풀어도 계속해서 시간초과가 떴다.

아무래도 O(n^2)짜리 다익스트라가 아닌 우선순위큐를 사용하는 O(nlogn)짜리 다익스트라를 써야 풀리는 모양이다..

스위프트에서는 이를 지원하지 않기에 힙과 우선순위큐를 구현해야 했는데, 이는 넘어가기로 했다..

다익스트라 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

import Foundation
let infinite = 20_000_000

func solution(_ n:Int, _ paths:[[Int]], _ gates:[Int], _ summits:[Int]) -> [Int] {
    var answer = [Int.max, Int.max]
    var matrix = Array(repeating: Array(repeating: infinite, count: n + 1), count: n + 1)
    var visited = [true] + Array(repeating: false, count: n)

    func initialize() {
        visited = [true] + Array(repeating: false, count: n)
        matrix = Array(repeating: Array(repeating: infinite, count: n + 1), count: n + 1)
        for path in paths {
            let start = path[0]
            let dest = path[1]
            let weight = path[2]
            if gates.contains(start) || summits.contains(dest) {
                matrix[start][dest] = weight
            } else {
                matrix[start][dest] = weight
                matrix[dest][start] = weight
            }
        }
    }

    func leastCostNodeWhereNotVisited(start: Int) -> Int {
        var nodeIndex = 0
        var min = Int.max
        for i in 1..<n+1 {
            if matrix[start][i] < min && !visited[i] {
                nodeIndex = i
                min = matrix[start][i]
            }
        }
        return nodeIndex
    }

    for gate in gates {
        initialize()
        for _ in 1..<n+1 {
            let currentByWayNode = leastCostNodeWhereNotVisited(start: gate)
            visited[currentByWayNode] = true
            for dest in 1..<n+1 {
                if matrix[gate][currentByWayNode] == infinite || matrix[currentByWayNode][dest] == infinite {
                    continue
                }

                if matrix[gate][dest] == infinite {
                    matrix[gate][dest] = max(matrix[gate][currentByWayNode], matrix[currentByWayNode][dest])
                } else {
                    matrix[gate][dest] = min(matrix[gate][dest],
                                             max(matrix[gate][currentByWayNode], matrix[currentByWayNode][dest]))
                }
            }
        }

        for summit in summits {
            if matrix[gate][summit] <= answer[1] {
                if matrix[gate][summit] == answer[1] {
                    answer[0] = min(answer[0], summit)
                    answer[1] = matrix[gate][summit]
                } else {
                    answer[0] = summit
                    answer[1] = matrix[gate][summit]
                }
            }
        }
    }


    return answer
}
print(solution(7, [[1, 2, 5], [1, 4, 1], [2, 3, 1], [2, 6, 7], [4, 5, 1], [5, 6, 1], [6, 7, 1]], [3, 7], [1, 5]))
CATALOG
    FEATURED TAGS
    운영체제 컴퓨터네트워크 Computer Science OS 데이터베이스 collectionView 날짜 다루기 Alamofire Algorithm Date app life cycle 알고리즘 2023 Kako ARC AppDelegate BFS Notification animation background foreground strong weak