[1946번] 신입 사원 ( 탐욕법 )

---

각각 입력하면 결과값이 잘 나오는데 같이 입력했을 때 결과값이 안나온다 -> 초기화 안해줌
아이디어 다 떠올렸는데 실제 구현에서 막혔다 -> 누가 이기나 해보자 😤

---

✅ 리스트 초기화

바보다. 각 테스트 케이스마다 리스트를 초기화줘야한다.
자바에서 ArrayList와 같은 동적 배열은 한 번 생성된 이후에 계속해서 데이터를 추가하면 크기가 동적으로 조절되면서 데이터가 계속 누적된다.

동적 배열 예시) LinkedList, Vector, Stack, Deque, HashSet, TreeSet, HashMap, TreeMap 등

아놔 근데 초기화 해줘도 또 틀렸네 미치겠다 아오

---

✅ 반례

반례가 있었다.
1
6
6 4
4 1
5 2
1 6
2 3
3 5

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		ArrayList<int[]> arr;

		int t = Integer.parseInt(br.readLine());

		for (int i = 0; i < t; i++) {
			arr = new ArrayList<>(); //
			int n = Integer.parseInt(br.readLine());
			for (int j = 0; j < n; j++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				arr.add(new int[] {a, b});
			}

			//오름차순 정렬
			Collections.sort(arr, Comparator.comparingInt((int[] a) -> a[0]));

			int cnt = n;
			int min = arr.get(0)[1];

			for (int j = 1; j < arr.size(); j++) {
				if (min < arr.get(j)[1]) {
					cnt--;
				} else { //면접 점수가 작은데
					if (arr.get(j)[0] == n) { //서류 점수가 꼴등이면 cnt --;
						cnt--;
					}
				}
			}

			System.out.println(cnt);

		}

	}
}

---

✅ 코드

왜 틀리지가 계속 된다면, 반레가 있는 거니까 계속 시도해도 틀리면 다른 방식을 강구해야 한다.
분명 반례가 없는 풀이가 있을 듯.

그런데... 왜 위에처럼 하면 반례가 생기고
밑에처럼 더해주면 반례가 안 생기냐,,?
일단 딴 문제 풀어야 하니까 넘어가고 시간 남으면 생각해보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {


	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		ArrayList<int[]> arr;

		int t = Integer.parseInt(br.readLine());

		for (int i = 0; i < t; i++) {
			arr = new ArrayList<>(); //
			int n = Integer.parseInt(br.readLine());
			for (int j = 0; j < n; j++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				arr.add(new int[] {a, b});
			}

			//오름차순 정렬
			Collections.sort(arr, Comparator.comparingInt((int[] a) -> a[0]));

			int ans = 1; // 서류 1등은 무조건 통과
			int min = arr.get(0)[1]; // 면접 점수 최소값
			for (int j = 1; j < n; j++) { // 서류 2등부터 시작
				if (arr.get(j)[1] < min) { // 이전의 최소 면접 점수보다 낮으면 통과
					ans++;
					min = arr.get(j)[1]; // 최소 점수 갱신
				}
			}
			System.out.println(ans);


		}

	}
}