[Baekjoon] 1946_신입 사원

Silver I

문제(출처: https://www.acmicpc.net/problem/1946)

---

< 신입 사원 >

 

문제 풀이 

 

처음에는 입력받은 성적을 서류 심사를 기준으로 내림 차순으로 정렬했다. 그 후 면접 성적을 이중 for문을 사용해서 다른 모든 사람보다 성적이 떨어지지 않는지 확인했다. 이렇게 할 경우 시간초과가 발생한다.

 

for문을 한 번 사용해서 문제를 해결하는 방법을 찾다가 떠오르지 않아 찾아봤다,,

먼저 서류 성적을 기준으로 오름 차순으로 정렬한다. 그 후에 면접 성적을 기준으로 최솟값을 찾는 방식으로 구한다.

 

 my solution (Java)

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

public class _1946_ { // 신입 사원
	static class Person implements Comparable<Person> {
		private int a;
		private int b;

		public Person(int a, int b) {
			this.a = a;
			this.b = b;
		}

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

	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

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

		ArrayList<Person> arr = new ArrayList<>();
		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(bf.readLine());

			for (int j = 0; j < n; j++) {
				st = new StringTokenizer(bf.readLine());
				arr.add(new Person(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
			}

			Collections.sort(arr);

			int result = 1;
			int idx = 0;
			for (int j = 1; j < n; j++) {
				if (arr.get(idx).b > arr.get(j).b) {
					result += 1;
					idx = j;
				}
			}
			bw.write(result + "\n");
			arr.clear();
		}
		bw.flush();
	}
}

 

Main

변수)
t : 테스트 케이스 개수
arr : 신입사원 성적 저장 
n : 지원자의 숫자
result : 선발할 수 있는 신입사원 수
idx : index

 

- 테스트 케이스 개수(t) 입력

- 지원자의 숫자(n) 입력

- 지원자의 성적을 입력받아 arr에 저장

- 서류 심사 성적을 기준으로 오름차순 정렬

- arr 순환

: 면접 성적이 순환하는 사람의 면접 성적보다 등수가 크다면 선발할 수 있는 신입사원 수 증가 및 idx를 그 값으로 교체

(서류 성적을 오름차순 정렬했다면 면접 성적이 내림차순으로 정렬될수록 선발할 수 있는 신입사원의 수가 늘어남)

---

---