11. 임시반장 정하기

1. 문제

출처: 한국정보올림피아드

1학년 ~ 5학년 까지

가장 많은 학생들과 같은 반이 된 학생이 6학년의 반장이 된다!

여기선 4번 학생이 2, 3, 5번 학생과 같은 반이었으므로 4번 학생이 반장이된다.

 

2 - 1. 나의 풀이

1번 학생이 1학년 때 같은 반인 친구, 2학년때 같은 반인 친구 반복문을 돌려서 count 한다.

for문에서 탐색을 한 열로 돌아간다.

그래서 같은 학생과 같은 반인 적이 많을 수 있으므로 HashSet을 이용해서 count했다.

HashSet은 중복을 허용하지 않으므로 2번 학생이 여러번 add되어도 Hash의 size를 세면 한 번으로 카운팅됨!

 

2 - 2. 나의 코드

package Algorythm_Array;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Array11 {
    public static int solution(int[][] intArr, int n) {
        int answer =0;
        int index =0;
        int count =0;
        Set<Integer> set = new HashSet<>();


        //k, k번학생을 의미한다.
        //실수로 k, i, j 순으로 반복문 실행했다.
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < 5; i++) {
                int tmp2 = intArr[k][i];
                for (int j = 0; j < n; j++) {
                    if( tmp2 == intArr[j][i]){
                        if(k == j) continue; //이거 없어도 실행 될거같다.
                        set.add(j);
                    }
                }
            }
            if(count < set.size()){
                count = set.size();
                index = k;
            }
            set.clear();


        }
        return index +1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] intArr = new int[n][5];

        for (int i = 0; i < intArr.length; i++) {
            for (int j = 0; j < intArr[0].length; j++) {
                intArr[i][j] = sc.nextInt();
            }
        }

       /* for (int i = 0; i < n; i++) {
            for (int j = 0; j < 5; j++) {
                System.out.print(intArr[i][j] + " ");
            }
            System.out.println();
        }*/

        System.out.println(solution(intArr , n));

    }
}

 

3 - 1. 강의 풀이

1번 학생이 1학년 때 2,3,4,5번 학생과 몇번 같았나 를 체크하면 Hashset을 쓰는게 편하지만

1번 학생이 2번 학생과같은 적이 있나? 있는걸 찾으면 count하고 바로 해당 반복문 break 로 하면 Hastset을 안써도됨

 

강의에서는 후자를 선택해서 for문으로 탐색할 때 행을 기준으로 탐색했고, 같은 반인 적 있으면 바로 break;해서 중복된 값이 count 되는걸 막는다.

 

입력값을 저장할 때, 1번학생 ~ n번 학생 직관적으로 풀이 하기 위해서

arr[0]부터가 아니라 arr[1] 부터 입력값을 저장했다.

이를 위해 배열 정의 할 때 n+1만큼의 크기로 초기화한다.

 

3 - 2. 강의 코드

package Algorythm_Array;

import java.util.Scanner;

public class Array11_solution {
    public static int solution(int[][] arr, int n) {
        int answer = 0, max = Integer.MIN_VALUE;

        for (int i = 1; i < n+1; i++) {
            int cnt=0;
            for (int j = 1; j < n +1; j++) {
                for (int k = 1; k < 6; k++) {
                	/*i번 학생과 j번 학생이 같은 반이었던 적이 있는지 탐색
                      같은 반인적 있었으면 count++ 하고 바로 break; (중복되는걸 방지)*/
                    if (arr[i][k] == arr[j][k]) {
                        cnt++;
                        break;
                    }
                }
            }
            //최대값 갱신
            if (cnt > max) {
                max = cnt;
                answer = i;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n+1][6];

        for (int i = 1; i < n+1 ; i++) {
            for (int j = 1; j < 6; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        System.out.println(solution(arr , n));


    }
}

 

4. 얻어갈 점 

1. 계속 하나의 로직으로 밀고가는 성향을 고치고 넓게 생각해보자.