인프런 커뮤니티 질문&답변

작성한 질문수

정말 쉽게 풀어보는 코딩 테스트 top 기본 문제 (with 자바)

보석과 돌(Jewels And Stones)

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

작성

·

187

1

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자료구조에 굳이 담을 필요가 있을까 생각해서 이런식으로 코드를 짰는데요

시간복잡도상 강사님과 같은 방식이 더 효율적인게 잘 이해가 되질 않습니다.

이중포문인 것은 알지만 자료구조에 담는시간 및 재확인 시간도 있기 때문에 시간상 제가짠 코드가 더 괜찮지 않을까란 의문이듭니다.

어떻게 이해하면 좋을까요?

java 코테 준비 같이 해요!

답변 1

1

푸샵맨 코딩스터디

지식공유자

고성빈님 , 안녕하세요 ~~~

질문 주셔서 감사합니다.

시간복잡도를 물어 보셨는데요. 시간복잡도는 면접에서도 서로에 생각을 물어보면서

답하고 개발한 소스코드에 대해서 얼마나 빠르게 메모리를 적게 쓰면서 해결할 수 있는지 물어보죠..

제 소스 코드는 로그가 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)이 되니까 제가 한 방법으로

하시는게 낫습니다.

질문자

와 예시를 보니까 확 와닿네요. 다음부턴 잘이해가 안될 때 로그를 남겨서 다음부터는 확인해보겠습니다. 감사합니다!! ㅎㅎ

작성한 질문수