wjdgh12392   1년 전

pypy3로 해도 시간초과가 나네요 80%에서... 감질맛나게... ㅠㅠ

접근 방식이 아예 잘못된걸까요 더 줄일 수 있는 부분이 없는 것 같은데... 고수님들 도움 부탁드리겠슴다!

dong5995   1년 전

굳이 arr이라는 리스트를 만들지 않고 처리할 수 있습니다.

enumerate 라는 함수를 사용하면, 인덱스와 값을 한번에 가져올 수 있습니다.

for point, x in enumerate(choice_number):

대충 이렇게 하면 point와 값을 한번에 얻을 수 있습니다.

그리고 stack에서 확인을 n번 전부 하다보니

1
5
2 3 4 5 3

이런 예제를 넣으면,

[[1, 2]]
[[1, 2], [2, 3]]
[[1, 2], [2, 3], [3, 4]]
[[1, 2], [2, 3], [3, 4], [4, 5]]
[[1, 2], [2, 3], [3, 4], [4, 5], [5, 3]]
[[2, 3]]
[[2, 3], [3, 4]]
[[2, 3], [3, 4], [4, 5]]
[[2, 3], [3, 4], [4, 5], [5, 3]]
[[2, 3], [3, 4], [4, 5], [5, 3], [3, 4]]
[[3, 4]]
[[3, 4], [4, 5]]
[[4, 5]]
[[5, 3]]

스택에 값이 이렇게 들어갑니다.

보시면 2~5번째 줄에서 방문한 값들을 6번째 줄부터 다시 방문합니다.

6번째 줄부터는 모두 1~5번째 줄에서 방문한 값들이기 때문에 다시 방문할 이유가 없습니다.

방문한 값은 바로바로 방문처리해서 다시 방문하지 않도록 해 시간을 줄이셔야 합니다.

dong5995   1년 전

1
5
2 3 4 5 3

이 예제에서 이 코드는 4, 5, 3 이라는 루프가 나올 때까지 모두 방문하게 되는데,

그것보단 2부터 시작해서 3, 4, 5, 3 으로 쭉 따라가다가 4, 5, 3이라는 루프가 발견되는 즉시 개수를 세고 전부 방문처리 하는 게 좋습니다.

극단적인 예시로,

1
100000
2 3 4 5 6 7 8 ...... 99999 100000 99999

이런 예시가 있으면 이 코드에선 첫 번째부터 시작해서 10만 번째까지 확인하고, 두 번째부터 시작해서 10만 번째까지 확인하고.. 가 반복됩니다.

첫 번째부터 시작해서 10만 번째까지 확인했을 때, 99999번째와 10만 번째가 팀을 이루는 것을 인식해서 바로 처리하면 10만 번 반복할 과정을 한 번의 과정으로 처리할 수 있습니다.

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