5-H 질문있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

5-H

작성

269

수정됨

	while(e<n){
		if(cnt[a[e]]==0){
			cnt[a[e]]++;
			e++;
		}
		else{
			ret+=(e-s);
			cnt[a[s]]--;  
			s++;
		}
	}

강사님 안녕하세요?

else문에서 cnt[a[s]]-- 대신 cnt[a[e]]--로 하면 틀리는 이유를 모르겠습니다. 어차피 a[s]랑 a[e]는 똑같은 값이어서 어떤 것을 줄여도 맞아야하는거 아닌가요?

http://boj.kr/b07dba8700854c70b5f4031fbd5239c1

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 kkh님ㅎㅎ

nt[a[s]]-- 대신 cnt[a[e]]--로 하면 틀리는 이유를 모르겠습니다. 어차피 a[s]랑 a[e]는 똑같은 값이어서 어떤 것을 줄여도 맞아야하는거 아닌가요?

>> 일단 e는 오른쪽, s는 왼쪽의 값을 뜻합니다.

이 e와 s의 흐름은 다음과 같으며 이 때문에 a[s]랑 a[e]는 매번 똑같은 값이 아닙니다.

배열을 순회하면서, 현재 요소 a[e]가 이전에 등장하지 않았다면 (cnt[a[e]]가 0이라면), cnt[a[e]]를 증가시키고 e를 1 증가시킵니다.
만약 현재 요소가 이전에 이미 등장했다면 (cnt[a[e]]가 0이 아니라면), 현재 부분 배열의 길이(e - s)만큼 ret에 더하고, 시작 지점을 나타내는 s를 증가시키며, cnt[a[s]]를 감소시킵니다. 이는 중복을 제거하고 새로운 부분 배열의 시작점을 조정하는 과정이 됩니다.

예를 들어 다음과 같은 상황의 경우

1 2 3 1 1

이 상황에서는 e와 s는 같죠?

그러나.

1 2 3 1 1

이 상황에서는 같지 않게 됩니다.

이 때문에 메번 a[s]랑 a[e]는 똑같은 값이 될 수 없습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

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

질문하신 5-H: 13144 List of Unique Numbers 문제에서 cnt 배열의 역할과 e와 s 인덱스의 쓰임에 대해 혼동이 있으신 것 같습니다. cnt 배열은 각 숫자가 현재 구간에 몇 번 등장했는지 기록하는 역할을 합니다. e는 현재 구간의 끝을, s는 시작을 나타냅니다.

따라서, else블록에서 cnt[a[e]]--를 수행하면 아직 구간에 포함되지도 않은 (즉, 카운트되지도 않은) 끝 숫자의 등장 횟수를 감소시키려 하게 되어 로직이 잘못되며, 결과적으로 정확한 계산을 할 수 없게 됩니다. a[s]와 a[e]가 같은 값을 가지는 순간은 e가 새로운 값을 더해줄 때만 발생하며, 이 경우에는 a[s]는 이미 카운트되어 있고 a[e]는 카운트되지 않았으므로 서로 다르게 처리해야 합니다.

해당 질문에 대한 유사한 상황을 설명한 지식공유자의 답변을 아래에서 확인하실 수 있습니다. 이 답변은 다른 질문자의 코드에 대한 구체적인 피드백과 설명을 포함하고 있습니다.

5-H: 13144 답(ret) 관련 문의
- 지식공유자님이 구체적인 코드 설명과 예시를 들어 문제점과 개념 이해를 돕는 답변을 제공했습니다.

위 링크에 제공된 상황이 정확히 일치하지 않을 수도 있으므로, 이해가 안 가거나 추가 질문이 있으시다면, 해당 강의의 질문&답변 섹션에 질문을 남겨주시기 바랍니다. 강의 지식공유자께서 더욱 상세하고 직접적인 답변을 제공해 드릴 것입니다.

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

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

5-H 질문있습니다.