시간복잡도 질문드립니다.

Question

int mySolution ( String jewels , String stones ) { int count = 0 ; for ( char jewel : jewels.toCharArray ()) { for ( char stone : stones.toCharArray ()) { if ( jewel == stone ) { count ++ ; } } } return count ; } 제가 작성한 코드입니다. 쥬얼리 같은경우 유니크하다 했으므로 중복된 자료가 없기 때문에 set자료구조에 굳이 담을 필요가 있을까 생각해서 이런식으로 코드를 짰는데요 시간복잡도상 강사님과 같은 방식이 더 효율적인게 잘 이해가 되질 않습니다. 이중포문인 것은 알지만 자료구조에 담는시간 및 재확인 시간도 있기 때문에 시간상 제가짠 코드가 더 괜찮지 않을까란 의문이듭니다. 어떻게 이해하면 좋을까요?

pushupman · Answer

고성빈님 , 안녕하세요 ~~~ 질문 주셔서 감사합니다. 시간복잡도를 물어 보셨는데요. 시간복잡도는 면접에서도 서로에 생각을 물어보면서 답하고 개발한 소스코드에 대해서 얼마나 빠르게 메모리를 적게 쓰면서 해결할 수 있는지 물어보죠.. 제 소스 코드는 로그가 2 + 7개가 찍힙니다. for문을 각 각 두번 돌리죠, 아래처럼 그래서 시간복잡도는 O(J.length + S.length) O(M+N)이고 결국 M=1000만개, N=1000만개를 돌려도 2천만개니까  O(N)으로 보시면됩니다.  이해하시겠죠?? 고성빈님 소스는  14개가 찍힙니다(아래그림). 이중 for문이지만 jewel과 stone의 length가 다르므로 O(M*N) 이죠 ,  O(J.length * S.length)  for문을 두번돌리면 역쉬 좋지는 않죠? 제가 한 방법처럼 for문 각각 한번씩 돌리면 O(N)이 되니까  제가 한 방법으로  하시는게 낫습니다.