[BOJ] 6159 코스튬 파티

문제

www.acmicpc.net/problem/6159

6159번: 코스튬 파티

풀이

1) 시간 복잡도 비효율적 코드(이중 For문)

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

public class Main {
	static int max = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N,S,size[], cnt=0;
        boolean[] chk;
        //입력
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        size = new int[N];
        
        for(int i=0;i<N;i++)
        	size[i] = Integer.parseInt(br.readLine());
        
        
        //계산
        for(int i=0;i<N;i++) {
        	for(int j=0;j<N;j++) {
        		if(i!=j && size[i]+size[j]<=S) {
        			cnt++;
        		}
        	}
        }
        System.out.println(cnt/2);
    }
} 

 

2) 효율적인 코드(Two Pointer)

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

public class Main {
   
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        //선언 및 입력
        int N,S,cows[],cnt=0;
        int end=0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        cows = new int[N];
        
        for(int i=0;i<N;i++)
        	cows[i] = Integer.parseInt(br.readLine());
        
        //계산
        Arrays.sort(cows);
        for(int start = 0;start<N-1;start++) {
        	end = start+1;
        	if(cows[start]>=S)
        		break;
        	while(end <N && cows[start]+cows[end]<=S) {
        		cnt++;
        		end++;
        	}
        }
        
        System.out.println(cnt);
    }
}