[종만북] 신문기사의 오류 확인하기 ( 400m 달리기 ) - JAVA

문제 출처 :종만북  2.3장 문제 해결 전략 - 문제를 분해할 수 있을까?

코드설명

아래의 테스트케이스 처럼 문제가 주어졌다고 가정합니다.

첫번째 선수는 48초가 최대기록이고, 54초가 최악의 기록입니다. ( 세계선수권 대회를 찾아보니 400m 세계 기록은 43초대입니다 )

두번째 선수는 52초가 최대기록이고, 78초가 최악의 기록입니다.

세번째 선수는 90초가 최대기록, 140초가 최악의 기록입니다.

 

이때 신문에서는

1. 3번 선수는 1번선수에게 반드시 패배함

2. 1번 선수와 2번 선수는 서로 상대에게 이길 가능성이 있음.

3. 3번 선수는 2번 선수에게 반드시 패배함

 

이라는 주장을 펼쳤습니다. 

 

신문 기사 유형은

1. 선수 i는 선수 j에게 반드시 패배함

2. 선수 i와 선수 j는 서로 상대에게 이길 가능성이 있음 입니다.

 

문제에서 유의해야할점은, 시간이 짧을수록 우수한 선수라는 점입니다.

해당 사항에 유의하여 풀면 됩니다.

 

첫번쨰 유형같은경우 손쉽게 조건을 작성할 수 있습니다.

playerI의 최고 점수 > playerJ의 최악 점수

두번쨰 유형같은경우, 여러가지 조건으로 만들 수 있습니다.

가장 먼저 드는 생각은, 두가지 기록이 겹치는 것을 생각할 수 있습니다. 물론 이 방식이 더 명확합니다. 결국에 i의 최고점수가 더 작든, j의 최고점수가 더 같든간에 겹치는 부분이 반드시 존재하기 때문입니다.

( 플레이어J의 최고점수 < 플레이어I의 최악점수) && ( 플레이어I의 최고점수 < 플레이어 J의 최악점수)

처음에 위의 조건문을 보고, 만약에 플레이어 J의 최고점수가 더 높은 경우라면? 이와 같은 식이 성립할까? 라는 생각이 문득 들었었습니다. 먼저 말씀드리면, 반드시 서로 상대에게 이길 가능성이 있으므로 올바른 조건문입니다.

 

처음에, 위의 조건문이 명확하지 않아, 서로 무조건 이기는 경우를 만들어서 해당 경우를 검사했을떄 맞을경우 부정확하다고 판단하는 방식으로 코딩했습니다. 이와 같은 방식도 맞습니다. 사실상 위의 코드를 논리 NOT연산을 한것과 같습니다.

if(type == 2) { //선수 I와 선수 J는 서로 상대에게 이길 가능성이 있음 ( 서로 무조건 이기는 경우를 만든다. )
    if( (player[playerI].worst <= player[playerJ].best || player[playerI].best >= player[playerJ].worst) ){
        System.out.println("신문기사가 부정확합니다.");
    } else {
        System.out.println("신문기사가 정확합니다.");
    }
}

 

 

테스트케이스

• 첫 번째 줄에는 선수의 수 N이 주어집니다.
• 다음 N개의 줄에 걸쳐 각 선수의 최고 기록과 최악의 기록이 공백으로 구분되어 주어집니다.
• 그 다음 줄에는 신문 기사의 수 M이 주어집니다.
• 다음 M개의 줄에 걸쳐 각 신문 기사 정보가 주어집니다. 첫 번째 숫자는 신문 기사의 유형(1 또는 2)이며, 그 다음 두 숫자는 해당 기사에서 언급된 선수 i와 j의 번호입니다.

입력 1

3 
48 54
52 78
90 140
3
1 3 1
2 1 2
1 3 2

결과 1

신문기사가 정확합니다.
신문기사가 정확합니다.
신문기사가 정확합니다.

 

 

압력 2

4
45 50
46 51
47 52
48 53
3
1 1 2
2 1 3
2 2 4

 

결과 2

신문기사가 부정확합니다.
신문기사가 정확합니다.
신문기사가 정확합니다.

 

코드

package Main;

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

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static Runner[] runner;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		runner = new Runner[N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int bestInput = Integer.parseInt(st.nextToken());
			int worstInput = Integer.parseInt(st.nextToken());
			
			runner[i] = new Runner(bestInput, worstInput);
		}
		
		st = new StringTokenizer(br.readLine());
		// 신문 기사 수 M		
		M = Integer.parseInt(st.nextToken());
		
		// 신문 기사 검증
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());
			int athelete_i = Integer.parseInt(st.nextToken()) - 1;
			int athelete_j = Integer.parseInt(st.nextToken()) - 1;
			
			//1. type 1 일경우 : i는 j에게 반드시 패배함
			// athelete_i의 최대 기록이 athelete_j의 최악기록보다 더 커야 합니다. (시간이 짧을수록 우세한 경기입니다.)
			if(type == 1) {
				if(runner[athelete_i].best > runner[athelete_j].worst) {
					System.out.println("신문기사 정확");
				} else {
					System.out.println("신문기사 오류");
				}
			}
			
			//2. type 2 일경우 : 선수 i와 선수 j가 서로 상대에게 이길 가능성 있음
			// i의 worst가 j의 best보다 작으면 안됨.
			// j의 worst가 i의 best보다 작으면 안됨.
			//	!( worst[i] > best[i] ) ( 	
			if(type == 2) {
				if( !(runner[athelete_i].worst <= runner[athelete_j].best) && !(runner[athelete_j].worst <= runner[athelete_i].best) ) {
					System.out.println("신문기사 정확");
				}else {
					System.out.println("신문기사 오류");
				}
			}
			
			
		}
	}
	
}

class Runner{
	int best;
	int worst;
	public Runner(int best, int worst) {
		this.best = best;
		this.worst = worst;
	}
}

 

조건식을 다르게 해본 코드(결국은 같다)

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static Player[] player;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		player = new Player[N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int best = Integer.parseInt(st.nextToken());
			int worst = Integer.parseInt(st.nextToken());
			player[i] = new Player(best, worst);
		}
		
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());
			int playerI= Integer.parseInt(st.nextToken()) - 1;
			int playerJ = Integer.parseInt(st.nextToken()) - 1;
			
			if(type == 1) { //선수 i는 선수 j에게 반드시 패배합니다. (기록이 작으면 경기는 이기는 것 입니다.)
				if( (player[playerI].best > player[playerJ].worst) ) { //선수i의 최고기록이 선수j의 최악기록보다 더 크다면, 반드시 패배하므로, 해당 조건이 만족하는지 확인한다.
					System.out.println("신문기사가 정확합니다.");
				}else {
					System.out.println("신문기사가 부정확합니다.");
				}
			}
			
			if(type == 2) { //선수 I와 선수 J는 서로 상대에게 이길 가능성이 있음 ( 서로 무조건 이기는 경우를 만든다. )
				if( (player[playerI].worst <= player[playerJ].best || player[playerI].best >= player[playerJ].worst) ){
					System.out.println("신문기사가 부정확합니다.");
				} else {
					System.out.println("신문기사가 정확합니다.");
				}
			}
		}
		
	}

}

class Player{
	int best;
	int worst;
	public Player(int best, int worst) {
		this.best=best;
		this.worst = worst;
	}
}