7회차 - Probing

2022. 7. 16. 09:26·TEAM STUDY/알고리즘 코딩 테스트 스터디
목차
  1. Probing
728x90
반응형

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;
	}
}

 

728x90
반응형
저작자표시 (새창열림)

'TEAM STUDY > 알고리즘 코딩 테스트 스터디' 카테고리의 다른 글

7회차 - 수열의 순환  (0) 2022.07.16
7회차 - 최대공약수와 최소공배수  (0) 2022.07.16
7회차 - 스도쿠 보드  (0) 2022.07.16
6회차 - 알고리즘 기록 : 과유불급 (어려웠던거 다시!)  (0) 2022.07.11
6회차 - 알고리즘 기록 : 네 카드 (어려웠던거 다시!)  (0) 2022.07.09
  1. Probing
'TEAM STUDY/알고리즘 코딩 테스트 스터디' 카테고리의 다른 글
  • 7회차 - 수열의 순환
  • 7회차 - 최대공약수와 최소공배수
  • 7회차 - 스도쿠 보드
  • 6회차 - 알고리즘 기록 : 과유불급 (어려웠던거 다시!)
Binsoo
Binsoo
내 트러블 슈팅
  • Binsoo
    정수빈 기술블로그임.
    Binsoo
  • 전체
    오늘
    어제
    • 빈수 개발자 개발 일기 (932)
      • 개발중 (634)
        • Spring Boot (95)
        • Spring Security (2)
        • Spring Batch (6)
        • Spring Boot & Redis (13)
        • Java Persistence API (JPA) (28)
        • Web (42)
        • Rest Api (7)
        • Spring Concurrency Control (3)
        • Redis (8)
        • Kubernetes (k8s) (4)
        • MYSQL (35)
        • AirFlow (15)
        • Docker (2)
        • Git (22)
        • Linux (9)
        • JSON Web Tokens (JWT) (4)
        • Troubleshooting (87)
        • Swagger (0)
        • Vue.js (52)
        • Java (74)
        • html (12)
        • C (5)
        • jQuery (15)
        • JavaServer Pages (JSP) (17)
        • Arduino (1)
        • JavaScript (35)
        • Amazon Web Services (AWS) (11)
        • Algorithm (9)
        • 참고 기능 (18)
        • mongo (2)
      • PROJECT (27)
        • 스프링부트+JPA+몽고 API 개발 (3)
        • MINI (2)
        • 게시판 (3)
        • vue 프로젝트 (1)
        • JPA 사이드 프로젝트 기록 (17)
      • TEAM STUDY (156)
        • 가상 면접 사례로 배우는 대규모 시스템 설계 기초 (8)
        • 한 권으로 읽는 컴퓨터 구조와 프로그래밍 (12)
        • NAVER DEVELOPER (4)
        • LINUX (23)
        • PYTHON (19)
        • SERVER (8)
        • 알고리즘 코딩 테스트 스터디 (31)
        • 쿠버네티스 (40)
        • 대세는 쿠버네티스 [초급~중급] (11)
      • BOOK (0)
      • 자격증 (61)
        • 리눅스 1급 - 필기 기록 (19)
        • 네트워크 관리사 (2)
        • 네트워크 관리사 2급 - 실기 기록 (21)
        • 네트워크 관리사 2급 - 필기 기록 (16)
        • 정보처리 (2)
      • 직장인 대학원 (17)
        • 기록 (1)
        • 캐글 스터디 (3)
        • R (12)
  • 블로그 메뉴

    • 홈
    • 태그
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    파이썬 알고리즘
    jpa
    파이썬
    네트워크 관리사 요약
    쿠버네티스 스터디
    리눅스 마스터 1급
    알고리즘
    java
    springboot
    리눅스 마스터 1급 요약
    Git 저장소
    리눅스 마스터 1급 정리
    네트워크 관리사 2급
    REST API
    리눅스 1급 요약
    git
    redis
    네트워크 관리사 자격증
    네트워크 관리사 학점
    네트워크 관리사 2급 실기
    BackendDevelopment
    VUE
    쿠버네티스
    네트워크 관리사
    리눅스 마스터 요약
    네트워크 관리사 실기
    docker
    Spring
    스프링
    리눅스 마스터
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.4
Binsoo
7회차 - Probing

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.