인프런 커뮤니티 질문&답변
작성한 질문수
모든 아나그램 찾기에서 시간복잡도
작성
·
41
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
강사님 안녕하세요!
모든 아나그램 찾기 문제에서 compareMaps에 for문이 있어서 해당 문제 시간복잡도가 O(N*M)이 되지 않나요? 그럼 결국 이중for문의 시간복잡도와 같아지는건 아닌지 궁금합니다~!
답변 1
0
안녕하세요, 인프런 AI 인턴입니다. 은우님.
모든 아나그램 찾기 문제에서의 시간복잡도에 대해 궁금해하셨네요. 이 문제에서 compareMaps 함수가 호출될 때마다 내부에서 반복문을 사용하면, 해당 부분은 일반적으로 O(N*M) 시간복잡도를 가질 수 있습니다. 즉, 각 슬라이딩 윈도우의 상태를 비교할 때마다 전체 문자를 다 비교하게 되면, 이중 for문의 시간복잡도와 비슷하게 됩니다.
다만, 효율적인 해결책은 슬라이딩 윈도우와 해시맵을 함께 활용하여 O(N) 시간복잡도로 문제를 풀 수 있습니다. 관련하여 강사님께서도 O(N) 복잡도로 문제를 풀 수 있도록 개선된 방법을 언급하셨습니다. 제가 유사한 질문이 있던 게시물들을 찾아보았습니다. 강사님의 코드에서는 슬라이딩 윈도우와 해시맵을 이용한 기법으로 성능을 개선하셨습니다.
유사한 질문과 답변 링크를 아래에 첨부하니 참조해 보세요:
각각의 답변에서 O(N) 복잡도로 문제를 해결하는 방법을 제시하고 있습니다. 이는 비교 및 제거할 문자가 지속적으로 관리되어 효율적인 처리가 가능하게 하는 코드로 설명되고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.