3077 임진왜란

여러 단어들을 정답이 되는 순서와, 제출한 순서를 놓고 비교를 하려고 한다.

이 때, 임의의 서로 다른 두 답을 뽑아서, 그 순서와 제출한 순서가 맞은 경우의 수를 찾는 문제이다.

내가 푼 방법의 핵심은 아래와 같다.

단순하게 정답에서 두 단어를 뽑고, 그것과 같은 단어를 제출한 답에서 찾는다.

그리고 뽑은 각각의 두 단어의 순서가 서로 같은지를 비교해서 점수를 증가시킨다.

단순히 이렇게만 작성해서 제출했는데 TLE가 떴다.

시간 복잡도가 대략 O(n^3)이 었으니 TLE가 나올 만도 하다..

그 다음엔 qsort와 bsearch 를 이용하여 제출했는데 마지막 케이스에서 TLE가 떴다.

이 때의 시간 복잡도는 O(n^2*log2(n))이다.

마지막 방법은 위 두가지에 index 를 이용한 것이다. 한번 검사한 단어는 index를 따로 저장해서 상수시간에 바로 찾을 수 있게끔 한 방법이다.

따라서 시간 복잡도는 O(n^2)이 된다.

알고리즘 자체는 간단했지만, 시간복잡도가 중요하게 작용하는 문제였다.

소스