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

https://www.acmicpc.net/problem/1946

---

문제

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
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 = new StringTokenizer(br.readLine(), " ");
		
		int t = Integer.valueOf(st.nextToken());
		
		for(int i=0; i<t; i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.valueOf(st.nextToken());
			
			int[] arr = new int[n+1];
			for(int j=0; j<n; j++) {
				st = new StringTokenizer(br.readLine());
				int f = Integer.valueOf(st.nextToken());
				int s = Integer.valueOf(st.nextToken());
				arr[f] = s;
			}
			int ans = solution(arr, n);
			System.out.println(ans);
		}
	}
	
	public static int solution(int[] arr, int n) {
		int ans = 1;
		int top = arr[1];
		for(int i=2; i<=n; i++) {
			if(top > arr[i]) {
				top = arr[i];
				ans += 1;
			}
		}
		return ans;
	}

}

 

 

 

초반에 선택한 풀이: 

딱 보니 O(n)의 풀이로 해야 시간초과가 나지 않을 것 같았습니다. 그래서 생각한 것은 HashMap이었습니다.

HashMap에 {신입사원 인덱스: [1차심사 결과, 2차심사 결과]} 로 넣어 신입사원을 도는 for문 동안 1차 2차 심사 결과가 겹치는지를 확인하려고 했습니다.

하지만 자바로는 2중 for문을 사용해야한다는 것을 뒤늦게 깨달았고, 결국 HashSet으로 교집합을 이용하여 풀어보고자 했지만, 이도 마찬가지로 2중 for문을 피할 수 없었습니다. 일단 풀어보자 하고 제출은 했지만 ← 시간 초과 였습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
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 = new StringTokenizer(br.readLine(), " ");
		
		int t = Integer.valueOf(st.nextToken());
		
		for(int i=0; i<t; i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.valueOf(st.nextToken());
			int[] f = new int[n];
			int[] s = new int[n];
			for(int j=0; j<n; j++) {
				st = new StringTokenizer(br.readLine());
				f[j] = Integer.valueOf(st.nextToken());
				s[j] = Integer.valueOf(st.nextToken());
			}
			
			int ans = solution(f, s);
			System.out.println(ans);
		}
	}
	
	public static int solution(int[] f, int[] s) {
		int ans = 0;
		
		for(int i=0; i<f.length; i++) {
			ArrayList<Integer> fArr = new ArrayList<>();
			ArrayList<Integer> sArr = new ArrayList<>();
			for(int j=0; j<f.length ; j++) {
				if(f[i] > f[j]) {
					fArr.add(j);
				}
				if(s[i] > s[j]) {
					sArr.add(j);
				}
			}
			HashSet<Integer> fSet = new HashSet<>(fArr);
			HashSet<Integer> sSet = new HashSet<>(sArr);
			fSet.retainAll(sSet);
			
			if(fSet.size() == 0) ans += 1;
		}
		
		return ans;
	}

}

 

 

---

회고

어제와 마찬가지로 다양한 사고를 할 수 있도록 노력해봐야겠습니다. 1차를 인덱스로, 2차를 값으로 넣는다는 발상은 어떻게 하셨을까요.. 알면 알수록 재밌네요