모든 아나그램 찾기에서 시간복잡도
98
작성한 질문수 3
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
강사님 안녕하세요!
모든 아나그램 찾기 문제에서 compareMaps에 for문이 있어서 해당 문제 시간복잡도가 O(N*M)이 되지 않나요? 그럼 결국 이중for문의 시간복잡도와 같아지는건 아닌지 궁금합니다~!
답변 1
0
안녕하세요, 인프런 AI 인턴입니다. 은우님.
모든 아나그램 찾기 문제에서의 시간복잡도에 대해 궁금해하셨네요. 이 문제에서 compareMaps 함수가 호출될 때마다 내부에서 반복문을 사용하면, 해당 부분은 일반적으로 O(N*M) 시간복잡도를 가질 수 있습니다. 즉, 각 슬라이딩 윈도우의 상태를 비교할 때마다 전체 문자를 다 비교하게 되면, 이중 for문의 시간복잡도와 비슷하게 됩니다.
다만, 효율적인 해결책은 슬라이딩 윈도우와 해시맵을 함께 활용하여 O(N) 시간복잡도로 문제를 풀 수 있습니다. 관련하여 강사님께서도 O(N) 복잡도로 문제를 풀 수 있도록 개선된 방법을 언급하셨습니다. 제가 유사한 질문이 있던 게시물들을 찾아보았습니다. 강사님의 코드에서는 슬라이딩 윈도우와 해시맵을 이용한 기법으로 성능을 개선하셨습니다.
유사한 질문과 답변 링크를 아래에 첨부하니 참조해 보세요:
각각의 답변에서 O(N) 복잡도로 문제를 해결하는 방법을 제시하고 있습니다. 이는 비교 및 제거할 문자가 지속적으로 관리되어 효율적인 처리가 가능하게 하는 코드로 설명되고 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
continue를 사용하는 이유
0
75
2
정렬 가능 여부 판단하기
0
62
2
알고리즘 학습법 관련해서 질문드립니다.
0
80
1
코드 리뷰 부탁드립니다!
0
88
1
indexOf를 사용해서 풀어보았습니다 !!
0
67
1
저는 이런식으로 구현 해보았습니다 !!
0
63
1
12,13,14 강의 소리만 나오고 검은 화면입니다
0
97
3
반복문 최소화하고 indexOf 사용해서 풀어봤습니다
0
61
1
영상 보기 전에 직접 풀어봤습니다.
0
71
1
섹션1의 17번문제 이 풀이로 풀어도 될까요?
0
133
2
정규표현식으로 처리해도 상관없나요 ?
0
119
2
3칸씩 건너뛸 수 있을 경우
0
124
2
강의에 대해 질문있습니다.
0
133
2
Object와 Set을 이용해 풀어봤습니다.
0
116
2
이렇게 해도 되나요?
0
102
2
선생님 중복 단어나 중복관련 문제들은 set을 이용하면 좋을것 같습니다.
0
144
2
이렇게 풀어도 괜찮을까요?
0
136
1
이렇게 풀어도 괜찮을까요?
0
112
1
코드리뷰 부탁드립니다.
0
129
1
for loop 탈출은 return 문으로 해도 되지 않나요?
0
129
1
투포인트알고리즘으로 풀어봤습니다.
0
138
0
코드 리뷰 부탁드립니다.
0
115
1
코드 맞게 작성한 거 아닌가여??
0
142
1
문드윽뀨
0
96
1