7회차 - Probing

---

Probing

 

 행사 기획자인 수정이는 이 번에 자신이 담당하게 된 행사에서 행운권 추첨을 기획하고 있다.

이번 행사에서는 최대 수천명 정도의 사람이 방문할 수 있기 때문에 어떻게 하면 공평하고 불규칙적으로 행운권 번호를 배정할 수 있을지가 큰 관건이었다.

하지만 똑똑한 수정이는 아래와 같은 아이디어를 냈다.

• 모든 행운권 번호는 0~(N-1)의 정수로 총 N개이다.
• 모든 고객은 회원번호를 가지고 있으며 회원 번호는 자연수이다.
• 입장한 고객은 자신의 회원 번호를 N으로 나눈 나머지를 계산해 그 번호와 같은 행운권을 지급받는다.
• 고객들은 순서대로 한 명씩 입장하며 한번 지급된 행운권 번호는 교환할 수 없다.

 

 

<N=5000일 때 행운권 번호를 지급받는 예시>

 

 수정이는 행사 중간에도 바쁠 예정이기에 당신에게 이를 자동화할 수 있는 프로그램을 작성해달라고 요청했다. 수정이를 도와주자. 

 

입력 형식

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

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

 

출력 형식

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

---

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


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	/**
	 *
	 * @param n     전체 티켓의 수
	 * @param m     요청 고객의 수
	 * @param ids   각 고객들의 회원번호
	 * @return
	 */
	public static ArrayList<Integer> getTicketNumbers(int n, int m, int[] ids)
	{
		ArrayList<Integer> tickets = new ArrayList<>();

		TicketTable table = new TicketTable(n);

		for(int ticket : ids)
		{
			int ticketIndex = table
.findEmptyIndexByUserId(ticket);
			
			tickets.add(ticketIndex);
			
			table.setUsed(ticketIndex, true);

		}
		return tickets;
	}

	public static void main(String[] args) throws Exception {
		int n = scanner.nextInt(); // 전체 티켓의 수
		int m = scanner.nextInt(); // 요청 고객의 수

		int[] ids = new int[m];

		for(int i = 0 ; i < m ; i ++)
		{
			ids[i] = scanner.nextInt();
		}

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

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

}


class TicketTable
{
	private final boolean[] used;
	public final int length;

	public TicketTable(int length)
	{
		this.length = length;
		this.used = new boolean[length];
	}

	/**
	 * 사용자의 회원 번호로 지급받게 될 행운권 번호를 계산하는 메소드
	 */
	public int findEmptyIndexByUserId(int userId)
	{
		int index = userId % length;
		
		while(isUsed(index)){
			index = (index + 1) % length;
		}
		
		return index;
	}

	/**
	 * 해당 행운권 번호가 이미 사용 중인지 여부를 반환하는 메소드
	 */
	public boolean isUsed(int ticketIndex)
	{
		return used[ticketIndex];
	}

	/**
	 *  티켓 사용 여부를 갱신하기 위한 메소드
	 */
	public void setUsed(int index, boolean status)
	{
		used[index] = status;
	}
}

---