[Python] BOJ(백준) 2170번 - 선 긋기(+ list와 tuple의 차이)

링크

https://www.acmicpc.net/problem/2170

난이도(solved.ac 참고)

골드5

풀이

문제를 보자마자 생각했던 것은

1) 처음 input으로 받은 y - x의 값을 길이를 나타내는 변수인 leng에 초기값으로 두고, 이 y값을 target으로 설정한 다음

2) 정렬이 되어있다는 전제 하에, 이 첫번째 y와 같은 x가 나올 때까지 leng의 값에 (y의 값들 - target)을 더해주고 target을 각 y로 바꿔주는 방식으로 업데이트하자

3) 계속 target값을 업데이트하던 와중에 새로운 x값이 target보다 클 경우 선이 끊어져 있다는 뜻이므로 여기서는 leng에 (새로운 y값 - 새로운 x값)을 더해준 다음 target은 똑같이 새로운 y값으로 바꿔주자

 

라는 것이었다. 그리고 그렇게 코드를 짜니 잘 해결되었다. 사실상 이게 코드에 대한 설명이므로 부가 설명을 덧붙일 필요는 없을 것 같다.

 

+) 이 문제를 풀면서 PyPy3으로는 잘 통과했으나 Python 3으로는 시간 초과가 떴었다. 이유가 뭘까 하다가, 예전에 얼핏 듣기로 튜플이 리스트보다 더 빠르단다. 그래서 6행에서 sorted([list~]) 를 sorted((list~)) 로 바꿔줬더니 시간초과를 해결했다. 문제를 해결하고서 어떤 차이가 있는지 궁금해서 구글링을 좀 해봤다.

 

여기에 자세한 설명이 나와있었고, 골자는

1) 튜플을 만드는 게 리스트를 만드는 것보다 더 빠르다.
2) 튜플이 인덱싱할 때 더 적은 포인터를 사용하기 때문에 리스트보다 더 빠르다.
3) 리스트의 경우 값이 바뀔 수 있으므로, 여분의 storage가 필요하다. 그래서 튜플을 해주면 메모리 절약도 할 수 있다.

이 세 가지였다. 리스트를 튜플로 바꿔줌으로써 시간 초과를 해결했던 경험은 없었기 때문에 이 문제를 통해서 시간 복잡도를 살짝 더 줄일 수 있는 인사이트를 얻었다.