728x90
❓ 신입 사원
🏷️ 관련 주제 : Greedy Algorithm Sort
💦 나의 시도
반복문을 이용한 교집합 구하는 방법을 이용한 시도
- 길이 N 이차원 배열 int[][] newbies 에 {사원 번호, 서류 심사 순위, 인터뷰 순위}를 입력 순서대로 할당
- 서류 심사 순위, 인터뷰 순위의 오름차순대로 정렬한 사원 번호를 각각의 배열 int[] paperRank, int[] interviewRank로 할당
- for-each문을 통해 newbies에서 사원 정보가 담긴 일차원 배열 int[] n을 하나씩 꺼내기
- n보다 높은 순위의 사원 구하기
- Set better에 n보다 높은 순위의 사원 번호를 반복문을 통해서 넣기
- 서류 심사 순위와 인터뷰 순위가 모두 높은 사원이 존재하지 않으면 결과값으로 출력할 int result 1증가
- interviewRank에서 n보다 높은 순위의 사원들 중 paperRank에도 포함된 사원번호가 있는지 반복문으로 체크
- 해당 사원 번호가 존재하지않으면, 결과값으로 출력한 int result 1증가
- 테스트 케이스가 끝날 때마다 BufferedReader에 result + "\n" 쓰기
- 모든 테스트 케이스가 끝난 후, BufferedReader 출력
위의 방법으로 작성한 코드
import java.io.*;
import java.util.*;
import java.util.stream.Stream;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
int[][] newbies = new int[N][3];
int result = 0;
for (int j = 0; j < N; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int paper = Integer.parseInt(st.nextToken());
int interview = Integer.parseInt(st.nextToken());
newbies[j][0] = j;
newbies[j][1] = paper;
newbies[j][2] = interview;
}
int[] paperRank = Arrays.stream(newbies).sorted((a, b) -> a[1] - b[1]).mapToInt(x -> x[0]).toArray();
int[] interviewRank = Arrays.stream(newbies).sorted((a, b) -> a[2] - b[2]).mapToInt(x -> x[0]).toArray();
for (int[] n : newbies) {
boolean in = true;
Set better = new HashSet<>();
for (int j = 0; paperRank[j] != n[0]; j++) {
better.add(paperRank[j]);
}
for (int j = 0; interviewRank[j] != n[0]; j++) {
if (better.contains(interviewRank[j])) {
in = false;
break;
}
}
if (in) {
result++;
}
}
bw.write(result + "\n");
}
bw.close();
}
}⏱️ 시간 초과
서류 심사 순위대로 정렬한 사원 번호를 담은 paperRank와
인터뷰 심사 순위대로 정렬한 사원 번호를 담은 interviewRank,
현재 뽑은 사원보다 순위가 높은 사원의 교집합을 구하는 과정에서 시간 초과가 날 것 같아서 코드를 변경해 보았습니다.
- int[][]
newbies대신paperRank와interviewRank에 {사원 번호, 심사 순위}를 할당 - 두 이차원 배열을 심사 순위로 오름차순 정렬
- Map<Integer, Integer>
interviewRankMap선언, 모든 사원의 사원번호, 인터뷰 심사 순위를 추가- 키 : 사원 번호
- 값 : 인터뷰 심사 순위
paperRank에서 서류 심사 순위가 높은 순서대로 사원을 뽑아서 해당 사원의 인터뷰 심사 순위 intiRank가 현재까지 뽑은 사원들의 인터뷰 심사 최고 순위 intbestRank보다 좋으면result1 증가bestRank에에iRank와bestRank` 중 더 작은 값 할당
위의 방법으로 작성한 코드
import java.io.*;
import java.util.*;
import java.util.stream.Stream;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
int[][] paperRank = new int[N][2];
int[][] interviewRank = new int[N][2];
int bestRank = N;
int result = 0;
for (int j = 0; j < N; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
paperRank[j][0] = interviewRank[j][0] = j;
paperRank[j][1] = Integer.parseInt(st.nextToken());
interviewRank[j][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(paperRank, (a, b) -> a[1] - b[1]);
Arrays.sort(interviewRank, (a, b) -> a[1] - b[1]);
Map<Integer, Integer> interviewRankMap = new HashMap<>();
for (int j = 0; j < N; j++) {
interviewRankMap.put(interviewRank[j][0], interviewRank[j][1]);
}
for (int[] n : paperRank) {
int iRank = interviewRankMap.get(n[0]);
if (iRank < bestRank) {
result++;
}
bestRank = Math.min(iRank, bestRank);
}
bw.write(result + "\n");
}
bw.close();
}
}❌ 틀렸습니다.
일단 틀린 원인은 모르겠어서 정렬하고 interviewRank에 원소를 추가하는데 걸린 시간을 없앨 방법을 궁리해 보았습니다.
- 길이 N의 정수형 배열 int[]
papers선언 : 순위를 오름차순대로 정렬한 사원 번호를 담은 배열 - Map<Integer, Integer>
interviews선언- 키 : 사원 번호
- 값 : 면접 심사 순위
- int
bestRank선언 : 현재까지 최고 면접 심사 순위 - int
result선언 : 입사 가능한 사원 수 - 그 다음 부분은 이전 코드와 동일
위의 방법으로 작성한 코드
import java.io.*;
import java.util.*;
import java.util.stream.Stream;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
int[] papers = new int[N];
Map<Integer, Integer> interviews = new HashMap<>();
int bestRank = N;
int result = 0;
for (int j = 0; j < N; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int paperRank = Integer.parseInt(st.nextToken());
int interviewRank = Integer.parseInt(st.nextToken());
papers[paperRank - 1] = j;
interviews.put(j, interviewRank);
}
for (int n : papers) {
int iRank = interviews.get(n);
if (iRank < bestRank) {
result++;
}
bestRank = Math.min(iRank, bestRank);
}
bw.write(result + "\n");
}
bw.close();
}
}❌ 틀렸습니다.
틀린 원인을 코드 중간 중간 변수의 값을 출력하며 확인해 본 결과
bestRank를 N이라고 둬서 iRank와 bestRank가 동일한 경우가 추가되지 않았다.
bestRank를N + 1로 초기화
📑제출 기록 및 오답 원인
💯해결 방법
import java.io.*;
import java.java.*;
import java.util.stream.Stream;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
int[] papers = new int[N];
Map<Integer, Integer> interviews = new HashMap<>();
int bestRank = N + 1;
int result = 0;
for (int j = 0; j < N; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int paperRank = Integer.parseInt(st.nextToken());
int interviewRank = Integer.parseInt(st.nextToken());
papers[paperRank - 1] = j;
interviews.put(j, interviewRank);
}
for (int n : papers) {
int iRank = interviews.get(n);
if (iRank < bestRank) {
result++;
bestRank = iRank;
}
if (bestRank == 1) {
break;
}
}
bw.write(result + "\n");
}
bw.close();
}
}728x90
