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

안녕하세요 명운님 ㅎㅎ

코드가 너무 좋네요 ㅎㅎ

저도 처음에 이코드보고 O(N)인데 통과하려나 했던 코드인데 제 생각에는 아마 이부분 때문에 통과하는 것 같습니다.

            ll c = find(v.begin(), v.end(), n) - v.begin();
            for (ll i = 0; i < c; i++) visited[v[i]] = 0;
            v.erase(v.begin(), v.begin() + c + 1);

계속해서 v에서 필요없는 부분을 지워주고 있기 때문에 해당 부분이 private TC에서 효율적으로 작동되어서 그런 것 같습니다.
그러나 이부분은 O(N)이 맞기 때문에 (find 때문에) 제 코드 기반 다른 방법도 숙지를 해두셔야 합니다.

간만에 보는 깔끔한 코드네요 ㅎㅎ

감사합니다.

안녕하세요, 인프런 AI 인턴입니다. 이명운님.

이명운님께서 사용하신 방식이 의도치 않게 주어진 입력 데이터의 특성이나 제한 조건과 잘 맞아떨어져 제출 시 정답으로 처리된 경우가 많은 알고리즘 문제 풀이에서 발생하곤 합니다.

문제 해결 시 왜 정답으로 처리되었는지 분석

1. 최악의 상황이 발생하지 않음: 백준과 같은 알고리즘 평가 사이트에서는 모든 가능한 입력이 주어지지 않는 한, 최악의 시간복잡도를 직접적으로 경험하는 경우는 드뭅니다. 따라서 O(N^2)과 같은 시간복잡도 알고리즘이 실제로 실행되는 도중 시간 제한을 통과할 수 있습니다.

2. 데이터의 특성: 주어진 문제 데이터가 특정 패턴을 가지고 있어서 생각보다 많은 부분이 효율적으로 처리되었을 가능성도 있습니다. 데이터의 특성이 특정 알고리즘의 비효율적인 부분을 피할 수 있습니다.

3. 부분적으로 효율적인 구현: ‘visiting’을 해제하는 부분을 포함해서 알고리즘의 나머지 부분이 평균 케이스에서는 매우 효율적으로 작동할 수 있습니다.

시간복잡도를 보다 정확히 개선할 수 있도록 ‘슬라이딩 윈도우’, ‘투 포인터’와 같은 방법론적 접근을 통해 해당 문제를 한 번 더 살펴보시면 좋은 연습이 될 것 같습니다.

아래 링크를 통해 보다 최적화된 방법을 찾아보길 추천드려요: 5-H 문제 최적화 풀이

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.