숫자로 되어 있는 문자열 정렬.
260624
-> 시간복잡도를 생각하면 정말 쉽게 풀 수 있따.
문자열의 sort는 nLogN * length
이므로 4억이 발생하므로, 다음에 문자열 비교를 할 때 반드시 순차 탐색으로 끝내야겠다는 마음가짐을 가져야 한다.
- 여기서 이진탐색이라던지, 다른 거를 가지고 와서 사용하면 시간복잡도 초과임을 알고 있어야 함.
핵심
- 아이디어 : 데이터들이 사전순으로 정렬되어 있기 때문에 인접한 인덱스끼리의 접두어 가 존해할 수 있다.
["119", "97674223", "1195524421"] 정렬하면
["119", "1195524421","97674223"] 이렇게 된다.
결과
- 시간복잡도 생각하지 않고, 그냥 접근하려고 하면,
sort 한 다음에 set을 사용하는 경우가 발생하는데, 이렇게 되면
위의 sort한 4억번에다가 추가로 set 을 사용하는 비용까지 추가되므로, 반드시 효율성 3번에서 틀린다.
260624=> 아래 내용은 틀리는 내용이고, 이렇게 하면 안됨.
-
문자열 정렬은 기존 sort보다 더 발생한다.
-> nLogN * 문자열 길이
-
효율성 3번만 계속 틀리는 코드
-> 아래의 for문에서의 insert는 좋지 않다 함.
🔥🔥🔥