[Java] Probing

1. 문제 설명

행운권 번호가 0 ~ (N-1)의 정수로 N개 주어진다.
모든 고객은 회원번호를 가지고 있고 자연수이다
고객은 자신의 회원번호를 N으로 나눈 나머지를 계산해 그 번호의 행운권을 받는다
행운권이 다른 사람에게 지급된 상황이라면 그것보다 +1한 번호 지급
만약 계속 +1하여 (N-1)번 행운권도 지급된 상태라면 0부터 조회
이렇게 순서대로 조회하다가 가장 먼저 발견된 아직 지급되지 않은 행운권을 지급받는다.
고객들은 순서대로 한 명씩 입장하며 한번 지급된 행운권 번호는 교환할 수 없다.

입력 형식

첫 줄에는 준비한 행운권의 수 N과 입장 할 회원의 수 M이 공백으로 구분되어 주어진다. N은 1이상 5,000이하의 자연수이며 M은 1이상 1,000이하의 자연수이다. 또한, M은 항상 N이하의 값을 가진다.

이후 총 M줄에 걸쳐서 입장 한 회원들의 회원번호가 순서대로 주어진다. 각 회원번호는 1이상 1억 이하의 자연수이다.

출력 형식

입장한 회원들의 순서대로 해당 회원이 지급받게 될 행운권 번호를 한 줄에 하나 씩 정수 형태로 출력한다.

2. 알고리즘 접근

회원번호(K)를 N으로 나눠 나머지값을 주는데 이게 중복이면 +1을 계속해서 탐색
최대값(N-1)에 없다면 0부터 탐색
그렇다면 행운권이 있는지 없는지 여부를 true / false로 구분하여 탐색

1. 티켓번호를 입력받는다
2. 티켓번호 를 n으로 나눈 행운값이 있는지 없는지 판단(배열 사용)
3. 판단에 따른 소스코드 구현

3. 알고리즘 풀이

import java.util.ArrayList;
import java.util.Scanner;

// probing 문제풀이
public class Q4B {
    public static final Scanner sc = new Scanner(System.in);
    private static ArrayList<Integer>  getTicketNumbers(int n, int m, int[] idx) {
        boolean[] used = new boolean[n]; // 이 티켓이 사용중인지 판단하는 배열 초기값은 false
        ArrayList<Integer> tickets = new ArrayList<>();

        for(int ticket : idx){ // 모든 티켓번호에 대해
            int index = ticket % n; // 회원번호를 행운권 수로 나눈 나머지값이 탐색할 인덱스이다.
            while (used[index] == true){ // 회원이 있으면 위치를 옮겨야함
                index = index + 1 % n; // 0으로 돌아가기위해 나머지 연산
            }
            tickets.add(index); // 티켓번호값 저장
            used[index] = true; // 해당 번호는 이제 없는 행운권
        }
        return tickets;
    }

    public static void main(String[] args) {
        int n = sc.nextInt(); // 행운권 수 N
        int m = sc.nextInt(); // 회원 수 M

        int[] idx = new int[m];

        for(int i = 0; i < m; i++){
            idx[i] = sc.nextInt(); // 회원번호 입력
        }

        ArrayList<Integer> tickets = getTicketNumbers(n, m, idx);

        for(int ticket : tickets){
            System.out.println(ticket);
        }
    }
}