[백준 1946번][Java] 신입 사원 - 정렬과 스택

www.acmicpc.net/problem/1946

1946번: 신입 사원

 

문제 풀이

 

모든 지원자 중 자신보다 면접, 서류 분야 점수가 더 낮은 사람이 존재하는 경우 탈락하게 됩니다.

입력이 크기 때문에  N^2 로는 통과할 수 없습니다.

 

아래의 그림을 살펴보면 힌트를 얻을 수 있습니다.

 

빨간색으로 체크 친 지원자가 떨어지게 되는데, 해당 포인트는 점선으로 이뤄진 영역에 임의의 포인트를 포함합니다.

먼저 x축으로 입력을 정렬한 후 어떤 포인트를 포함하는 경우는 스택에 푸시하지 않고 아닌 경우에 푸시하도록 합니다.

그리고 마지막에 스택의 사이즈를 반환하면 끝.

 

 

hasInnerPoint 를 구현할 때 x축은 오름차순이 보장되므로 y축만 비교했습니다.

 

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

public class Main {
	static int T,N;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader();
//		InputReader reader = new InputReader("testcase.txt");
		T = reader.readInt();
		for (int tc = 0; tc < T; tc++) {
			N = reader.readInt();
			List<Point> applicant = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(reader.readLine());
				int y = Integer.parseInt(st.nextToken());
				int x = Integer.parseInt(st.nextToken());
				applicant.add(new Point(y, x));
			}

			applicant.sort(Comparator.comparingInt(point -> point.x));
			int ret = solve(applicant);
			System.out.println(ret);
		}
	}

	private static int solve(List<Point> applicant) {
		List<Point> stack = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			Point point = applicant.get(i);
			if(!hasInnerPoint(applicant.get(i), stack)) {
				stack.add(point);
			}
		}
		return stack.size();
	}

	private static boolean hasInnerPoint(Point point, List<Point> stack) {
		if(stack.isEmpty()) return false;
		Point top = stack.get(stack.size()-1);
		if(top.y < point.y) return true;
		return false;
	}
}
class Point {
	int y, x;

	public Point(int y, int x) {
		this.y = y;
		this.x = x;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}