백준_1946 신입 사원(자바) / 그리디 알고리즘

시간 & 메모리 제한

문제

입력 & 출력

그리디 알고리즘을 이용한 풀이

package com.Back;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Back_1946 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int testCase = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for (int tc = 0; tc < testCase; tc++) {
			int N = Integer.parseInt(br.readLine());
			rank[] r = new rank[N];
			int min = Integer.MAX_VALUE;
			int ans = 0;
			for (int i = 0; i < N; i++) {
				st= new StringTokenizer(br.readLine());
				int first = Integer.parseInt(st.nextToken()); 
				int second = Integer.parseInt(st.nextToken()); 
				r[i] = new rank(first, second);
			}
			
			Arrays.sort(r);
			
			for (int i = 0; i < N; i++) {
				if(min>r[i].secR) {
					min=r[i].secR;
					ans++;
				}
			}
			sb.append(ans+"\n");
		}
		System.out.println(sb);
	}

	static class rank implements Comparable<rank>{

		int firR;
		int secR;
		
		public rank(int firR, int secR) {
			super();
			this.firR = firR;
			this.secR = secR;
		}

		@Override
		public int compareTo(rank o) {
			return Integer.compare(this.firR, o.firR);
		}
		
	}
}

 

- 그리디 알고리즘을 이요해서 문제풀이를 진행했습니다.

 

- 그리디 알고리즘을 구현하기 위해서 클래스를 만들었고, 비교를 위해서 Comparable를 사용했습니다.

 

- 첫번째 값을 비교 했고, 두번째 값을 비교하면서 최솟값으로 담아가며, 답을 구했습니다.

- 두번째 예시를 예로 들어봤습니다. 어떤 값으로 정렬을 해도 상관이 없습니다. 정렬한 값 외의 값으로 비교 작업을 하면 됩니다.

 

- 두번째 값을 비교할 때, 두번째 값에 대한 min값을 잡아줘야 합니다.