백준 3711번 JAVA 풀이 - 학번

문제 링크 - https://www.acmicpc.net/problem/3711

3711번: 학번

문제

Z 대학교 학생은 입학할 때 학번을 받게 된다. 학번은 0보다 크거나 같고, 106-1보다 작거나 같은 정수이다. Z 대학의 김상근 교수는 학번으로 학생들을 구분한다. 상근이는 학생들을 조금 더 쉽게 기억하기 위해서 자신이 가르치는 학생들의 학번을 m으로 나누었을 때, 나머지가 모두 다른 가장 작은 양의 정수를 찾으려고 한다.

입력

첫째 줄에 테스트 케이스의 개수 N이 주어진다. 각 테스트 케이스의 첫째 줄에는 상근이가 가르치는 학생의 수 G가 (1 ≤ G ≤ 300) 주어진다. 다음 G개 줄에는 학생의 학번이 한 줄에 하나씩 주어진다. 학번이 같은 경우는 없다.

출력

각 테스트 케이스마다, 학번을 m으로 나눈 나머지가 모두 다른 가장 작은 정수 m을 출력한다.

 

 

# 문제 풀이

1. 테스트 케이스를 입력받은 후 학생 수를 입력 받는다. 

입력받은 학생 수만큼 LIST에 담은 후 checkQ 함수를 호출하여 각 학번별로 나머지를 파악한다.

for(int i = 0; i < testCase; i++){
	int studentNum = sc.nextInt();

	List<Integer> list = new ArrayList<>();  

	for(int j = 0; j < studentNum; j++){
		list.add(sc.nextInt());
	}

	System.out.println(checkQ(list));
}

 

2. checkQ 함수

해당 함수는 학번 리스트를 인자로 받으며 리스트가 1이면 1을 리턴 1이 아닐경우 2부터 나누기를 시작한다.

if(list.size() == 1) return 1;

int answer = 2;

 

3. 나머지를 담을 리스트를 선언, 나눈 나머지가 매열에 있다면 반복문을 종료, 없다면 추가해준다.

List<Integer> reList = new ArrayList<>();
            
for(int i = 0; i < list.size(); i ++){
	int temp = list.get(i) % answer;

	if(reList.contains(temp)){
		break;
	}

	reList.add(temp);
}

 

4. 나머지를 담은 배열과 학번 리스트의 크기가 같다면 모든 학번을 나눴을 때 나머지가 다르다는 의미이기 때문에 answer를 리턴하며 프로그램을 종료한다.

if(reList.size() == list.size()){
	return answer;
}

 

# 전체코드

import java.util.*;

public class Main_3711{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int testCase = sc.nextInt();

        for(int i = 0; i < testCase; i++){
            int studentNum = sc.nextInt();

            List<Integer> list = new ArrayList<>();  

            for(int j = 0; j < studentNum; j++){
                list.add(sc.nextInt());
            }

            System.out.println(checkQ(list));
        }
    }

    static int checkQ(List<Integer> list){
        
        if(list.size() == 1) return 1;

        int answer = 2;

        while(true){
            List<Integer> reList = new ArrayList<>();
            
            for(int i = 0; i < list.size(); i ++){
                int temp = list.get(i) % answer;

                if(reList.contains(temp)){
                    break;
                }

                reList.add(temp);
            }

            if(reList.size() == list.size()){
                return answer;
            }
            answer++;
        }
    }
}