konis123   2년 전

우선 제가 푼 방법은


1 3 4 5 6 3 4 8 4 2

이런식으로 있다고 하면,  반복문을 10번 도는데

첫번째  반복을 돌때에는 1이 자기자신을 가리키므로 +10000000을 해주고 끝나고

두번째 반복을 돌떄에는 3->4->5->6->3 이렇게 가리키므로 6->3 되는 부분에서 또 다시 회전을하면서 4->5->6->3 이 부분만 +10000000 을 더해줍니다. 

그리고 세번쨰 반복을 돌때에는 10000000보다 값이 크므로 바로 리턴을 하고 빠져나오는 식으로.. 나머지 반복을 쭉 도는데요. 

그리고 마지막에 10000000보다 작은 것들의 개수를 세서 출력을 합니다.

일단 테스트케이스는 질문글에있는거 다 해봤는데 다 잘되는거같은데.. 82%에서 시간초과가 나옵니다... 

다른분들중에서도 82%에서 시간초과 뜨시는분이 있는거같은데, 그분이랑은 다른 이유인거같고...(제가 잘 이해를 못했을수도있습니다 ㅠㅠ)

위에 코드가 확실히 비효율적이긴해도 O(n) 인거같은데.. 어디가 문제인지 알려주시면 감사하겠습니다 ㅠㅠㅠ


seico75   2년 전

일단 deep 과 addvalue 가 재귀이기 때문에 O(n)은 아닐 것 같습니다.

만일

2, 3, 4, 5, 6, 7, ..., 99999,100000, 100000

즉 마지막만 자기 자신을 찍은 경우, 

첫번째에서 모든 수열을 다 돌고, 마지막 하나 제외시키고

두번째에서 모든 수열 다 돌고, 실패하고

세번째에서 모든 수열 다 돌고, 실패하고.............

결국 O(n2) 되는거 아닌가요?

한번 거쳐서 실패한 수들은 다시 팀이 될 수 없지 않나 합니다. 

konis123   2년 전

아... 감사합니다! 어떤경우에 안되는건지 이제야 알거같네요!

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