N^2은 너무 크고 (100억), 이 사이에 있을 만한 거라면 NlogN, NsqrtN, Nlog^2N 정도가 있겠지만, N이나 NlogN까지는 고려할 수 있지만 그 이상은 알고리즘을 처음 하는 입장에서는 거의 볼 일이 없기 때문에 굳이 고려할 필요가 없습니다.

앗.. 딱 O(N)은 아니어용 ㅠ

입력이 10만개정도였을때 O(N^2) 이상으로 시간 걸리는 시간복잡도로는 안된다는 의미였습니다!

djm님 말씀대로 저런 시간복잡도들도 있어요.

뭐 예를들어서 N개 각각에 대해 직접 순회하며 찾으면 O(N^2)이고 (2중반복문으로 그냥 찾는다면)

만약 해당 데이터가 정렬된 데이터임을 알았다면, 각각에 대해(N) 이분탐색(logN)을 하면 O(NlogN)이고 그건 통과가 되겠죠.

이전 글에 O(N)이라 쓴건 해당 문제가 그걸로 가능했기 때문입니닭

시간복잡도로 구글링해서 한번 읽어보심 좋을듯합니다!

문제 풀기전에 대강 생각한게 되겠다 안되겠다 각을 잡을 수 있어서 좋더라구요.