프로그래머스 - 추억 점수

https://school.programmers.co.kr/learn/courses/30/lessons/176963

프로그래머스

 

 

첫 풀이

photo에 담긴 배열 수만큼 result 에 합산한 값을 담아주었다.

 

이떄 photo에 있는 이름을 name 배열에서 firstIndex(of: 검색할값)으로 인덱스를 찾고

 

그리움 점수 배열에 해당 인덱스를 넣어 점수를 합산했다.

 

func solution(_ name:[String], _ yearning:[Int], _ photo:[[String]]) -> [Int] {
    
    var result : [Int] = []
    
    for (index, people) in photo.enumerated() {
        
        var score = 0
        
        for photoName in people {
            if let nameIndex = name.firstIndex(of: photoName) {
                score += yearning[nameIndex]
            }
        }
        
        result.append(score)
    }
    return result
}

 

문제점

앱을 개발할때 if let 문법을 자주써서 언래핑을 하는 방법으로 이를 채택했지만

 

외부 for문과 내부 for문 루프 firstIndex 배열 순회로 인해

 

시간 복잡도가 O(N * M * K) 가 된다

 

해결 방안

Dictionary를 생성하고 이중 for문 순회후에 Dictionary 검색을 하는 방안으로 개선해보았다.

 

이렇게 하면 *K 가 아닌 + K 의 시간 복잡도를 가지게 된다.

 

func solution(_ name:[String], _ yearning:[Int], _ photo:[[String]]) -> [Int] {
    // 처음에 한 번만 Dictionary 생성 - O(K)
    let scoreDict = Dictionary(uniqueKeysWithValues: zip(name, yearning))
    
    var result : [Int] = []
    
    for people in photo {  // O(N)
        var score = 0
        for photoName in people {  // O(M)
            score += scoreDict[photoName] ?? 0  // O(1)
        }
        result.append(score)
    }
    return result
}

 

if let 으로 언래핑 하지 않고 값이 없을 경우 0을 더해주는 방식으로 개선해주었다.