kotlin 의 link[i] 은 java 의 link.get(i) 을 사용하는데, LinkedList.get 의 시간복잡도는 O(n) 입니다.
이렇게 될 경우 33~35번째 반복문의 시간복잡도는 O(n^2) 이 되면서 시간초과가 발생합니다.
반면, link.toCharArray() 의 시간복잡도는 O(n) 인데, 출력할 때 따로 반복문을 사용할 필요가 없으므로 출력의 시간복잡도는 그대로 O(n) 입니다.
1406번 - 에디터
34번째 줄에서 get 의 시간복잡도는 O(n), write 의 시간복잡도는 (1글자를 출력하므로) O(1) 입니다.
34번째 줄의 시간복잡도는 O(n) + O(1) = O(n) 으로 생각할 수 있습니다.
한편, 33번째 줄의 for 문장은 O(n) 번 반복합니다.
O(n) 번 반복하는 반복문 안에 O(n) 이 있으므로 전체 시간복잡도는 O(n) * O(n) = O(n^2) 이 됩니다.
반면, bw.write(link.toCharArray()) 문장에서 toCharArray() 의 시간복잡도는 O(n), write 의 시간복잡도는 (n글자를 출력하므로) O(n) 입니다.
문장의 시간복잡도는 O(n) + O(n) = O(n) 으로 생각할 수 있습니다.
여기에는 반복문이 따로 없으므로 O(n) 으로 계산이 끝납니다.
var check = BooleanArray(1000001){true}
check[0] = false
check[1] = false
for(i in 2..1000000){
if(check[i]){
var j = i
for(j in i+i..1000000 step i){
check[j]=false
}
}
}
bupjae님 혹시 더 설명 가능하시다면 부탁드립니다
다른 문제들도 bupjae님 말씀대로 시간복잡도를 고려하면서 풀었는데
풀면서 헷갈리는 부분들이 생겼습니다.
4번째 줄 for문에서 1,000,000번 반복하는 O(n)시간복잡도가 있고
그 안에 5번째줄 check[i]도 check의 크기가 1,000,000이므로 O(n)의 시간 복잡도가 있으니 (get을 쓴다고 생각하면)
O(n^2)가 되므로 시간초과가 되는게 아닌가요? (참고로 문제는 17103 골드바흐파티션입니다.)
제가 어디서 잘못 이해한것인지 알려주시면 감사하겠습니다.
댓글을 작성하려면 로그인해야 합니다.
devhyun46 2년 전
아래 코드대로 작성시 시간초과가 납니다..
그런데
for(i in 0 until link.size){
bw.write("${link[i]}")
}
이 부분을 아래처럼 바꿨더니 해결되었어요.
bw.write(link.toCharArray())
왜 for문으로 작성하면 시간초과가 나는지 이해가 안갑니다.
+) 그리고 link.toCharArray()는 문자열을 char형 배열로 바꿔주는 기능을 할 뿐 아닌가요?
배열을 그대로 출력이 원래 가능한건데 제가 몰랐던건지 혼란스럽습니다