<2.11> 임시반장 정하기

mutexlocking·2022년 7월 29일
0

문제
: 1번학생부터 N번 학생까지에 대해 과거 1학년부터 5학년까지 몇반이었는지에 대한 내역이 주어진다. 그러면 1번 학생부터 N번 학생까지의 각각의 학생에 대하여 과거 같은 반에 속한 학생수가 가장 많은 학생을 임시 반장으로 선정한다.
이때 학생 수 N과 ,N명의 학생에 대한 1학년부터 5학년 까지의 속한 반의 내역이 입력으로 주어지면 -> 이에 따른 임시반장은 몇번 학생인지 구하라.

예를 들어 같이 N=5로 입력되고 , 이후 입력이 아래와 같이 주어졌다면
1번학생의 경우는 나머지 2~4번 학생들과 1~5학년동안 단 한번도 같은반에 속하지 않았고/
2번학생의 경우는 -> 4번 학생과 4학년때 같은 반에 속했으니 {4}
3번학생의 경우는 -> 2학년 때 4번학생과 , 3학년때 4번과 5번 학생과 같은반에 속했으니 결과적으로 {4,5}번 학생과 같은반에 속한 내역이 있고
4번학생의 경우는 -> 2학년때 3번 학생과, 3학년때 3번과 5번 학생과 , 4학년때 2번학생과 같으느반에 속했으니 결과적으로 {2,3,5}번 학생과 같은반에 속한 내역이 있으며
5번 학생의 경우는 3학년때 3번과 4번학생과 같은반에 속했으니 결과적으로 {3,4}번 학생과 같은반에 속한 내역이 있다.

그렇다면 이 중에서 과거 같은반에 속한 학생 수가 가장 많으면서 && 학생 번호가 가장 작은 경우는 4번 학생 이므로, 출력값은 4가 되어야 한다.

나의 경우는 이 문제의 요구사항을 어렵지 않게 파악할 수 있었다.
"각 학생별로 과거 같은반에 속한 학생 수를 count하여
그 count값이 가장 크면서 && 학생 번호가 가장 작은 학생의 번호를 출력하자"

그런데 해결로직을 처음에 잘못 생각하여 문제를 계속 맞추지 못하였다.

[잘못 생각한 해결 로직]

  • 각 학생별로 , 나머지 학생들과 같은 반이었는지 여부를 비교하여 , 같은반이었다면 cnt 변수를 1씩 증가시키자
  • 그리하여 이 cnt 값이 가장 크면서 && 학생 번호가 가장 작은 학생의 번호를 출력하자.

여기서 cnt 변수를 단순하게 1씩 증가시키는 로직으로 ,
같은반이었던 아이들 수를 센 것이 문제였다.

왜냐하면 이러한 반례가 있을 수 있기 때문이다.
2 3 1 7 3
4 1 9 6 8
5 5 2 4 4
6 5 2 6 7
8 4 2 2 2
위와 같이 문제에서 주어진 예시 입력을 기준으로 본다면
3번 학생은 2학년때도 3학년때도 모두 4번 학생과 같은반이었으므로 count를 2번하게 되지만 / 실제로는 모두 4번학생 하고만 같은 반이었기 떄문에 결과적으로 같은반이었던 학생수를 따질때는 2값이 아닌 1값만큼만 으로 간주되어야 한다.

  • 이를 통해 cnt변수를 1증가시키는 로직으로 같은 반이었던 학생 수를 count하면 안된다는 것을 알 수 있다.

[올바른 해결 로직]

  • 위에서 본 잘못된 해결 로직에서는 동일한 4번 학생을 2번 count하였기 때문에 문제가 되었다.
  • 따라서 무조건 count하는게 아니라 , 이전에 한번 count한 학생 번호라면 - 중복count를 하지 않으면 올바른 count 로직이 된다.
  • 이에 대한 구현 방식으로 나는 Set을 사용하였다.
  • 같은 반에 속한 다른 아이들의 번호를 Set안에 넣어둔다면 , Set의 특징으로 인해 어차피 중복된 아이의 번호는 count되지 않을 것이고, 나중에 Set의 Size만을 가지고 같은반에 속했던 아이들의 수를 비교할 수 있기 때문이다.

[나아가 loop를 사용하는 논리]

  • 각각의 아이에 대해 , 나머지 아이들과 비교를 해야 하므로 기본적으로 2중 loop가 사용된다.
  • 또한 동시에 1학년 부터 5학년까지를 다시 각각 비교해야 하므로 loop가 한번 더 사용되어 총 3중 loop가 사용된다.
  • 그런데 나의 경우는 "각 학년별로 -> 나머지 학생들과 비교하는 순서"로 값을 비교하였으므로,
  • 루프도 각 학년에 대 한 루프가 더 바깥에 있고 -> 나머지 학생들을 반복하는 루프가 더 안쪽에 있어야 한다.
//1. 첫번째 loop는 [각각의 아이에 대한 루프]
for(int i=0; i<N; i++){
	//2. 두번째 loop는 [각 학년에 대 한 루프]
	for(int k=0; k<5; k++){
    	//3. 세번째 loop가 [나머지 학생들에 대한 루프]
    	for(int j=0; j<N; j++){
        	// 나머지 아이들 하고만 비교해야 하므로 , 자기자신과의 비교는 하지x
            if(i==j) continue;
            //이 아래에서 arr[i][k]와 arr[j][k] 값이 같으면 , 
            //i번째 Set에 j를 넣는다.
       }
     }
   }
어쨌든 이 문제는 내가 한번 제대로 실수를 했던 문제이고 , 
그래서 꼭 다시 풀어볼 필요가 있는 문제라고 생각한다.
이에 대한 나의 코드는 아래와 같다.

import java.util.*;
import java.util.stream.Collectors;

public class Main {

public static int solution(int[][] arr, int numOfChild){

    List<Set<Integer>> listOfSet = new ArrayList<>();
    for(int i=0; i<numOfChild; i++){
        listOfSet.add(new HashSet<>());
    }


    for(int i=0; i<numOfChild; i++){
        for(int k=0; k<5; k++){
            for(int j=1; j<numOfChild; j++){
                if(i==j) continue;

                if(arr[i][k] == arr[j][k]){
                    listOfSet.get(i).add(j);
                }
            }
        }
    }

    List<Integer> listOfSetSize = listOfSet.stream()
            .map(s -> s.size())
            .collect(Collectors.toList());


    Integer maxSize = listOfSetSize.stream()
            .max((e1, e2) -> e1 - e2)
            .get();

    int result = 0;
    for(int i=0; i<listOfSetSize.size(); i++){
        if(maxSize == listOfSetSize.get(i)){
            result = i;
            break;
        }
    }

    return result;
}

public static void main(String[] args) {

    //0. Scanner 준비
    Scanner sc = new Scanner(System.in);
    //1. 입력
    int numOfChild = sc.nextInt();

    int[][] arr = new int[numOfChild][5];
    for(int i=0; i<numOfChild; i++){
        for(int j=0; j<5; j++){
            arr[i][j] = sc.nextInt();
        }
    }

    //2. solution() 호출
    int result = solution(arr, numOfChild);

    //3. 결과 출력
    System.out.println(result + 1);
}

}






profile
개발자가 되고자 try 하는중

0개의 댓글