[백준] 1940번: 주몽(수학, 정렬)

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

1940번: 주몽

코드

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 bf = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(bf.readLine());
		int M = Integer.parseInt(bf.readLine());
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(bf.readLine());
		for(int i=0; i<arr.length; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		int count = 0;
		for(int i=0; i<arr.length-1; i++) {
			for(int j=i+1; j<arr.length; j++) {
				if(arr[i] + arr[j] == M) {
					count ++;
					break;
				}
			}
		}
		
		System.out.println(count);
		bf.close();
	}

}

풀이

시간 제한이 2초에 N의 범위가 15,000 이어서 O(N^2) 완전탐색으로 모든 경우의 수를 구해서 해결했다.

for문의 범위만 신경써주고, 모든 배열 값들을 확인하면서 두 개의 재료 고유번호 합이 M일 경우 count ++ 해준다.

 

 

 

 

 

다른 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));

		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 i=0, j=arr.length-1;
		int cnt = 0;
		while(i < j) {
			if(arr[i] + arr[j] == M) {
				i++;
				j--;
				cnt++;
			}
			else {
				if(arr[i] + arr[j] > M) {
					j--;
				}
				else {
					i++;
				}
			}
		}
		
		bw.write(String.valueOf(cnt));
		
		br.close();
		bw.close();
	}
}

정렬을 하고, 가장 작은 값과 가장 큰 값의 합을 구해서 M과 비교를 하며 해결할 수도 있다.

두 개의 합이 M과 같으면 i 값을 증가 , j 값을 감소(이분 탐색의 느낌)시키고,

두 개의 합이 M보다 클경우 -> 합을 줄여야 하므로 큰값을 감소(j--)

두 개의 합이 M보다 작을경우 -> 합을 증가시켜야 하므로 작은값을 증가(i++) 시킨다.