코딩테스트 시간초과 해결법 (백준)

1. 코드를 PYPY3로 돌려본다. pypy3도 파이썬으로 만든거지만 속도도 빠르고 문법이 동일해서 pypy3로 바꿔주기만 하면 된다.

2. 입력을 받을 때 input()대신에 sys.stdin.readline()을 사용하자. 거의 2배는 빠르다고 한다. input()은 rstrip()을 적용해 반환하기 때문에 느리다.
※ 주의) sys.stdin.readline()는 \n도 받아오기 때문에 항상 .strip()을 해줘야한다.

3. 반복문 줄이기, 특히 중첩 for문

4. 재귀함수를 쓰는 경우, 메모이제이션 기법을 활용해보자.
▶ 이전에 계산한 값을 중복 계산하지 않기 위해 저장해놓는 기법. 팩토리얼이나 피보나치수열 처럼 기존에 한번 계산을 했던 것이 나중에 반복적으로 다시 나올 때 사용하면 효율적이다.

5. ★★★빈 리스트에 append()로 직접 채우지 말고, 원하는 리스트의 크기 n 만큼 list = [0]*(n+1)와 같이 초기화시킨 뒤에, 인덱스로 접근해 해당 위치에 직접 값을 넣어주는 게 좋다.

▶ 파이썬 함수별 시간복잡도 참고
https://wiki.python.org/moin/TimeComplexity

6. 줄바꿈 할때엔 print()가 아니라 '\n'을 사용하기. for문 마다 출력하지 말고 문자열 변수에 저장해놓고 한 번에 출력 
Ex) for i in num_lst :
     num += (str(i) + '\n')

---

＠ 나의 생각 @

이제 실버3이지만, 일단 지금은 리스트를 최대한 안쓰는 방향으로 문제를 해결하는게 좋다고 생각한다.

리스트에서 시간초과가 나는 경우가 정말 많았다.

워낙 입력값이 크기 때문에, 리스트는 보통 시간초과가 나는 것 같다.

최대한 for문 안에서 해결해보려고 하고, 그래도 안되면 크기를 고정시켜서 리스트를 선언해 사용하는 게 좋아보인다.