백준(1940번, 주몽, 실버IV)

문제 내용

문제 내용

---

제출한 코드

import java.io.*;
import java.util.*;

public class 주몽의명령 {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            // 재료들의 고유번호를 입력받음
            int N = Integer.parseInt(br.readLine());
            int M = Integer.parseInt(br.readLine());

            // 입력받은 값들을  N 개의 숫자를 공백 단위로 나누어 배열에 저장
            int[] A = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                A[i] = Integer.parseInt(st.nextToken());
            }

            // 오름차순으로 정렬
            Arrays.sort(A);

            int i = 0; // 맨처음
            int j = N - 1; // 맨끝
            int count = 0; // 결과값

            // i가 j보다 작을 때까지 반복(끝 포인터)
            while (i < j) {
                int sum = A[i] + A[j];

                if (sum == M) { // 두 재료의 합이 목표치와 같은거 찾기
                    count++;
                    i++;
                    j--;
                } else if (sum < M) {
                    i++;
                } else {
                    j--;
                }
            }

            bw.write(count + "\n");

            bw.flush();
            bw.close();
            br.close();
        }
}

---

후기

이번 문제를 풀면서 투 포인터기법을 활용하는 방법과, 포인터를 언제 이동해야 하는지에 대한 개념을 확실하게 익힐 수 있었다. 처음에는 투 포인터를 적용하는 방식이 직관적으로 이해되지 않아, 어떤 상황에서 왼쪽 포인터를 증가시켜야 하는지, 오른쪽 포인터를 감소시켜야 하는지를 고민하는 데 시간이 걸렸다.

투포인터에 대한 개념, 어떨때 포인터를 이동시켜야하는지, 맨처음 포인터랑 끝 포인터를 설정하는 기준이 뭔지에 대한 개념이 헷갈려 아래의 첨부한 블로그의 내용을 참고했다

---

투포인터 개념

투 포인터 기법은 정렬된 배열에서 두 개의 포인터를 사용해 특정 조건을 만족하는 쌍을 찾는 방법이다

이 문제에서는 배열을 정렬한 후, 하나의 포인터는 배열의 맨 처음(i = 0), 다른 하나는 배열의 맨 끝(j = N-1)에서 시작하여 다음과 같이 움직인다.

1. A[i] + A[j] == M일때
두 수의 합이 정확히 목표 값이므로 카운트를 증가시키고, 양쪽 포인터를 이동한다

2. A[i] + A[j] < M일때
합을 더 크게 만들어야 하므로 작은 값(A[i])을 증가시키기 위해 i를 오른쪽으로 이동한다

3. A[i] + A[j] > M일때
합을 더 작게 만들어야 하므로 큰 값(A[j])을 줄이기 위해 j를 왼쪽으로 이동한다

 

모든 경우를 직접 계산하는 방식은 O(N²)의 시간복잡도를 가지지만, 배열이 정렬되어 있기 때문에 투 포인터를 활용하면 훨씬 효율적인 O(N) 시간 복잡도로 해결할 수 있다.

---

배열을 정렬해야하는 이유

투 포인터를 사용하려면 배열이 정렬되어 있어야 한다. 그래야 sum < M일 때, 작은 값을 증가시키는 것이 의미가 있고, sum > M일 때, 큰 값을 감소시키는 것도 의미가 있기 때문이다. 만약 정렬하지 않으면 A[i] + A[j]의 크기를 예측할 수 없기 때문에 포인터 이동 기준을 정해줄 수 없기때문에 반드시 배열을 정렬해줘야한다

 

 

 

참고한 자료

https://velog.io/@isohyeon/Java-%EB%B0%B1%EC%A4%80-1940-%EC%A3%BC%EB%AA%BD%EC%9D%98-%EB%AA%85%EB%A0%B9