[Java] 백준 1268번 - 임시 반장 정하기

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

1268번: 임시 반장 정하기

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 구현

문제

오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. 그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다.

그래서 오민식 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다. 예를 들어 학생 수가 5명일 때의 표를 살펴보자.

 1학년2학년3학년4학년5학년

1번 학생	2	3	1	7	3
2번 학생	4	1	9	6	8
3번 학생	5	5	2	4	4
4번 학생	6	5	2	6	7
5번 학생	8	4	2	2	2

위 경우에 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며, 2번 학생과는 4학년 때 같은 반이었음을 알 수 있다. 그러므로 이 학급에서 4번 학생과 한번이라도 같은 반이었던 사람은 2번 학생, 3번 학생과 5번 학생으로 모두 3명이다. 이 예에서 4번 학생이 전체 학생 중에서 같은 반이었던 학생 수가 제일 많으므로 임시 반장이 된다.

각 학생들이 1학년부터 5학년까지 속했던 반이 주어질 때, 임시 반장을 정하는 프로그램을 작성하시오.

입력

첫째 줄에는 반의 학생 수를 나타내는 정수가 주어진다. 학생 수는 3 이상 1000 이하이다. 둘째 줄부터는 1번 학생부터 차례대로 각 줄마다 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 5개의 정수가 빈칸 하나를 사이에 두고 주어진다. 주어지는 정수는 모두 1 이상 9 이하의 정수이다.

출력

첫 줄에 임시 반장으로 정해진 학생의 번호를 출력한다. 단, 임시 반장이 될 수 있는 학생이 여러 명인 경우에는 그 중 가장 작은 번호만 출력한다.

 

---

 처음엔 어떤 학생이 같은 반으로 많이 겹쳤는가? 문제인 줄 알았다.

다른 반례의 경우

 

5
1 1 1 1 1
1 1 1 1 1
1 3 4 5 5
3 3 3 3 3
4 4 4 4 4

정답
3

처음 내가 짠 코드대로라면 정답은 1이 된다.

 

1번학생과 2번 학생이 5년 내내 같은 반이었기 때문이다.

 

하지만 이는 틀렸으며 해당 문제는 가장 많이 같은 반을 해본 학생을 물어보는 문제로

 

1번 학생 : 2, 3

2번 학생 : 1, 3

3번 학생: 1, 2, 4, 5

4번 학생: 3

5번 학생: 3

 

즉 정답은 3이 된다.

 

문제 해석을 잘못하여 검색해서 알아낸 문제였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Date;
import java.util.StringTokenizer;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int [][] data = new int [n][5];
		int [][] result = new int[n][n];
		
		for(int i=0; i<n; i++) {
			String s = br.readLine();
			String [] arr = s.split(" ");
			for(int j=0; j<5; j++) {
				data[i][j] = Integer.parseInt(arr[j]);
			}
		}
		
		for(int j=0; j<5; j++) {
			for(int i=0; i<n-1; i++) {
				int cmp = data[i][j];
				for(int k=i+1; k<n; k++) {
					if(cmp == data[k][j]) {
						result[i][k] = 1;
						result[k][i] = 1;
					}
				}	
			}
		}
		
		int index = 0;
		int max = 0;
		for(int i=0; i<n; i++) {
			int tmp = 0;
			for(int j=0; j<n; j++) {
				if(result[i][j] == 1) {
					tmp++;
				}
			}
			if(max < tmp) {
				max = tmp;
				index = i;
			}
		}
		System.out.println(index+1);
	}
}

 

각 학생으로 행열로 구성된 2차원 배열을 구현하여

 

같은 반이었던 적이 있으면 1을 저장하도록 하였다.

 

같은 반인 경험이 있으면 1만 존재하므로 중복케이스도 쉽게 배제할 수 있으며 모든 경우의 수를 고려하기 쉬워진다.