[백준] 1268번: 임시 반장 정하기(구현)

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

1268번: 임시 반장 정하기

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		/** 1 **/
		int n = Integer.parseInt(bf.readLine());// 학생 수
		int[][] arr = new int[n][5];		// 행: 학생수, 열: 1~5학년
		int[] sameClassRoom = new int[n];	// 학생 별 같은 반이었던 학생 수 
		int maxStudent = 0;			// 같은 반이었던 학생 수 최댓값
		int answer = 0;
		
		/** 2 **/
		for(int i=0; i<n; i++) {	// 학생 수별로 1학년 ~ 5학년까지 몇 반에 속했었는지 입력
			st = new StringTokenizer(bf.readLine());
			for(int j=0; j<5; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		/** 3 **/
		for(int i=0; i<n; i++) {
			Set<Integer> sameClass = new HashSet<>(); 

			for(int j=0; j<5; j++) {
				for(int k=0; k<n; k++) {
					if(arr[i][j] == arr[k][j] && k != i) {
						sameClass.add(k);
					}
				}
			}
			
			if(maxStudent < sameClass.size()) {
				maxStudent = sameClass.size();
				answer = i;
			}
		}
		
		
//		/** 4 **/
//		for(int i=0; i<sameClassRoom.length; i++) {
//			if(sameClassRoom[i] > maxStudent)
//				maxStudent = sameClassRoom[i];
//		}
//
//		/** 5 **/
//		for(int i=0; i<sameClassRoom.length; i++) {
//			if(sameClassRoom[i] == maxStudent) {
//				System.out.println(i+1);
//				break;
//			}
//		}
		System.out.println(answer+1);
		
		bf.close();
	}

}

풀이

구현 문제, 문제에서 주어진 방식대로 완전탐색으로 해결하려고 했다.

Input 학생 수는 최대 1000이고, 5학년이어서 O(5*1000*1000) 이어서 가능하다고 판단하고 접근했다.
1번 ~ n번의 각 학생별로 다른 학생과 몇번 같은반이 된지 하나하나 다 찾아서 비교를 해주었다.

문제의 예시를 통해 보면,,

1번 학생이 1학년, 2학년, 3학년, 4학년, 5학년동안 다른 학생과 총 몇번 같은반이 된지 체크해서 카운트해주었다.

1번 학생은 1학년~5학년 전부 다른 학생과 같은반이 된 적이 한번도 없으므로 카운트는 0이다,

위와같이 해보면 2번 학생은 4학년때 4번 학생과 1번

3번 학생은 3번, 4번 학생은 4번, 5번 학생은 2번이 나온다.

하지만 위와 같이 접근했을때 중복이라는 문제점이 발생한다. 이 중복때문에 헤맸는데..

 

4

3 5 1 5 5

4 4 3 5 1

1 2 3 2 2

1 3 3 2 2

 

만약 위와 같이 주어졌을때, 3번친구는 4번친구와 4학년, 5학년에 모두 같은반이지만, 중복이 되므로 +2가 아닌 +1을 해주어야 한다. 따라서 위와 같은 예외가 있었다.

그래서 Set - HashSet을 이용해 해결을 해주었는데, 특징은 중복을 허락하지 않고 순서와 관계없이 정렬된다.

중복을 허락하지 않으므로 위와같은 중복을 방지할 수 있다.

따라서 같은 반이 된 경우, HashSet에 추가해주고,(크기 +1) 학생 수와 비교해준다.

 

 

/** 1 **/

변수 입력

 

/** 2 **/

2차원 배열에 Input 값을 저장한다.

 

/** 3 **/

각 학생 별로 비교하는 문장,

가장 밖 for문(i=0; i<n; i++) 이 for문은, 비교할 대상이 되는 학생을 지목할 행이다.

중간 for문(j=0; j<5; j++) 이 for문은, 비교할 대상의 학년 별로 선택할 열이다.

가장 안 for문(k=0; k<n; k++) 이 for문은, 위 i,j의 학생과 학년별로 모든 학생을 탐색하면서 비교할 for문이다.

 

1번 학생의 경우로 예를 들어보면,

1번 학생: 1학년, 2학년, 3학년, 4학년, 5학년 동안

2번 ~ 5번 학생의 1, 2, 3, 4, 5 학년과 비교를 해야한다.

비교를 통해 같은 반일경우 -> HashSet에 add()를 통해 사이즈를 +1 한다.