[알고리즘] 백준 1940번 주몽의 명령 (with Java)

 

* 해당 문제는 투포인터 알고리즘을 사용하는 문제이다.*

투 포인터 알고리즘은 배열이나 리스트에서 특정 조건을 만족하는 부분을 효율적으로 찾기 위해 두 개의 포인터를 사용하는 기법이다. 주로 정렬된 배열에서 유용하며, 시간 복잡도를 줄일 수 있는 장점이 있다. 

 

 

 

오답

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

//투포인터관련
public class P1940_주몽 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] num = new int[N];//N만큼 배열 만들기
        for (int i = 0; i < N; i++) {
            num[i]=Integer.parseInt(sc.nextInt());
        }
        Arrays.sort(num);
        int count = 0;
        int sum = 0;
        int startPoint=num[0];
        int endPoint=num[0];

        for (int i = 0; i < N-1; i++) {
            if (sum==M){
                count++;
                endPoint=num[i+1];
                sum+=endPoint;
            }else if (sum>M){
                sum-=startPoint;
                startPoint=num[i+1];
            }else if (sum<M){
                endPoint=num[i+1];
                sum+=endPoint;
            }
        }


    }
}

 📖오답 사유

• 이해의 오류
  • startPoint와 endPoint가 같아도 된다고 생각하였다.
    • 실제: 서로다른 두 재료여야 함
  • startPoint와 endPoint 사이의 모든 수를 더한다고 생각하였다.
    • 실제: 2가지만 사용
  • sum==N일때의 변수 변화
    • 주몽 문제: 두 개의 재료로 구성된 쌍을 찾는 문제로, 두 포인터를 모두 이동시켜 새로운 쌍을 찾는다.
    • (헷갈렸던 부분)연속된 자연수의 합 문제: 연속된 자연수의 구간을 확장하는 문제로, 하나의 포인터만 이동시켜 연속된 구간을 확장→새로운 합을 만든다.

---

✅ 풀이

예제 입력 값 해석

1. 재료의 개수 N, 갑옷을 만드는데 필요한 수 M 받기
2. M → 오름차순 정렬
   • Arrays.sort(변수)
3. 변수 선언 : count, sum(start, endPoint 수의 합), startPoint, endPoint
4. 투포인터 알고리즘 적용
   1. M=sum→ endPoint--, startPoint++, count(정답개수)++
   2. M>sum→ startPoint++
   3. M<sum→ endPoint--

정답 코드

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

//투포인터관련
public class P1940_주몽 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] num = new int[N];//N만큼 배열 만들기
        for (int i = 0; i < N; i++) {
            num[i]=sc.nextInt();
        }
        Arrays.sort(num);

        int count = 0;
        int startPoint=0;
        int endPoint=N-1;

        while(startPoint<endPoint){
            int sum=num[startPoint]+num[endPoint];
            if (sum==M){
                count++;
                startPoint++;
                endPoint--;
            }else if (sum>M){
                endPoint--;
            }else{//sum<M
                startPoint++;
            }
        }
            
        System.out.println(count);

    }
}