ido0812   11달 전

시간초과가 나는데 어떤 부분을 손보면 좋을지 잘 모르겠습니다 ㅜㅜ 

주석 최대한 달아놓겠습니다. 한번만 봐주실 수 있을까요?

tong39   11달 전

19번 째 줄 nums = nums[1:]로 초기화 하는 과정에서 O(n)만큼의 시간복잡도를 사용해서 시간초과가 나는 것 같습니다. 

변수를 하나 둬서 그 값을 증가시키며 비교하거나 num을 deque 자료형을 사용해서 해결하면 될 것 같네요.

lambda   11달 전

시간 초과 나는 이유는 19번째 줄 때문입니다. python에서 슬라이싱은 새로운 리스트를 만듭니다. 그래서 슬라이싱할 리스트가 길다면 그 만큼 오래 시간이 걸립니다.그러면 슬라이싱을 안쓰고 pop을 쓰면 되지 않나 생각할 수 있는데  nums에서 첫번째 요소를 제거하려고 nums.pop(0)을 쓰는 것도 모든 요소를 한 칸씩 앞으로 옮겨야 하므로 오래 걸립니다.(O(n))

해결 방법으로는 nums를 거꾸로 뒤집어서 만든 다음 요소를 지워야 할 때 마다 nums.pop()으로 마지막 요소를 지우거나 collections모듈의 deque를 이용해서 num.popleft()를 하는 방법도 있습니다. 둘 다 O(1)의 시간이 걸립니다.

좀 더 시간을 줄일 요소가 있는데 첫번째는 출력 부분입니다. 여러 번 print하는 것은 느립니다. 29,30번째 줄처럼 리스트에 저장되어있는 str을 여러줄에 출력할 때는 print('\n'.join(cals)) 처럼 하나의 문자열로 만들어 한번에 출력 하는 것이 빠릅니다. 만약 리스트에 저장되어있는 것이 숫자라면 print('\n'.join(map(str,cals))) 이런식으로 map을 이용 할 수 있습니다.

두번째는 전체를 함수로 감싸는 것입니다. 전역변수에 접근 하는 것 보다 함수 내부의 지역 변수에 접근하는 것이 빠릅니다. 그래서 전체를 함수로 감싸면 더 빠르게 실행됩니다.

http://boj.kr/046f58b4a7f94cb0...

http://boj.kr/04a3b41ebe504e54...

http://boj.kr/bb781c2f26844c99...

http://boj.kr/f71e91f7055a4553...

위에서 부터 deque사용,deque사용+함수,deque사용+ join 을 이용한 print,deque사용+join을 이용한 print+함수 입니다.

시간이 292,256,228,196으로 빨라지는 것을 볼 수 있습니다.

ido0812   11달 전

와 직접 이렇게까지 ㅜㅜㅜㅜ 너무 감사히 잘 배웠습니다 ㅜㅜ 실습도 꼭 해볼게요! 

친절하게 알려주셔서 진짜 감사합니다.. 저도 얼른 잘해져서 많이 베풀겠습니다!

메리 크리스마스 하시고 좋은 하루 보내세요 :)

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