5-B

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요! 제가 처음 문제를 읽고 접근했던 방법이 substr이였습니다. 구현을 하면서도 substr의 시간복잡도 때문에 최악의 경우에는 O(N^2)이 될거같았지만, 일단 로직을 구현했고 결과적으로 코딩살구클럽에서도 통과를 했습니다. 왜 통과를 했는지와 이렇게 구현해도 되는지 여쭤보고싶어 문의드립니다!

큰돌 · Answer

안녕하세요ㅎㅎ 이문제는 사실 O(NM) 시간복잡도로 풀어야하는 문제입니다. 이렇게 구현하시면 안됩니다 ㅠ 제 해설코드 참고하셔서 다시 풀어주세욤ㅎㅎ 코살의 채점서버는 테케를 기반으로 다 통과하기까지는 구현했지만 아직 시간초과에 대한 부분이 미흡해서 통과하는 거 같습니다 이부분은 개선할 예정입니다 감사합니다

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 기존의 접근 방식을 확인해보니, substr의 시간 복잡도로 인해 최악의 경우 O(N^2)이 발생할 수 있다는 점을 염두에 두셨군요. 이 방법이 통과하게 된 이유는 실제 입력 데이터가 최악의 경우에 해당하지 않거나, 문제 자체가 이러한 시간 복잡도를 필요로 하지 않기 때문일 수 있습니다. 하지만, 일반적으로 substr을 사용하여 반복적으로 문자열 연산을 수행할 때, 실제로 입력이 최대 크기로 주어진다면 O(N^2)의 시간 복잡도가 문제가 될 수 있습니다. 이는 경쟁 코딩 및 코딩테스트에서는 주의해야 할 점입니다. 이를 해결하기 위해서는 더 효율적인 방법으로, 예를 들어 two-pointer 기법이나 스택을 활용하여 문자열을 한번만 순회하면서 문제를 해결하는 것도 고려할 수 있습니다. 이런 방식은 O(N)으로 구현할 수 있습니다. 유사한 상황에 대한 기존의 답변을 참고 하여, substr과 같은 함수를 반복적으로 사용하는 대신 효율적인 알고리즘을 고려하는 것이 좋습니다. &mdash;start of instructor answer&mdash; 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다. &mdash;end of instructor&rsquo;s answer&mdash;