[Codility] (Swift) CountDiv

 

🟠 문제

 

🟠 오답으로 바라본 나의 코드

이번에도 역시, time out 이다.ㅋㅋㅋㅋㅋ 내가 여태까지 코딩테스트를 준비했을때, 시간복잡도에 대해서 크게 고려하지 않고 공부했었다. 대체 이걸 어떻게 고려하면서 공부한단 말인가? 다들 천재인가...  그냥 문제를 풀지도 못하는데 시간복잡도까지 고려해야하다니,, 흑.. 슬프다.

이게 나의 코드이다. 그냥 진짜 도 단순하게 for문을 갈겼다!

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    var count = 0
    for i in A...B {
        if i % K == 0 {
            count += 1
        }
    }
    return count
}

역시나,,, 시간초과. 만약 A가 1, B가 2,000,000,000이고, K가 2라면, 최대 2,000,000,000의 for문이 돌게 된다. 돌아버려~ 당연히 시간초과지. 어떻게 해결할까 머리를 싸매어보자. 

자자 단순하게 for문을 최소로 돌릴 수 있는 방법을 찾아보자.

🔖 B에서 A를 빼고, K로 나눠준 몫을 결과값으로 가진다면?

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    let range = B - (A - 1)
    return range / K
}

웨않되...  코드를 이렇게 썼는데, 아래 케이스들에서 전부 오답이었다. 답은 정말 가까운데 다 1정도의 차이로 오답이 났다. 그래서 다양하게 범위를 수정하면서 코드를 작성했는데, 게속 오답,, 대체 왜?

A = 11, B = 345, K = 17 케이스도 틀렸다. 자자 살펴보자. 345까지 17의 배수는 총 20개다. 아,, 근데 19개라고 출력됐구나. 왜 이렇게 나오지?

345에서 11을 빼버리니까,334가 된다. 결국, 334까지 17의 배수를 찾게 되면, 17의 배수인 340이 범위안에 들어가지 못해서 갯수가 세어지지 않은 것이다. 그렇다면,, 다른방식응로 해야한다. (이 방법으로 내가 잘못한줄 모르고 계속 코드만 고치고 있었다. ㅋㅋ 바보.. .하..)

🔖 그럼 B까지의 배수 갯수에서 A까지의 배수 갯수를 빼주자

이 그림과 같은 풀이로 문제를 풀어보자!

 

아 왜 또 오답이야...

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    let bcount = B / K
    let acount = A / K

    return bcount - acount
}

결국 화가나서 인터넷을 봤다. 뭐라고??? 나눗셈을 하면 반올림되어 integer로 표현된다고?!?! 참나.. 그니까 나눈 결과가 2.5면, 3이 출력된다는 것이다. 그래서 계속 틀렸던것.. 아니 그럼,, 하.. Floor 처리로 소수점아래를 버려버리자... ㄱㄷㄱㄷ
(참고 - https://jeong9216.tistory.com/440)

 

🟠 정답코드

public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int {
    let bcount = Int(floor(Double(B) / Double(K)))
    let acount = Int(floor(Double(A-1) / Double(K)))

    return bcount - acount
}

오아아아아,,, 진짜 어이없어! floor로 소숫점을 버려주고 최종적으로 빼서 값을 도출해냈다. .. 드디어 성공