씨름선수( Greedy or 조합 )

 

전략 1. 2중 for문 O(n^2) : time limit
전략 2. combination 사용하여 비교. OK
전략 3. Greedy algorithm

//키순으로 내림차순 정렬하면 키를 고려할 필요가 없어진다.

//첫번째 인자는 키가 가장 크기 때문에 언제나 포함.
//따라서 다음인자의 w가 max보다 낮으면, 탈락. (키와 몸무게 모두 낮게 되는 조건을 만족)
//따라서 max가 업데이트 되는 순간을 카운트하면 살아남는 인원을 구할 수 있다. (직전값들 보다 w가 크다)

 

 

조합을 이용한 풀이.

package com.test.testapplication;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {

	static int m, n, answer=Integer.MAX_VALUE;
	static int COMPARE = 2;
	//전략 1. 2중 for문 O(n^2) : time limit
	//전략 2. combination 사용하여 비교. OK
	//전략 3. Greedy algorithm
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		
		n = in.nextInt();
		
		int []h = new int[n];
		int []w = new int[n];
		int []combi = new int [COMPARE];//1:1 compare
		int []ch = new int[n];
		for ( int i = 0 ; i < n ; ++i) {
			h[i] = in.nextInt();
			w[i] = in.nextInt();
		}
		
		//start index from  0
		M.D(0, 0, combi, h, w , ch);
		int cnt=0;
		for ( int v : ch)
			if( v == 1) cnt++;
		
		answer = n - cnt;
		System.out.println(answer);
		
	}

	private void D(int level, int start, int [] combi, int[] h, int[] w, int[] ch) {
		
		//비교 대상의 범위
		if ( level == COMPARE) {
			//combi's index indicate selected person
			int a = combi[0];
			int b = combi[1];
			//System.out.println(String.format("%d %d", a,b));
			if ( h[a] < h[b] && w[a] < w[b]) {
				//System.out.println(String.format("%d %d [ch==1]", a,b));
				ch[a] = 1;
			} else if ( h[a] > h[b] && w[a] > w[b]) {
				//System.out.println(String.format("%d %d [ch==1]", a,b));
				ch[b] = 1;
			} else ;
			
			
		} else {			
			//for range : 선수의 범위
			for ( int i = start ; i < n ; i ++ ) {
				combi[level] = i;
				D ( level + 1 , i +1, combi, h, w, ch );
			}
			
		}
		
	}


	


}

ex)
input
5
172 67
183 65
180 70
170 72

output
3
181 60

 

내림 차순 정렬 후, max값 찾기

package com.test.testapplication;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {

	static int m, n, answer = Integer.MAX_VALUE;
	static int COMPARE = 2;

	// 전략 1. 2중 for문 O(n^2) : time limit
	// 전략 2. combination 사용하여 비교. OK
	// 전략 3. Greedy algorithm
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);

		n = in.nextInt();
		Person[] pArr = new Person[n];
		
		for (int i = 0; i < n; ++i) {
			int h = in.nextInt();
			int w = in.nextInt();
			pArr[i] = M.new Person(h, w);
		}
		//키순으로 내림차순 정렬하면 키를 고려할 필요가 없어진다.
		Arrays.sort(pArr);
		
		int cnt = 0;
		int max = -1;
		for (Person p : pArr) {
			//첫번째 인자는 키가 가장 크기 때문에 언제나 포함.
			//다음인자(키가 이전보다 작은) 가 max보다 w가 낮으면, 탈락.(키와 몸무게 모두 낮음)
			//따라서 max가 업데이트 되는 순간만 체크하면 살아남는 인원을 구할 수 있다.
			if ( max < p.w) {
				cnt++;
				max = Math.max(max, p.w);
			}			
		}
		answer = cnt;
		System.out.println(answer);

	}

	class Person implements Comparable<Person> {
		int h, w;

		Person(int h, int w) {
			this.h = h;
			this.w = w;
		}

		@Override
		public int compareTo(Person o) {
			return o.h-this.h;
		}
	}

}