삼총사 (considering 시간복잡도) / 시간복잡도를 고려하니 중복값 문제 발생

문제

풀이

import Foundation

func solution(_ number:[Int]) -> Int {
    var count = 0
    let n = number.count
     
    for i in 0..<n {
        for j in i+1..<n {
            for k in j+1..<n {
                if number[i] + number[j] + number[k] == 0 {
                    count += 1
                }
            }
        }
    }
    
    return count
}

 

해석

 

-> 이 풀이법은 모든 경우의 수를 탐색하기 때문에 시간복잡도 O(n^3)이다.

시간복잡도란? 

시간 복잡도가 뭔가요?

💡 시간 복잡도는 꼭 최악의 경우를 기준으로 계산해야합니다.

• 정의
  • 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간 복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. (출처: 위키피디아)
  • 정의가 다소 난해하지만, 예제와 함께 직접 계산해보시면 이해가 빠릅니다.

 

func findMaxNum(_ array: [Int]) -> Int? {
    for num in array {
        for compareNum in array {
            if num < compareNum {
                break
            }
        }
        else {
            return num
        }
    }
    return nil
}

let input = [3, 5, 6, 1, 2, 4]

let result = findMaxNum(input)
print("정답 = 6 / 현재 풀이 값 = ", findMaxNum([3, 5, 6, 1, 2, 4]) ?? "결과 없음")
print("정답 = 6 / 현재 풀이 값 = ", findMaxNum([6, 6, 6]) ?? "결과 없음")
print("정답 = 1888 / 현재 풀이 값 = ", findMaxNum([6, 9, 2, 7, 1888]) ?? "결과 없음")

이 함수의 시간 복잡도를 계산해볼까요?

for num in array { // array 의 길이만큼 아래 연산이 실행
    for compareNum in array { // array 의 길이만큼 아래 연산이 실행
        if num < compareNum { // 비교 연산 1번 실행
            break
        }
    }
    else {
        return num
    }
}

• 위에서 언급한 말을 다시 살펴볼게요.
  • 문제를 해결하는데 걸리는 시간과 입력의 함수 관계
• 입력
  • array의 원소 갯수 = N
• 실행 시간
  • array의 원소 갯수 X array의 원소 갯수 X 비교 연산 1번 = N X N
  • 그러면 우리는 이제 이 함수는 $N^2$ 만큼의 시간이 걸렸겠구나! 라고 말할 수 있습니다.
• 시간 복잡도는 Big-O(빅오) 표기법으로 표시하며 이 경우엔 O($N^2$)의 시간 복잡도를 가진다고 합니다.

func findMaxNum(_ array: [Int]) -> Int? {
    guard let firstNum = array.first else {
        return nil
    }
    
    var maxNum = firstNum
    
    for num in array {
        if num > maxNum {
            maxNum = num
        }
    }
    
    return maxNum
}

let input = [3, 5, 6, 1, 2, 4]
let result = findMaxNum(input)
print("정답 = 6 / 현재 풀이 값 = ", findMaxNum([3, 5, 6, 1,

• 입력
  • array의 원소 갯수 = N
• 실행 시간
  • max_num 대입 연산 = 1번
  • max_num 대입 연산 1번 + array의 길이 X (비교 연산 1번 + 대입 연산 1번) = 1 + 2N
  • 마찬가지로 이 함수는 2N + 1의 시간이 걸렸겠구나! 라고 말할 수 있습니다.
  • 하지만, 빅오 표기법에서는 N의 지수부분만이 유효하게 쓰이고 나머지는 절삭합니다.
    • 다시 말해서 2N + 1 → O(N)입니다.

강의자료

https://gigantic-comte-5b4.notion.site/98ed8e3feb16417e8c8e978383141ac0#2215190d4a2a40fe98fc3741ef762566

알고리즘 강의 | Notion

 

시간복잡도를 고려한 풀이

import Foundation

func solution(_ number: [Int]) -> Int {
    var count = 0
    let sortedNumbers = number.sorted()
    let n = sortedNumbers.count
    
    for i in 0..<n {
        var left = i + 1
        var right = n - 1
        
        while left < right {
            let sum = sortedNumbers[i] + sortedNumbers[left] + sortedNumbers[right]
            
            if sum == 0 {
                count += 1
                left += 1
                right -= 1
            } else if sum > 0 {
                right -= 1
            } else {
                left += 1
            }
        }
    } 
    return count
}

-> 포인터 알고리즘을 사용한 풀이법을 사용하면 시간복자도를 O(n^2)으로 줄이고자 했으나, 

                left += 1
                right -= 1

sum이 0일 때, left += 1와 right -= 1을 동시에 수행하면, 같은 합을 가지는 다른 조합을 놓칠 수 있다. 정확한 카운트를 위해 sum이 0일 때, left 또는 right 포인터만 이동시키거나, 중복된 값을 처리하는 로직을 추가해야 한다.

예를 들어, [-1, 0, 1, 1] 같은 배열이 있을 때, [-1, 0, 1]과 [-1, 0, 1]이라는 같은 합을 가지는 두 조합이 있다. 하지만 위 코드는 이 두 조합 중 하나만 카운트하게 된다.

import Foundation

func solution(_ number:[Int]) -> Int {
    var count = 0
    let sortedNumbers = number.sorted()
    let n = sortedNumbers.count
    
    for i in 0..<n {
        var left = i + 1
        var right = n - 1
        
        while left < right {
            let sum = sortedNumbers[i] + sortedNumbers[left] + sortedNumbers[right]
            
            if sum == 0 {
                count += 1
                while left < right && sortedNumbers[left] == sortedNumbers[left + 1] {
                    left += 1
                }
                while left < right && sortedNumbers[right] == sortedNumbers[right - 1] {
                    right -= 1
                }
                left += 1
                right -= 1
            } else if sum > 0 {
                right -= 1
            } else {
                left += 1
            }
        }
    } 
    return count
}

-> sum이 0일 때, left와 right 포인터가 가리키는 값이 중복되는 경우를 처리한 코드