[프로그래머스] (Swift) 타겟넘버 (lv.2) (BFS, 시간초과에 대한 고찰)

 

💬 잡담

아,, 어제 SK플래닛 코테를 봤는데 문제는 분명 쉬었다. 그래 쉬웠어. 근데 나한테 쉬웠다고는 안했다 ㅋㅋㅋㅋㅋ 코테 공부가 아무래도 조금 부족한 지금 수주에서는,,,, 어떻게 풀지 감이 잡힐듯 말듯 하면서 효율성이 엄청 떨어지는 코드를 구현하고 말았다.

어쨌든,, 4문제중에 3솔을 하긴 했다만,,,, 두개정도는 시간초과로 털릴것 같다 헤헤
그러던 와중, 오늘 풀던 문제에서 발생한 시간초과! 
코테를 준비하면 할 수록 시간복잡도에 대한 생각이 깊어진다. 이 문제를 어떻게 빠르게 캐치해낼 수 있을까? 알고리즘을 항상 구현하면서 시간복잡도를 계산하는 버릇을 들여야할 것 같다. 

지금 경우도, 히든케이스에서 두개 시간초과가 났는데,,,, SKP 처럼 히든케이스가 주어지지 않는 시험에서는 이런것을 모른채 제출했겠지..? 그럼 또 탈락이겟지? 하하하하하하하 어렵다 어려워 

 

⚫️ 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=swift 

프로그래머스

 

⚫️ 나의 풀이

뭔가,, 재귀로 풀릴 듯한 느낌은 아니라서 BFS에 대한 기초 개념을 다시 훑고 지나왓다. 그리고 다시 문제를 읽어보는 순간, 아 이건 BFS구나를 깨달았다. (사실,, 이전에 이 문제는 파이썬으로 풀어본 경험이 있다. 아주 쬐끔! 기억이 난다.)

https://github.com/HotCodeBreakers/CodingTest/discussions/25

[개념정리] DFS+BFS (혹시,,, 문제풀이 전에 이코테 책을 보시나요!?) · Discussion #25 · HotCodeBreakers/Codi

내가 정리해둔 이 글을 보면, BFS는 모든 노드를 지나치면서 모든경우의수를 살펴본다. 그렇기 때문에, 한 가지 방향만으로 가서 해를 가져오는 DFS가 아니라, 모든 경우의 수를 살펴보는 BFS 알고리즘이 이 문제에는 더 적합하다. 

어떻게 풀지 고민을 하던 와중, 아래와 같이 규칙을 찾아냈다.

빨간색으로 쓰여진 숫자는 인덱스 번호이다. 연두색 형광팬으로 주어진 부분이 numbers로 들어왔다면, 아래 순서대로 계산을 거친다. 초반에 4혹은 -4가 더해질거고, 그 이후에 인덱스를 하나씩 거듭하며 -와 +를 붙인 것들이 더해질 것이다. 이것을 나는 while문으로 구현했고, while문에서 탈출하는 조건은 더이상 계산할 것이 남아있지 않으면 탈출하라는 조건을 주었다. 

❌ 첫번째 시도 - 시간초과

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var queue = [(Int, Int)]()
    queue.append((-numbers[0], 0))
    queue.append((numbers[0], 0))
    var answer = 0

    while !queue.isEmpty {
        let q = queue.removeFirst()
        let num = q.0
        var idx = q.1
        idx += 1
        if idx < numbers.count {
            queue.append((num+numbers[idx], idx))
            queue.append((num-numbers[idx], idx))
        } else {
            if target == num {
                answer += 1
            }
        }
    }

    return answer
}

시간초과가 났다. 우선, 모든 노드를 탐색해주는 알고리즘을 채택했기 때문에 시간초과에 유의해야함을 알고 있었다. 그럼 이제 수정해볼까,,,

우선 queue의 길이만큼 (노드와 간선의 수만큼) while문이 돌아가기 때문에 현재 시간복잡도는 O(N)이다. 그리고 그 내부에 removeFirst()라는 메서드가 사용되는데, 이 메서드 자체의 시간복잡도도 O(N)이다. 이 부분을 O(1)로 바꿔보는게 어떨까

✅ 두번째 시도 - 정답코드

위에서 언급한것 처럼, 인덱스에 접근하는 방식의 시간복잡도를 O(N)에서 O(1)로 줄이니까 바로 통과가 되었다. 굳이 queue 내부에 첫번째부터 접근해야하는 순차적인 조건이 주어진게 아니기 때문에, queue에 들어어와있는 애들중 마지막 애부터 접근했다. (이름은 큐 이지만, 큐 보다는 스택 성향을 가진 arr를 사용했다고 보면 된다.)

swift에서 removeLast()는 배열의 마지막 원소에 접근하므로, 배열에서 무언가를 꺼냈을때 배열을 재정렬해줄 필요가 없다. 그래서 인덱스로 접근하는 것과 동일한 O(1)의 시간복잡도를 가진다. 그렇게 ... 바로 통과!!

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var queue = [(Int, Int)]()
    queue.append((-numbers[0], 0))
    queue.append((numbers[0], 0))
    var answer = 0

    while !queue.isEmpty {
        let q = queue.removeLast()
        let num = q.0
        var idx = q.1
        idx += 1
        if idx < numbers.count {
            queue.append((num+numbers[idx], idx))
            queue.append((num-numbers[idx], idx))
        } else {
            if target == num {
                answer += 1
            }
        }
    }

    return answer
}

let numbers = [1, 1, 1, 1, 1]
let target = 3

print(solution(numbers, target))

 

💬 또 잡담! 시간초과에 대한 잡담,,

알고리즘과 관련해서 친구와 대화를 나눴다. '비효율적인 코드를 개선한다'라는 이야기가 나와서 '비효율'이란 뭘까에 대해서 잠깐 이야기를 나누는 과정에서 친구가 정확하게 내 사례를 이야기해주었다.

바로 내가 지금 이경우다!! 친구는 몇개가 시간초과가 나는경우, 본인의 알고리즘에 비효율적인 측면을 찾는 과정을 거치는데 그 과정에서 이런 상황도 자주 발생한다고 했다. 지금 딱 내경우다. 나는 queue를 사용할 필요가 없는데 배열을 queue처럼 사용했기 때문에 (removeFirst) 시간초과가 발생했고, 이를 개선하니까 바로 통과가 되었다.

또 시간초과가 나는 이유중 하나가 제대로된 예외처리가 되지 않았을때 많이 발생한다며 예외를 처리하는 부분 먼저 검토하면서 문제를 풀으라고 조언해주었다. 예를들어, 0이면 탈출해야한다거나, 10000번 이상 반복되면 더이상 의미가없는데 내 알고리즘에서 10000번 이상 돌아가고 있다거나 등등! 

그리고 심지어는 input의 범위를 제한해주면서 시간초과문제가 해결되는 경우도 있다고 한다. while문 내부에서 반복횟수를 제한한다거나 이런식으로! 참.. 다양하게 풀린다. 이런 이야기를 해주는 친구를 보면서 얼마나 많은 알고리즘 문제를 풀면서 고민해봤는지 알 수 있었다.... 멋지다! 연진아

또 친구가 많은 조언을 해주었는데 다 나의 경우, 내가 흔히하는 실수들이라 너무 놀랐다. 예를들어 최단거리를 묻는 문제면, 나는 BFS먼저 떠올리는데 사실 다익스트라, 플루이드워셜 알고리즘을 떠올려야 하는 경우가 많다고 하는데,,, 나는 그냥 무턱대고 BFS나 반복문을 떠올리곤 한다 ㅠㅠ 다 겪는 과정이구나... 아직 배울게 너무 많고 갈길이 멀다.