Prepare > Python > Sets > The Captain's Room

The Captain's Room | HackerRank

 

문제

---

Mr. Anant Asankhya is the manager at the INFINITE hotel. The hotel has an infinite amount of rooms.

One fine day, a finite number of tourists come to stay at the hotel.
The tourists consist of:
→ A Captain.
→ An unknown group of families consisting of  K members per group where  K≠1 .

The Captain was given a separate room, and the rest were given one room per group.

Mr. Anant has an unordered list of randomly arranged room entries. The list consists of the room numbers for all of the tourists. The room numbers will appear K times per group except for the Captain's room.

Mr. Anant needs you to help him find the Captain's room number.
The total number of tourists or the total number of groups of families is not known to you.
You only know the value of K and the room number list.

 

Mr. Anant Asankhya는 INFINITE 호텔의 매니저입니다. 호텔에는 무한한 양의 객실이 있습니다.

어느 화창한 날 한정된 수의 관광객이 호텔에 묵으러 옵니다.
관광객은 다음으로 구성됩니다.
→ 캡틴.
→ K≠1 인 그룹당 K 구성원으로 구성된 알려지지 않은 가족 그룹.

캡틴에게는 별도의 방이 주어졌고 나머지는 그룹당 하나의 방이 주어졌습니다.

Anant 씨는 무작위로 배열된 방 항목의 정렬되지 않은 목록을 가지고 있습니다. 목록은 모든 관광객의 방 번호로 구성됩니다. 객실 번호는 캡틴의 방을 제외하고 그룹당 K번 나타납니다.

Anant 씨는 선장의 방 번호를 찾는 데 도움이 필요합니다.
총 관광객 수 또는 총 가족 그룹 수는 귀하에게 알려져 있지 않습니다.
K의 값과 방 번호 목록만 알고 있습니다.

 

 

=> 투숙객 방 번호로 이뤄진 목록이 있는데, 투숙객들은 구성원이 K명인 가족팀들임. 선장은 혼자 방 씀.

선장방 찾아줘

 

 

 

코드

---

a = input()
b = list(int(x) for x in input().split())

set_b = set(b)
unique_b = list(set_b)


for i in range(len(unique_b)):
    b.remove(unique_b[i])
    
print(
    sum(set_b - set(b))
)

 

 

 

 

두 번째 시도

K = int(input())  
room_numbers = list(map(int, input().split()))  


unique_rooms = set(room_numbers)  
captain_room = (sum(unique_rooms) * K - sum(room_numbers)) // (K - 1)


print(captain_room)

• 수학의 중요성
• 유니크해진 번호들의 합을 k배 한 뒤 기존 번호들의 합을 빼고 k-1로 나누면 바로 번호가 나옴

 

 

노트

---

기본아이디어

1. k=5일 때, 투숙객들은 5인가족 들이고, 선장은 1명, 따라서 선장 방 번호는 1개, 나머지 방 번호들은 5개 씩 존재

2. 각 방번호들을 하나씩만 없애주면 리스트에서 투숙객 번호들만 4개씩 남음(선장 방 번호 제거)

3. 기존 리스트의 set과 각 번호를 하나씩 없애준 리스트의 set을 비교하면 선장의 방 번호 파악 가능

(set 자료형을 활용하는 풀이....떠올린 사람은 대단하다)

 

인풋 받아오기

a = input()
b = list(int(x) for x in input().split())

print(b)
# [1, 2, 3, 6, 5, 4, 4, 2, 5, 3, 6, 1, 6, 5, 3, 2, 4, 1, 2, 5, 1, 4, 3, 6, 8, 4, 3, 1, 5, 6, 2]

• 방 번호는 중복이 필요하므로, set로 받아오면 곤란

 

 

방 번호 각각을 하나씩만 제거한 리스트

set_b = set(b)
unique_b = list(set_b)


for i in range(len(unique_b)):
    b.remove(unique_b[i])

print(unique_b)
# [1, 2, 3, 4, 5, 6, 8]

print(b) # 각 번호들을 하나씩 없애준 리스트임
# [4, 2, 5, 3, 6, 1, 6, 5, 3, 2, 4, 1, 2, 5, 1, 4, 3, 6, 4, 3, 1, 5, 6, 2]

 

 

선장 방 번호 구하기

print(
    sum(set_b - set(b))
)

• 출력시 기본 자료형이 set이므로 정수로 바꾸기 위해 sum() 사용

 

 

두 번째 시도

K = int(input())
tour_list = list(int(x) for x in input().split())

tour_set = set(tour_list)

for i in tour_set:
    tour_list.remove(i)


print(*(tour_set - set(tour_list)))

• 풀이 아이디어는 같음
• 튜플자료로 나오는 값이 한 개 뿐인걸 언패킹으로 표현한게 차이?(처음엔 sum()함수를 씀)

 

 

 

 

참조

---

https://github.com/nathan-abela/HackerRank-Solutions/blob/master/Python/04%20-%20Sets/11%20-%20The%20Captain's%20Room.py