문제를 어떻게 풀어야할지 고민했다
만약에 1,2,3,4,5 가 있다면 다음과 같은 경우들이 있다
그리고 슬라이딩 윈도우로 풀어야 겠다고 생각했는데
아래와 같은 조합들을 슬라이딩 윈도우로 만들 수 가 없었다
그래서 고민하다가 풀이를 보아도 이해가 되지 않았는데 조합을 만드는 순서를 달리 생각해보니 할 수있겠다는 생각이 든다
아래와 같은 순서로 조합을 구하면 된다.
1~5까지 인덱스로 보자면 l=0 r=4 l부터r까지 중복숫자없었다면 l 을 증가시키면서 ans 에 r-l+1 개수를 더하면 된다
원소가 {1, 2, 3, 1, 3} 인경우를 보자 솔직히 잘 이해가 안되긴 한다
나는 l 을 고정시키고 r만 변화하면서 만들 수 있는 수열을 구하면 된다라고 정리를 해보았다
초기값 l=0, r=0
r증가하면서 중복된 값이 나오면 r=3 에 있다 중복되기 전의 값 r=2
l=0, r=2 이면 ans+=3 (l-r+1)
중복된 값이 있으므로 l++
l=1, r=3 이면 ans+=3
l=2, r=4 이면 ans+=3
l=3, r=4 이면 ans+=2
l=4, r=4 이면 ans+=1
색상은 {1,2,3} 으로 만들 수 있는 조합 6가지
{2,3,1} 으로 만둘 수 있는 조합 단 중복되는것은 제외되어서 2가지
{3,1,2} 으로 만들 수 있는 조합 단 중복되는것은 제외되어서 1가지
{1,2} 으로 만들 수 있는 조합 3 가지 을 색상으로 구분 해보았다
게임개발자 백엔드개발자