BOJ_1940 : 주몽

👉 문제링크

1940번: 주몽

---

---

🔸 문제 분석 🔸

• n개의 수를 입력받고, 그 중에 2개의 합이 m이 되는 경우의 수를 출력한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        int arr[] = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int answer = 0;
        for (int i = 0; i < n - 1; i++){
            for (int j = i+1; j < n; j++){
                if (arr[i] + arr[j] == m)
                    answer++;
            }
        }
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• n, m 과 n개의 숫자를 입력받아 배열에 저장하고, 이중 반복문으로 쌍의 합이 m이 되는지 확인한다.

 

🔸 다른 풀이 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int arr[] = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr);

        int answer = 0;
        int i = 0;
        int j = n - 1;
        while(i < j){
            if (arr[i] + arr[j] < m) i++;
            else if (arr[i] + arr[j] > m) j--;
            else {
                answer++;
                i++;
                j--;
            }
        }
        System.out.println(answer);
        br.close();
    }
}

• 투 포인터로 풀기위해 입력받은 배열을 정렬한다.
• i는 맨 처음 인덱스, j는 맨 마지막 엔덱스를 가리키고 합이 m이 되는지 확인한다.
  • 합 < m 이면, i를 1증가시킨다. (작은 쪽을 키움으로서 합을 조금씩 증가시킴)
  • 합 > m 이면, j를 1감소시킨다. (큰 쪽을 줄임으로서 합을 조금씩 감소시킴)
  • 합 == m 이면, i를 증가, j를 감소 시킨다. (바로 다음 쌍을 확인함)

---

🔸 end 🔸

• 브루트 포스식으로 이중 반복문을 사용해 문제를 풀었는데, 정렬 후 투포인터를 쓰는게 시간 복잡도가 절반까지 내려갔다.