[백준 알고리즘] 백준 3711번 학번 자바(JAVA)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 3711번 학번 자바(JAVA)

1) 문제번호 : 3711번

 

2) 문제 출처

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

3711번: 학번

 

2. 문제

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

 

3. 제약사항

 

4. 입력

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

 

5. 출력

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

 

6. 풀이

- 일단, 1개의 숫자가 입력 받았을 때, 가장 작은 나머지는 0이다. 즉, 1로 나눴을 때 나머지는 0이기 때문에 1을 출력한다.

- 이제 Num이 1이 아닐 경우에는 여러 숫자가 들어 오는데, m은 2부터 각 숫자를 나누면서 나머지를 리스트에 저장한다.

- 근데, 저장할 때 나머지가 리스트에 존재하면 m을 증가시켜 다시 로직을 돌고, 존재하지 않으면 리스트에 추가한다.

- 맨 마지막에, 나머지의 개수가 리스트의 개수와 같다면 서로 다른 것이므로 해당하는 m을 출력한다.

 

7. 소스 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < N; i++) {
			int Num = Integer.parseInt(br.readLine());
			
			List<Integer> list = new ArrayList<>();
			
			for(int j = 0; j < Num; j++) {
				list.add(Integer.parseInt(br.readLine()));
			}
			
            //Num이 1이면 1이 제일 작아서 1 출력
			if(Num == 1) {
				System.out.println(1);
				continue;
			}
			
			int m = 2;
			
            //Num이 1이 아닐 경우에는 2부터 리스트에 나머지가 같은게 존재하면 break
			while(true) {
				List<Integer> remainList = new ArrayList<>();
				
				for(int j = 0; j < Num; j++) {
					int temp = list.get(j) % m;
					
					if(remainList.contains(temp)) {
						break;						
					}
					
					remainList.add(temp);
				}
				
				if(remainList.size() == Num) {
					System.out.println(m);
					break;
				}
				
				m++;
			}
		}
	}
}

---