[백준 풀이_Java] 1946 신입사원

 

 

 

 

처음 생각

 

'서류와 면접 중 적어도 하나는 다른 지원자보다 떨어지지 않는 자만 선발한다' 는 말의 의미는

 

'서류와 면접 둘다 다른 지원자보다 떨어진다면 너는 탈락이다' 라는 의미이다

 

그래서 처음에는 탈락자가 누구인지를 세려고 했었는데 풀다보니까 탈락자를 세기보다는 합격자를 세는 것이 더 편했다

 

처음에는 2차원 배열에 서류와 면접 등수를 넣고 서류의 등수대로 재배열하고자 했는데

 

그냥 1차원 배열의 인덱스에 서류의 등수를, 값에 면접의 등수를 넣으면 자동으로 등수대로 재배열된 효과가 있다

 

배열의 인덱스에 서류의 등수는 오름차순으로 되어있으니 이제 면접의 등수를 비교하면 된다

 

 

 

 

 

내가 푼 방법

 

처음에는 아래와 같이 제출했다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
		int N;
		int[] table;
		int cnt=1; // 서류 1등인 사람은 면접 결과와 상관없이 일단 합격이므로 1
		StringTokenizer st;
		int[] answer;
		
		for(int i=0; i<T; i++) { // 테스트케이스 T
			N = Integer.parseInt(br.readLine());
			table = new int[N+1];
            
			for(int j=0; j<N;j++) { // 서류, 면접의 등수를 table 배열의 인덱스와 값으로 넣기
				st = new StringTokenizer(br.readLine(), " ");
				table[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken()); // 배열의 주소와 값으로 넣기
			}
			
			answer = new int[N+1];
			for(int a=1; a<N+1; a++) { // 앞사람을
				for(int b=a+1; b<N+1; b++) { // 그 다음사람부터 마지막사람까지 비교
					if(table[a] > table[b]) answer[b] = 1; // 합격한사람 answer[] 값 1로 설정
				}
			}
			
			for(int k =1; k<N+1; k++) { // 중복으로 세는걸 방지하기 위해 answer[] 활용함
				if(answer[k] == 1) cnt++;
			}
			System.out.println(cnt);
			
		}
		br.close();
	}
}

 

**틀린 이유 및 주의할점

 

1) 앞사람을 다음사람부터 끝까지 비교한 이중 for문은 백준에서 시간초과를 내는 큰 원인중 하나이다

 

2) for문 밖에 선언한 필드는 for문이 돌고 난 후 for문 내 필드값 그대로 for문 밖에 저장되는 것을 염두에 두어야 한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
		int N;
		int[] table;
		StringTokenizer st;	
		
		for(int i=0; i<T; i++) {
			
			N = Integer.parseInt(br.readLine());
			table = new int[N+1];
			for(int j=0; j<N;j++) {
				st = new StringTokenizer(br.readLine(), " ");
				table[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken()); // 배열의 주소와 값으로 넣기
			}
            
			int cnt=1; // for문 밖에 선언시 이전의 테스트케이스에서의 cnt 값을 그대로 가져오게됨
			int min = table[1]; // 마찬가지로 이전의 min 값을 그대로 가져오게되므로 for 문 안에 선언
			for(int a=2; a<N+1; a++) {
				if(min > table[a]) {
                		cnt++;
                        	min = table[a]; // 이전의 합격자의 면접성적이 기준이됨
                		}
			}
			System.out.println(cnt);
			
		}
		br.close();
	}
}