본문 바로가기

코딩테스트

[인프런 자바/java] 12. 멘토링 _디버깅의 눈물

체크 포인트

 

1. 2차원 배열에 대한 3중 for 문 이용

 

예제)

4 3
3 4 1 2
4 3 2 1
3 1 4 2

 

-처음 문제를 풀려고 했을 때, 메모리의 효율적 사용을 생각하다보니 설마 다중 for문으로 풀어야 한다고 생각하지 못했다. 고민해도 해결하기 어려워 인프런 풀이를 보니 4중 for문으로 해결하는 방식이 있었다.

-하지만 고민하던 중 3중 for문으로도 해결이 가능해 나의 방식으로 해결을 시도했고 성공했다.

 

-먼저 예제를 보면, 3개의 수학 테스트에 대한 1,2,3,4번 학생시험등수 순으로 입력된 2차원 배열이 있다.

-멘토가 되려면 멘티보다 모든 테스트에서 항상 높은 등수여야 한다는 조건을 확인하기 위한 과정을 다음과 같이 추론해보았다.

 

 

(1)각 테스트에 대한 학생들의 순위를 파악해야하고,

(2)기준 학생보다 높은 순위의 학생이 있다면 기록해두고,

(3)모든 테스트 탐색이 끝났을 때, 기준 학생보다 낮은 순위의 학생이 있다면 멘토-멘티 관계가 성립한다. 

 

 

-이해를 위해 좀 더 자세히 설명하자면...

 

 

 

 

2. 학생들의 순위 정보를 담는 check[][] 배열 별도 생성

 

예제)

4 3
3 4 1 2
4 3 2 1
3 1 4 2

 

 

-첫 수학 테스트 결과 3 4 1 2에서,

(1)4번 학생(2등)보다 등수가 높은 학생은 3번 학생(1등)이고, check[][]의 4행 3열에 기록한다.

(2)1번 학생(3등)보다 등수가 높은 학생은 4번 학생(2등), 3번 학생(1등)이고, check[][]의 1행4열, 1행3열에 기록한다.

(3)2번 학생(4등)보다 등수가 높은 학생은 1번 학생(3등), 4번 학생(2등), 3번 학생(1등)이고, check[][]의 2행1열, 2행4열, 2행3열에 기록한다.

 

 

-check[][]의 4행 3열 기록의 의미는, 4행(4번 학생)보다 순위가 한번이라도 높은 적이 있는 학생으로 3열(3번 학생)이 있다라는 것이다.

-따라서 총 세 번의 수학 테스트를 탐색해가면서 기준 번호의 학생보다 순위가 높은 학생의 정보를 check[][]배열에 모두 기록해두고,

-모든 테스트가 끝난 후 check[][]를 탐색하며 기록되지 않은 개수를 센다면 '멘토-멘티' 관계의 개수를 구할 수 있다.

 

 

 

 

 

풀이

 

 

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

public  class Main {
	
	// 테스트와 학생의 등수를 나타내는 배열
	static int[][] arr;
	
	// 1번부터 ~ N번 학생까지 각 학생보다 높은 등수를 가진 다른 학생을 표기하는 배열  
	static boolean[][] check;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	
    	// 학생의 수 N
    	int N = Integer.parseInt(st.nextToken());
    	// 수학 테스트의 수 M 
    	int M = Integer.parseInt(st.nextToken());
    	
    	// 테스트x학생 수 배열 초기화
    	arr = new int[M][N];
    	// 0번 학생은 없기 때문에 편의상 N+1로 초기화
    	// 학생 간의 순위를 나타내기 위해 [N+1][N+1]로 설정
    	check = new boolean[N+1][N+1];
    	
    	// 테스트x학생 수 배열 정보 입력
    	for(int i=0; i<M; i++) {
    		st = new StringTokenizer(br.readLine(), " ");
    		for(int j=0; j<N; j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	// 탐색 시작
    	solution(N,M);
    	
    } // end of main
    
    
    static void solution(int N, int M){
    	
    	// 탐색을 위한 3중 for문 시작
    	// 테스트의 수 만큼 탐색
    	for(int i=0; i<M; i++) {
    		// 각테스트에 대한 학생 탐색
    		for(int j=1; j<N; j++) {
    			// j번째 학생을 기준으로, 
    			// 해당학생보다 순위가 높은 학생을 check[][]배열에 저장
    			for(int k=j-1; k>=0; k--) {
    				// arr[i][j] 번호 학생은, arr[i][k]번호를 가진 학생보다 순위가 낮다는 의미
    				check[arr[i][j]][arr[i][k]] = true;
    			}
    		}
    	} // end of for
    	
    	// 멘토-멘티가 될 수 있는 총 개수를 담는 변수
    	int count = 0;
    	
    	// 모든 학생에 대한 순위 정보를 가지고 있는 check[][]배열 탐색 
    	for(int i=1; i<=N; i++) {
    		for(int j=1; j<=N; j++) {
    			// 자기 자신과의 비교를 제외하고 && 해당 학생보다 항상 순위가 높았으면,
    			if(i!=j && check[i][j]==false) {
    				// 멘토-멘티 성립 개수 추가
    				count++;
    			}
    		}
    	}
    	
    	System.out.println(count);
    	
    }
    
} // end of Main