[Baekjoon] 1940 - 주몽

📝 문제

 

 

🔑 풀이 과정

이 문제는 풀이방법을 두 가지 사용했다.

① 이중 for문을 사용한 풀이

N이 15,000이고 시간 제한이 2초라서 O(N^2)으로도 충분히 풀 수 있을거라 판단했다.

다만 여기서 갑옷을 만드는 재료들은 "고유한" 번호를 가지고 있다고 했으므로,

합이 M인 짝을 찾으면 break를 사용해서 안 쪽 반복문을 탈출한다.

 

② 정렬 + 투 포인터를 사용한 풀이

입력 받은 배열을 정렬 시켜준 뒤, 투 포인터를 사용한다.

 

---

위가 정렬 + 투 포인터 풀이 했을 때,

아래가 이중 for문을 사용했을 때,

인데 두 경우 다 제한시간 2초에 비해 충분한 시간이니 본인이 편한 쪽으로 쓰면 될 것 같다.

 

 

 

🔓 답안

① 이중 for문을 사용한 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //입력 받기
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        int M = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        //입력 종료

        int count = 0;
        for(int i = 0; i <= N-2; i++){
            for(int j = i+1; j < N; j++){
                if((arr[i] + arr[j]) == M){
                    count++;
                    break;
                }
            }
        }

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

    }

}

② 정렬 + 투 포인터를 사용한 풀이

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //입력 받기
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        int M = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        //입력 종료

        Arrays.sort(arr);

        int count = 0;
        int min = 0;
        int max = N-1;

        while(min < max){
            if((arr[min] + arr[max]) == M){
                count++;
                min++;
                max--;
            } else if((arr[min] + arr[max]) < M){
                min++;
            } else if((arr[min] + arr[max]) > M){
                max--;
            }
        }

        bw.write(count + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

🖤 알고리즘 분류

- 정렬

- 투 포인터