[Eric's 백준] 1946번 - 신입 사원 - Java

안녕하세요! Eric 입니다!

오늘 풀어볼 문제는 백준 1946번

신입사원 문제 입니다.

해당문제는 그리디 유형으로 풀어보았습니다.

우선 예시에서 나온 값을 저는 오늘도 그림으로 그려서 문제를 풀어 보았습니다.

그리디 유형에서 우선 각각의 test 케이스마다

저는 A를 기준으로 오름차순으로 정리를 우선 하였습니다. ( Comparble 이용)

그러면 B 기준이 왔다갔다하면서 정렬이 안되어 있을텐데요,

 

여기에서 우선 A를 기준으로 오름차순이 되어있으므로,

하나하나 내려가면서 보면

 

(1 ,4) 와 (2, 3) 을 비교하면 (2, 3) 이 A랭크에서는 비록 지고 있지만, B랭크에서는  (1, 4)의 4 보다 등수가 좋으니

cnt + 을 해주었습니다.

마찬가지로

( 2 ,3 ) 과 (3, 2)로 내려갔을때 B랭크가 2로 더 좋으므로 cnt+ 을 해주었습니다.

이런식으로 하면 첫번째 케이스에서는

(5, 5) 만 탈락! 

 

두번째 케이스를 보면

( 1, 4) 랑 ( 2 , 5) 를 비교해보면 ( 2, 5)는 (1, 4) 보다 A랭크도 안좋고, B랭크도 안좋아서 탈락!

(3, 6) 도 마찬가지 이유로 탈락!

 

반면에, (1, 4)와 (4, 2)는 B랭크에서 더 좋은 점수 이므로 합격 cnt+ 

 

이런식으로 코드를 작성해보면..!

 

코드

코드로 구현해보면..!

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collections;
	import java.util.StringTokenizer;
	public class N1946 {
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int tc = Integer.parseInt(br.readLine());
	ArrayList<Candidate> arr;
	StringTokenizer st;
	for (int i = 0; i < tc; i++) {
	int N = Integer.parseInt(br.readLine());
	arr = new ArrayList<>();
	for (int j = 0; j < N; j++) {
	st = new StringTokenizer(br.readLine());
	int rankA = Integer.parseInt(st.nextToken());
	int rankB = Integer.parseInt(st.nextToken());
	arr.add(new Candidate(rankA, rankB));
	}
	System.out.println(solution(arr, N));
	}
	br.close();
	}
	public static int solution(ArrayList<Candidate> arr, int N) {
	int cnt = 0;
	Collections.sort(arr);
	int min = Integer.MAX_VALUE;
	for (Candidate ob : arr) {
	if (ob.rankB < min) {
	min = ob.rankB;
	cnt++;
	}
	}
	return cnt;
	}
	}
	class Candidate implements Comparable<Candidate> {
	int rankA;
	int rankB;
	public Candidate(int rankA, int rankB) {
	this.rankA = rankA;
	this.rankB = rankB;
	}
	@Override
	public int compareTo(Candidate o) {
	// rankA기준으로 오름차순
	return this.rankA - o.rankA;
	}
	}

view raw N1946.java hosted with ❤ by GitHub

 

 

이상 신입사원 문제 였습니다.

 

P.S
문제를 풀다보니
저도 얼른 개발 신입사원이
되고싶네여...