목표 합을 만드는 두 위치

위치 두 개를 고르면 값이 같아도 다른 선택이에요

앞 레슨에서는 중복값의 순위를 같게 취급했어요. 이번에는 값을 고른 위치가 선택의 식별자예요. {2,2,5}에서 합 7인 짝은 첫 2와 5, 둘째 2와 5 두 개예요.

i<j인 위치 두 개만 검사하면 같은 위치를 두 번 고르지 않고 (i,j)와 (j,i)를 중복으로 세지 않아요.

정렬 후에도 위치쌍 개수는 유지돼요

정렬은 원소를 다시 배치하지만 서로 다른 두 원소를 고르는 조합의 수를 바꾸지 않아요. 작은 값부터 순회할 때 고정된 첫 값에 더하는 두 번째 값은 점점 커져요.

첫 값이 2, 나머지가 3·6·8이고 목표가 8이면 합은 5→8→10이에요. 10 이후의 값이 더 커져도 목표 8로 돌아갈까요? 아니요. 다만 합이 맞았다고 바로 끝내면 뒤의 같은 값으로 만든 다른 위치쌍을 놓칠 수 있어요.

직접 풀어봐요

서로 다른 두 인덱스 i<j를 골라 values[i]+values[j]=target인 위치쌍의 개수를 반환해요. 같은 값을 가진 원소들도 서로 다른 인덱스면 각각 선택할 수 있어요. 같은 원소를 두 번 고를 수 없어요.

길이는 0100, 원소는 −10001000, target은 −2000~2000이에요. 길이 0 또는 1이면 답은 0이에요. 실행용 입력은 n, n개 원소, 마지막 줄 target이에요. 출력은 반환값이고 하네스가 입출력을 처리해요.

예시 1: values={1,3,5,7}, target=8 → 2. 1+7과 3+5 두 짝이에요. 예시 2: values={1,1,2,2}, target=3 → 4. 각 1마다 두 개의 2를 골라 네 위치쌍이에요.

4
1 3 5 7
8

2

4
1 1 2 2
3

4