투포인터 슬라이딩 방식이 아니면 어떻게 구현해야 하나요?

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

기존에 남겨주신 코드들 보면 합계를 이용해서 rt를 하나 증가시키고 lt도 합계에 따라 증가시키는 방식으로 이해습니다.

궁금한 부분이 lt에서 rt까지의 합이 아닌 lt와 rt 두 포인터의 합의 최소값으로 구현하려고 하니까 구현 방식이 greedy와 다를게 없어져서 어떻게 구현해야할지 잘 모르겠는데 어떻게 해야하나요?

현재 아래와 스니펫처럼 어떻게든 구현해보려고 하는데 구현하신 방식대로 하려고 하니 잘 풀리지 않습니다.

for(int rt = 1; rt < arr.length; rt++){

    sum = arr[lt] + arr[rt];

    if(Math.abs(sum) < gap){
        gap = Math.abs(sum);
        answer[0] = arr[lt];
        answer[1] = arr[rt];
    }

    while(lt + 1 < rt){
        lt++;
        sum = arr[lt] + arr[rt];
        if(Math.abs(sum) < gap){
            gap = Math.abs(sum);
            answer[0] = arr[lt];
            answer[1] = arr[rt];
        }
    }
    lt++;
}

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

lt와 rt를 이용하는 투 포인터 방식은 주로 정렬된 배열에서 범위의 합이나 최대, 최소값 등을 효율적으로 찾을 때 사용됩니다. lt와 rt의 합 최소값을 구하려면, 배열이 미리 정렬되어 있다는 가정하에 양 끝점에서 시작해서 조건에 따라 포인터를 이동하며 값을 갱신하게 됩니다.

제시한 코드 스니펫을 보면, 두 요소의 합이 최소가 되는 값을 찾으려고 하신 것으로 보입니다. 그런데 코드 중 while (lt + 1 < rt) 루프는 lt 포인터를 rt 방향으로만 이동시키는데, 이는 배열 전체를 탐색하는 것이 아니기 때문에 더 좋은 해결책을 놓칠 수 있습니다.

lt와 rt의 합의 최소값을 찾는 문제에서는 보통 배열을 정렬하여, lt를 시작점, rt를 끝점으로 두고 시작합니다. sum이 목표값보다 크면 rt를 감소시키고, 작으면 lt를 증가시켜가면서 최소값을 찾습니다. 이러한 방식으로 두 포인터 간의 합이 가장 최소가 되는 쌍을 찾을 수 있습니다.

다음은 해당 방식으로 작성된 코드 일부 예시입니다. 이는 전체 문제에 대한 답을 제공하는 것이 아니고 로직을 이해하시는 데 도움을 드리기 위한 예시 코드이며, 실제 문제에 맞게 조건을 추가하셔야 합니다.

Arrays.sort(arr); // 배열을 먼저 정렬
int lt = 0, rt = arr.length - 1;
int gap = Integer.MAX_VALUE; // 최소값 갱신을 위한 초기 큰 값 설정

while (lt < rt) {
    int sum = arr[lt] + arr[rt];
    
    // 현재 합계와 최소 갭 비교
    if (Math.abs(sum) < gap) {
        gap = Math.abs(sum);
        answer[0] = arr[lt];
        answer[1] = arr[rt];
    }
    
    // 합계 조정을 위한 포인터 이동
    if (sum > 0) rt--;
    else if (sum < 0) lt++;
    else break; // 합계가 0이면 최소값이므로 탐색 종료
}

실제 문제에서는 gap(최소값)을 설정하는 목표나, 구하려는 합의 조건 등이 더 명확할 것입니다. 따라서 그 조건에 맞춰 lt와 rt의 이동 규칙을 설정하시면 됩니다.

질문하신 내용에 대한 답변이 명확하지 않거나 추가로 궁금한 점이 있는 경우 자세한 사항을 문의하시거나 인프런 커뮤니티의 경험많은 다른 학습자들과 지식을 나누는 것도 좋을 것 같습니다.

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