sort 연산 회고

이번 문제 또한 복잡도에 관한 문제였다. (복잡도시치...)

이번 문제는 2개의 숫자로 이뤄진 문자열에서 공통을 찾아내는 것이였다. 그리고 찾아낸 숫자로 만드는 가장 큰수를 알아 내는 것이다.
문제만 보면 크게 어려움이 없지만 복잡도에서 문제가 발생했다.

해법

1. X in Y
   말 그대로 2개의 문자열이니까 둘 중에 작은 문자를 찾아 반복문을 돌면서
   Y에 있는지 확인하는 것이다. 하면서도 이건 복잡도에 걸리겠구나 했고 역시나 복잡도에서 문제가 발생했다. len(X) * len(Y)번 정도 실행하니까 최대 300백만개의 문자열이 주어지는 조건에서는 올바르지 못하다.

2. pop()
   이번에는 pop을 이용했다 먼저 문자열을 오름차순sort하고 (n log n 2번)
   2문자열에서 1개씩 빼서 둘이 같다면 결과에 추가, 둘이 다르다면 큰 수를 가진쪽만 다시 pop해서 다시 비교하는 방식으로 했다. 이 방식은 처음 sort할때 n log n 그리고 서로 비교할때 최대 2n이 발생한다. 하지만 이것 또한 시간복잡도에서 걸렸다. 알고보니 굳이 문자열을 list로 나누고 join으로 합치는 과정에서 시간복잡도를 더 써버렸고 문제가 발생한것이다 이를 해결해서 해결했다.

3. 모니터 이용하기
   물론 해결했지만 더 좋은 방법이 있을 것 같아 찾아보니 모니터를 할용한 방법이 있었다. 두 문자열을 처음부터 확인하며 숫자를 확인해 모니터에 표시한다(10개의 리스트 각 index는 숫자 value는 갯수를 의미한다)
   그 후 각 문자열에 대한 모니터를 비교해서 겹치는 만큼 꺼낸다. 그걸 통해서 정답을 만든다. 이렇게 풀면 2n으로 문제를 해결한다.
   ※또한 이 방법이 좋았던 이유는 이 방법으로는 문자열이 몇 개가 주어지더라도 간단하게 해결할 수 있다.