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

안녕하세요 유태님 ㅎㅎ

	for (ll i = 0; i < N; i++)
	{
		cnt++;
		for (ll j = i + 1; j < N; j++)

이 코드의 시간복잡도는 O(N^2)이고 N의 시간복잡도는 10만이라 100억정도의 시간복잡도를 가지는 코드입니다.

시간복잡도를 개선해주셔야 합니다.

		for (ll j = i + 1; j < N; j++)
		{
			if (arr[j] != arr[i]) cnt++;

그리고 이 로직만으로는 1 2 2 와 같은 경우의 수를 체크하지 못합니다.

{1, 2}

{1, 2, 2}

의 경우의 수 다 카운트 되지 않을까요?

감사합니다.

안녕하세요, 인프런 AI 인턴입니다.

한유태님, 완전탐색을 이용하여 문제를 해결하려 하였으나 올바른 결과가 나오지 않아서 고민이시군요. 완전탐색은 모든 가능한 경우를 고려하여 답을 찾는 방법으로, 특정 유형의 문제에서는 효율적이지 않을 수 있습니다.

문제를 해결하기 위해 다음 몇 가지를 고려해 보시면 좋겠습니다:

1. 시간 복잡도: 완전탐색은 일반적으로 비효율적이기 때문에, 입력 크기에 비해 시간이 많이 걸릴 수 있습니다. 문제에서 요구하는 시간 내에 수행 가능한지 확인해 보세요.

2. 잘못된 구현: 코드에서 인덱스 범위 또는 조건문에서 실수가 있을 수 있습니다. 예를 들어, 배열 인덱스 범위를 초과하거나 잘못된 조건으로 인해 논리적 오류가 발생할 수 있습니다.

3. 다른 접근법: 만약 완전탐색이 비효율적이라면, 다른 알고리즘적 접근이나 최적화가 필요한지 고민해 보세요. 가능한 데이터 구조의 활용을 고려해 보세요.

이 문제와 유사한 문제나 다른 학습자의 토론을 참고하고 싶으시면, 약간의 수정 또는 최적화 기법을 공유한 게시물을 참고하시면 도움이 될 수 있습니다:
- 5-D 질문드립니다 :)

위의 질문에서 해결했던 방식이나 제안된 코드가 도움이 될 가능성이 큽니다. 해결책을 보완하여 적용해 보시기를 권장드립니다.

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