[프로그래머스] 로또의 최고순위와 최저순위 (Swift) (스터디)

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

코딩테스트 연습 - 로또의 최고 순위와 최저 순위

1. 적용 알고리즘과 문제 설명

문제 설명

1부터 45까지의 수를 중복없이 6개가 나열된 로또 번호가 2개 주어진다. (배열 2개, 중복없음은 하나의 로또 번호안에서만 해당)

하나는 민우의 손상된 로또 번호로, 0으로 표시된 수가 손상된 수이다.

다른 하나는 당첨 번호를 담은 로또이다. 

이때, 민우가 가진 로또가 될 수 있는 최고 순위와 최저 순위를 구하여 순서대로 배열에 담아 반환하는 문제.

 

적용 알고리즘

배열의 전체요소를 탐색하면서 값을 확인하면 되는 단순 구현 문제라 적용 알고리즘은 딱히 없음.

 

2. 코드에 대한 설명

import Foundation

func solution1(_ lottos:[Int], _ win_nums:[Int]) -> [Int] {

	// '맞춘개수:순위'를 대응시킨 딕셔너리
    let scoreRankMap: [Int:Int] = [0:6, 1:6, 2:5, 3:4, 4:3, 5:2, 6:1]
    
    var correctCount: Int = 0 // 확실이 맞춘 숫자의 개수
    var unclearCount: Int = 0 // 모르는 숫자의 개수
	
    // 본인의 로또 숫자 배열 탐색하면서 0의 개수와 확실히 맞춘 수의 개수 카운팅 
    lottos.forEach{
        if $0 == 0 { unclearCount += 1 }
        else if win_nums.contains($0) { correctCount += 1 }
    }
	
    // 최저순위 = 확실히 맞은 수 빼고 다 틀렸을 때 (== 확실히 맞은 개수)
    let lowestRank = scoreRankMap[correctCount] ?? 0
    // 최고순위 = 모르는 숫자가 모두 당첨 번호일 때 (== 확실히 맞은 개수 + 모르는 수의 개수)
    let highestRank = scoreRankMap[correctCount + unclearCount] ?? 0

    return [highestRank, lowestRank]
}

 

3. 다른 풀이에 대한 설명

import Foundation

func solution2(_ lottos:[Int], _ win_nums:[Int]) -> [Int] {
    
    let scoreRankMap: [Int:Int] = [0:6, 1:6, 2:5, 3:4, 4:3, 5:2, 6:1]
    
    // filter 고차함수 사용
    var correctCount: Int = lottos.filter{ win_nums.contains($0) }.count
    var unclearCount: Int = lottos.filter{ $0 == 0 }.count
    
    let highestRank = scoreRankMap[correctCount + unclearCount] ?? 0
    let lowestRank = scoreRankMap[correctCount] ?? 0

    return [highestRank, lowestRank]
}

4. 시간 복잡도, 공간 복잡도 계산

기존 풀이의 시간 복잡도, 공간 복잡도

 

시간 복잡도

forEach문 안에 있는 조건문의 contains 메서드의 시간복잡도가 O(n)이므로

총 O(n^2)..ㅎ..

탐색 시간복잡도를 줄이려면 이분탐색을 사용하는 방법도 있음. 이분탐색의 시간복잡도가 O(logN)인데 이분탐색을 하려면 정렬을 해야하니까 퀵정렬로 한다고 하면 O(NlogN) = O((N+1)logN) -> 이걸 N번 반복하니까 O((N^2+N)logN) 

결론 : 이분탐색을 사용하는거 X

 

공간 복잡도

입력받은 배열들 외에 n값에 따라 변하는 변수나 상수가 없으므로 O(n)

 

5. 사용 라이브러리

swift의 Array 메서드 contains(_:) 사용

https://developer.apple.com/documentation/swift/array/2945493-contains

Apple Developer Documentation

 

6. 문제 풀이에 어려웠던 점

딱히 없었음