Kotlin] 프로그래머스 Lv.2, 롤케이크 자르기

https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=2&languages=java%2Cjavascript 

코딩테스트 연습 | 프로그래머스 스쿨

 

 

풀이

이 문제의 문제(?)는 롤케이크 100만개, 토핑이 1만개라는 점이다.

 

처음에,

0부터 토핑 갯수까지 for문을 돌려서 i만큼 자른 후(0부터 i까지 잘라 철수 것, i + 1 부터 끝까지 동생 것) 내부의 토핑을 distinct해서 요소의 갯수가 같다면 answer += 1 해서 결과를 도출하자! 했는데

 

결과는 처참하게 시간초과

 

그 때 깨달았다.

아 이거 시간복잡도 개선하는 문제구나.. distinct도 결국 해당 배열을 전부 돌아 요소를 추출하는거라 결국 시간복잡도가 O^2(N)이겠구나..

 

두 번째는 각 토핑의 범위를 찾아 HashMap<Int, IntRange>를 한 뒤 -> 이를 value.first 순과 value.last 순으로 각각 sorting하하고, valueFirst 에서 동일하게 나누어지는 시작범위를 찾고, valueLast에서 동일하게 나누어지는 종료범위를 찾자!

했는데 이것도 1번 9번 19번 테스트에서 실패했을 뿐만 아니라 

>> 토핑이 1만개 << 에서 1만개가 든 해시맵을 다시 또 배열을 돌려 솔팅을 두 번 하고 또 솔팅된 두 배열을 또 돌아서 값을 또 필터링 하고.. 하다보니 이것도 시간복잡도가 어마무시하게 늘어나는 것이다.. 

 

세 번째는 각 토핑을 갯수를 세어 놓고(O(N)), 배열을 돌면서(O(N)) 갯수를 세어둔 토핑에서 하나씩 빼버린다. 이 때, 남은 토핑의 종류와 내가 가져간 토핑의 종류의 갯수가 같다면 answer += 1을 하자.

갯수를 셀 때는 hashMap<Int, Int>를 이용해서 key에 토핑 종류를, value에 갯수를 넣었다.

근데 또 시간초과가 걸린다.

 

..

..?

..

..

..!

 

아 토핑 1만개였지.

갯수 카운트 하려고 hashMap.count { (key, value) -> value != 0 } 을 넣어놨는데 이거 토핑이 100만개고 종류가 1만개면 백만 돌 때마다 계속 1만씩을 돌아서 1,000,000 * 10,000 번을 또 도는구나 에라이미친;

 

그래서 해시맵에서 쓰이지 않는 값들을 날려버려야 한다 이런미친..

 

class Solution {
    fun solution(topping: IntArray): Int {

        var answer = 0

        var hashMap = HashMap<Int, Int>()
        var hashSet = HashSet<Int>()

        topping.forEach {
            hashMap[it] = hashMap.getOrDefault(it, 0) + 1
        }

        topping.forEach {
            hashSet.add(it)

            hashMap[it] = hashMap[it]!! - 1

            if (hashMap[it] == 0) {
                hashMap.remove(it)
            }

            if(hashSet.size == hashMap.count()) {
                answer += 1
            }

        }

        return answer

    }
}

 

 

++) 아미친 프로그래머스 문제 점점 시간복잡도 따져서 이상한 테스트케이스(귤 천만개, 세일 갯수 10만개) 개많이 나오는데 시간복잡도용 난수만드는 코드라도 만들어야 하나 지금 진지하게 고민됨..