<프로그래머스> 롤케이크 자르기(Lv.2)
[깃허브]
[프로그래머스]
https://school.programmers.co.kr/learn/courses/30/lessons/132265
지금 푸는 문제들을 보면 이제 시간복잡도를 생각해야하는 문제들이 나오기 시작함을 느낀다.
이번 문제도 그렇고 저번 주에 풀었던 문제들도 그렇고...
보통 가장 먼저 생각나는 방법들은 시간복잡도를 오버하게 된다.
제일 많은 경우가 2중 반복문이지 않나 싶다.
이번 문제의 경우에도 1000000개의 배열을 2중 반복문으로 돌기만 하면 풀리는 쉬운 문제이지만 제한 시간이 그 방법을 막고 있기에 다른 생각을 해야만 했다.
왜 이리 시간복잡도를 줄이는 과정이 어려운지... 이 부분은 풀 때마다 어떻게 하면 될까를 계속 고민하면서 해야지만 몸에 체득할 수 있을 것 같다.
초반에 쉬운 문제를 풀 때는 그런 걸 생각 안 하고 풀어도 정답이 되니까 넘어갔었는데 지금은 브레이크가 걸리니까 오히려 코드를 작성하는 시간보다 시간복잡도를 생각하며 알고리즘을 생각하는 시간이 길어진다.
이 문제도 3번정도 코드가 변했다.(깃허브에 다 올려놨다.)
처음은 당연히 안 될 걸 알면서도 2중 반복문과 같은 O(n^2) 형태의 코드를 짜서 시간초과를 맞이했다.
다음에는 도저히 생각이 안 나서 힌트를 보고 진행을 했는데 틀렸다. 무려 시간초과가 났다.
'이럴리가 없는데...?!'라고 생각하며 당황해서 코드를 뜯어보는데 딱 하나로 인해서 시간초과가 났었던 거였다.
시간초과가 난 부분을 바꾸고 나니까 시간이 거의 100배이상 빠르게 통과했다.(문제를 해결했다는 소리다.)
그 부분은 바로 배열에 사용한 += 연산자 때문이었다.
나는 보통 크기를 주지 않고 배열을 선언한 다음 += 연산자로 배열에 값을 집어넣는 방식을 선호하는데,
이 방식이 과부하가 많이 된 것 같다.
좀 검색을 해보니까 plus 연산자랑 += 연산자가 같다고 보이는데 plus 연산자의 경우 배열의 끝에 하나의 요소를 추가한 새로운 배열을 생성한다.
그렇게 되면 크기가 큰 배열에 한 가지 값을 추가한 크기의 새로운 배열을 만들어야하고 그걸 반환해줘야하니 시간이 오래 걸릴 수 밖에 없는거였다.
그 부분을 배열의 크기를 미리 정해놓고 = 연산자로 하니까 해결이 되었다.
해당 방법으로 작성한 코드는 다음과 같다.
class Solution {
fun solution(topping: IntArray): Int {
var answer: Int = 0
// 형 조각
var onePiece = IntArray(topping.size) {0}
// 동생 조각
var anotherPiece = IntArray(topping.size) {0}
// 형 조각 토핑 종류
var oneToppingCount = mutableSetOf<Int>()
// 동생 조각 토핑 종류
var anotherToppingCount = mutableSetOf<Int>()
for (i in topping.indices) {
// 왼쪽부터 오른쪽으로
oneToppingCount.add(topping[i])
onePiece[i] = oneToppingCount.size
// 오른쪽에서 왼쪽으로
anotherToppingCount.add(topping[topping.size - 1 - i])
anotherPiece[i] = anotherToppingCount.size
}
for (i in 0 until topping.size - 1) {
// 토핑 종류 비교
if (onePiece[i] == anotherPiece[topping.size - 2 - i]) answer++
}
return answer
}
}(재귀로도 해보려고 했었는데 손으로 그려보고 흐름을 익혔어도 코드로 표현하는 건 안 돼서 이쪽으로 해결했다.)