백준 JAVA 1940 주몽

https://www.acmicpc.net/problem/1940

1940번: 주몽

 

먼저 풀었던 방법은 이중 for문으로 푸는 것이었다.

배열중에 2개를 선택해서 m 과 같은 값을 만드는 것이었기 때문이다.

 

이중 for문으로 해도 정답은 통과했지만, 지금은 내가 투포인터 연습문제를 풀고 있기 때문에, 다시 고민했다.

오름차순으로 배열을 정렬하고, 앞에서부터 더하게 되면 이중for문이랑 다를게 없었다.

[ 1, 2 , 3 ,4 ,5 ,6 ] 일 때 1 + 2 / 1 + 3 / 1+ 4 ...

 

그래서 첫째값 + 마지막값으로 줄여나가는식으로 적용했다.

[ 1, 2 , 3 ,4 ,5 ,6 ] 일 때 1 + 6 / 1 +5 ..

 

이중 for문

package BAEKJOON.Silver.Ⅳ;

import java.util.Scanner;

public class NO1940 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //재료개수
        int m = sc.nextInt(); //갑옷을 만드는데 필요한 수
        int [] arr = new int [n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int count = 0;

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

 

투 포인터 적용

package BAEKJOON.Silver.Ⅳ;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 시간 제한   메모리 제한 제출 정답 맞힌 사람  정답 비율
 * 2 초 128 MB 8423   4028   3193   47.536%
 */
public class NO1940_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int s = 0;
        int e = n-1;
        int count = 0;
        Arrays.sort(arr);

        while (s < e) {
            if (arr[s] + arr[e] == m) {
                count++;
                s++;
                e--;
            } else if (arr[s] + arr[e] < m) {
                s++;
            } else if (arr[s] + arr[e] > m) {
                e--;
            }
        }
        System.out.println(count);
    }
}