본문 바로가기
Java/Java 알고리즘 인프런

[Ch.02 - Array] 11. 임시반장 정하기

앤 썸 2022. 5. 19. 13:05
반응형
11. 임시반장 정하기
 

설명

김갑동 선생님은 올해 6학년 1반 담임을 맡게 되었다.

김갑동 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다.

그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다.

그래서 김갑동 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다.

예를 들어 학생 수가 5명일 때의 표를 살펴보자.

위 경우에 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며,

2번 학생과는 4학년 때 같은 반이었음을 알 수 있다. 그러므로 이 학급에서 4번 학생과 한번이라도

같은 반이었던 사람은 2번 학생, 3번 학생과 5번 학생으로 모두 3명이다.

이 예에서 4번 학생이 전체 학생 중에서 같은 반이었던 학생 수가 제일 많으므로 임시 반장이 된다.

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

입력

첫째 줄에는 반의 학생 수를 나타내는 정수가 주어진다. 학생 수는 3 이상 1000 이하이다.

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

주어지는 정수는 모두 1 이상 9 이하의 정수이다.

출력

첫 줄에 임시 반장으로 정해진 학생의 번호를 출력한다.

단, 임시 반장이 될 수 있는 학생이 여러 명인 경우에는 그 중 가장 작은 번호만 출력한다.

예시 입력 1 

5
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

예시 출력 1

4
import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int[][] arr =new int[n][5];
    for(int i=0;i<n;i++){
      for(int j=0;j<5;j++){
        arr[i][j]=in.nextInt();
      }
    }
    System.out.println(solution(n, arr));
  }
  static int solution(int n, int[][]arr){
    int result=Integer.MIN_VALUE;
    //단, 임시 반장이 될 수 있는 학생이 여러 명인 경우에는 그 중 가장 작은 번호만 출력한다.
    int[][] answer= new int[n][n];
    //각 학생별로 다른 학생과 같은 반이었는지 확인하는 배열 -> 0이면 같은 반인적 없음, 1이면 같은 반 인적 있음
    for(int i=0;i<n;i++){
      //번호
      for(int j=0;j<5;j++){
        //학년
        for(int k=0;k<n;k++){
          //같은 반
        	if(arr[i][j]==arr[k][j] && answer[i][k]==0) answer[i][k]=1; 
           }
      }
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        //System.out.print(answer[i][j]+" ");
      }
      //System.out.println();
    }
    int last=0;
    int tmp2=0;
    for(int i=n-1;i>=0;i--){
      int tmp=0;
      for(int j=0;j<n;j++){
        if(answer[i][j]==1) tmp++;
        if(tmp>=tmp2){
          last=i;
          tmp2=tmp;
        }
      }
    }
    return last+1;
  }
}

 

package string.ch01;

import java.util.Scanner;
  
public class asdf {
  public int [] solution(int[][] arr, int n){
    int [] answer=new int[n];
    int same=0;
    int tmp =0;
    
    for(int i=0;i<5;i++){
      tmp=0;
      for(int j=0;j<n;j++){
        for(int k=0;k<n;k++){
         if(j!=k&&arr[j][i]==arr[k][i])
           answer[j]++;
          }
      }
    }
    return answer;
  }
  public static void main(String[] args){
    asdf T=new asdf();
    Scanner kb=new Scanner(System.in);
    int n = kb.nextInt();
    int[][] arr = new int[n][5];
    for(int i=0;i<n;i++){
      for(int j=0;j<5;j++){
        arr[i][j]=kb.nextInt();
      }
    }
    int [] result=T.solution(arr,n);
    int max=0;
    int answer=Integer.MAX_VALUE;
    
    for(int i=0;i<n;i++){
      if(result [i] >max){
        max=result[i];
        answer=i;
      }
    }
    System.out.println(answer+1);
  }
}

 

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Scanner;

public class Main {
	public int solution(int n, int[][] arr) {
		LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
		int cnt = 0;
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < n; j++) {
				int tmp = arr[j][i];
				for (int k = 0; k < n; k++) {
					if (k != j)
						if (tmp == arr[k][i])
							cnt++;
				}
				map.put(j, map.getOrDefault(j, 0) + cnt);
				cnt = 0;
			}
		}
		int answer = 0;
		Iterator<Integer> it = map.keySet().iterator();
		int max = Integer.MIN_VALUE;

		while (it.hasNext()) {
			int key = it.next();
			if (max < map.get(key)) {
				max = Math.max(max, map.get(key));
				answer = key;
			}
		}

		return answer + 1;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[][] arr = new int[n][5];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < 5; j++)
				arr[i][j] = kb.nextInt();

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

 

-> 같은 반이었던 학생이 가장 많은 학생

 

 

-> 같은 반이었던 학생이 가장 많은 학생이 아니라 한번이라도 같은 반이었던 학생이 많은 학생

import java.util.Scanner;
  
public class Main {
  public int solution(int n, int[][]arr){
    int [] [] answer=new int [n][n];
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        for(int k=0;k<n;k++){
          if(j!=k&&arr[j][i]==arr[k][i] && answer[j][k]==0){
            answer[j][k]=1;
          }
        }
      }
    }
    
    int tmp=0;
    int max=0;
    int X=0;
    for(int i=0;i<n;i++){
    	tmp=0;
        for(int j=0;j<n;j++){
        	if(answer[i][j]==1)
        		tmp++;
        }
        if(tmp>max) {
        	max=tmp;
        	X=i;
        }
    }
    return X+1;
  }
  public static void main(String[] args){
    Main T = new Main();
    Scanner kb=new Scanner(System.in);
    int n = kb.nextInt();
    int [][] arr = new int[n][5];
    for(int i=0;i<n;i++){
      for(int j=0;j<5;j++){
        arr[i][j]=kb.nextInt();
      }
    }
    System.out.println(T.solution(n, arr));
    
   
  }
}

-> 2가지 테스트케이스는 통과하는데 나머지 테스트케이스에서 런타임 오류 발생

-> 원인 : for문의 인덱스 범위 초과

 

 

import java.util.Scanner;
  
public class Main {
  public int solution(int n, int[][]arr){
    int [] [] answer=new int [n][n];
    for(int i=0;i<5;i++){
      for(int j=0;j<n;j++){
        for(int k=0;k<n;k++){
          if(j!=k&&arr[j][i]==arr[k][i] && answer[j][k]==0){
            answer[j][k]=1;
          }
        }
      }
    }
    
    int tmp=0;
    int max=0;
    int X=0;
    for(int i=0;i<n;i++){
    	tmp=0;
        for(int j=0;j<n;j++){
        	if(answer[i][j]==1)
        		tmp++;
        }
        if(tmp>max) {
        	max=tmp;
        	X=i;
        }
    }
    return X+1;
  }
  public static void main(String[] args){
    Main T = new Main();
    Scanner kb=new Scanner(System.in);
    int n = kb.nextInt();
    int [][] arr = new int[n][5];
    for(int i=0;i<n;i++){
      for(int j=0;j<5;j++){
        arr[i][j]=kb.nextInt();
      }
    }
    System.out.println(T.solution(n, arr));
    
   
  }
}

 

#같은 반인 친구가 많은 사람

(1) 같은 반이었던 친구가 몇명인지 구할 대상 반복문

(2) 같은 반인 친구를 찾을 대상 반복문

(3) 학년 반복문

 

1.  같은 반 횟수를 배열에 넣는다.

2. 같은 반 한번 된 친구의 경우에는, 건너뛰기 위해서 break;

3. 배열 중 가장 큰 값의 인덱스를 값으로 한다. [단, 같은 값이 존재할 경우 작은 인덱스]

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n= in.nextInt();
    int[][] arr = new int[n+1][6];
    for(int i=1;i<=n;i++){
      for(int j=1;j<=5;j++){
        arr[i][j]=in.nextInt();
      }
    }
    System.out.println(solution(n, arr));
  }
  static int solution(int n, int[][] arr){
    int[] answer = new int[n+1];
      for(int i=1;i<=n;i++){
        for(int k=1;k<=n;k++){
		   for(int j=1;j<=5;j++){
            if(arr[i][j]==arr[k][j]){
              answer[i]+=1;
              break;
            }
        }
      }
    }
    int max=0;
    int result=0;
    for(int i=1;i<=n;i++) 
      if(answer[i]>max){
        max=answer[i];
          result=i;
    }
    
    return result;
  }
}

 

+)세련된 풀이

import java.util.*;

class Main {
	public int solution(int n, int[][] arr) {
		int answer = 0, max = 0;
		for (int i = 1; i <= n; i++) {
			int cnt = 0;
			for (int j = 1; j <= n; j++) {
				for (int k = 1; k <= 5; k++) {
					if (arr[i][k] == arr[j][k]) {
						cnt++;
						break;
					}
				}
			}
			if (cnt > max) {
				max = cnt;
				answer = i;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[][] arr = new int[n + 1][6];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= 5; j++) {
				arr[i][j] = kb.nextInt();
			}
		}
		System.out.print(T.solution(n, arr));
	}
}

 

# 같은 반인 친구가 많은 인덱스 구하기

1. for문을 0부터

    int last=0;
    int tmp2=0;
    for(int i=0;i<n;i++){
      int tmp=0;
      for(int j=0;j<n;j++){
        if(answer[i][j]==1) tmp++;
        if(tmp>tmp2){
          last=i;
          tmp2=tmp;
        }
      }
    }

2. for문을 뒤에서 부터

    int last=0;
    int tmp2=0;
    for(int i=n-1;i>=0;i--){
      int tmp=0;
      for(int j=0;j<n;j++){
        if(answer[i][j]==1) tmp++;
        if(tmp>=tmp2){
          last=i;
          tmp2=tmp;
        }
      }
    }

3. 간단하게 -> 새로운 배열을 만들지 않고 구현

int answer = 0, max = 0;
for (int i = 1; i <= n; i++) {
    int cnt = 0;
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= 5; k++) {
            if (arr[i][k] == arr[j][k]) {
                cnt++;
                break;
            }
        }
    }
    if (cnt > max) {
        max = cnt;
        answer = i;
    }

 

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    //5학년까지 n명 학생
    int n=in.nextInt();
    int[][] arr = new int[n+1][5];
    for(int i=1;i<=n;i++){
      for(int j=0;j<5;j++){
        arr[i][j]=in.nextInt();
      }
    }
    int [][] answer= new int[n+1][n+1];
    //같은 반이었던 친구가 가장 많은 학생  
    for(int i=1;i<=n;i++){
      for(int j=0;j<5;j++){
        for(int k=1; k<=n;k++){
          if(arr[i][j]==arr[k][j]) answer[i][k]=1;
        }
      }
    }
    
    //같은 반이면 2차원 배열에 1로 저장
    int[] result=new int[n+1];
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        if(answer[i][j]==1) result[i]+=1;
      }
    }
    int max=0;
    int number=0;
    //1로 저장한 카운트가 가장 많은 학생 리턴
    for(int i=1;i<=n;i++){
      if(max<result[i]) {
        max=result[i];
        number=i;
      }
    }
    System.out.println(number);
  }
}

-> 같은 반인적이 있으면 break 후, 다음 학생 확인해 cnt++, cnt와 max를 이용해 answer에 해당 학생 번호 저장

 

확인할 학생번호:i

같은반 학생번호:j

학년 번호 :k

-> 같은반일 학생번호 기준 돌면서 해당 학년에 같은반이었으면 break이후, 다음 학생부터 진행하면서 cnt++

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    int[][] arr = new int[n+1][5];
    for(int i=1;i<=n;i++){
      for(int j=0;j<5;j++){
        arr[i][j]=in.nextInt();
      }
    }
    int answer=0;
    int max=0;
    //같은 반이었던 친구가 가장 많은 학생  
    for(int i=1;i<=n;i++){
      int cnt=0;
        for(int k=1; k<=n;k++){
         for(int j=0;j<5;j++){
          if(arr[i][j]==arr[k][j]){
            cnt++;
            break;
          }
        }
        if(cnt>max){
          max=cnt;
          answer=i;
        }
      }
    }
    System.out.println(answer);
  }
}
반응형
저작자표시 비영리

'Java > Java 알고리즘 인프런' 카테고리의 다른 글

[Ch.03 - 투 포인터] 1. 두 배열 합치기  (0) 2022.05.19
[Ch.02 - Array] 12. 멘토링  (0) 2022.05.19
[Ch.02 - Array] 10. 봉우리  (0) 2022.05.18
[Ch.02 - Array] 09. 격자판 최대합 (+ list, Math.max, 리팩토링) #  (0) 2022.05.18
[Ch.02 - Array] 08. 등수 구하기 (+ Arrays.sort와 fill)  (0) 2022.05.18

'Java/Java 알고리즘 인프런' Related Articles

티스토리툴바