devhyun46   2년 전

아래 코드대로 작성시 시간초과가 납니다..

그런데

for(i in 0 until link.size){
bw.write("${link[i]}")
}

이 부분을 아래처럼 바꿨더니 해결되었어요.

bw.write(link.toCharArray())

왜 for문으로 작성하면 시간초과가 나는지 이해가 안갑니다. 

+) 그리고 link.toCharArray()는 문자열을 char형 배열로 바꿔주는 기능을 할 뿐 아닌가요? 

배열을 그대로 출력이 원래 가능한건데 제가 몰랐던건지 혼란스럽습니다

bupjae   2년 전

kotlin 의 link[i] 은 java 의 link.get(i) 을 사용하는데, LinkedList.get 의 시간복잡도는 O(n) 입니다.

이렇게 될 경우 33~35번째 반복문의 시간복잡도는 O(n^2) 이 되면서 시간초과가 발생합니다.

   

반면, link.toCharArray() 의 시간복잡도는 O(n) 인데, 출력할 때 따로 반복문을 사용할 필요가 없으므로 출력의 시간복잡도는 그대로 O(n) 입니다.

devhyun46   2년 전

답변 감사합니다!

그런데 33~35번째 반복문의 시간복잡도는 O(n^2) 이 된다고 하셨는데

이게 get에서 O(n)이랑 bw.write 에서 O(n) 이 걸려서 그런거죠? 근데 왜 제곱이 되는지가 좀 이해가 안가는데 설명 해주실수있나요?

bupjae   2년 전

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) 으로 계산이 끝납니다.

devhyun46   2년 전

완전히 이해되었습니다!

답변 감사합니다!!

devhyun46   2년 전

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 골드바흐파티션입니다.)

제가 어디서 잘못 이해한것인지 알려주시면 감사하겠습니다.

bupjae   2년 전

LinkedList.get 과 다르게, Array.get 의 시간복잡도는 O(1) 입니다.

자료구조에 따라 get 의 시간복잡도가 다릅니다.

   

참고로, 붙여넣으신 프로그램은 '에라스토테네스의 체' 라는 이름이 붙어있으며, 시간복잡도는 O(n log (log n)) 입니다.

댓글을 작성하려면 로그인해야 합니다.