캡틴의 방 | 설명이 포함된 Hackerrank 문제 해결 방법

문제 설명

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

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

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

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

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

입력 형식
첫 번째 줄은 각 그룹의 크기인 정수 K로 구성됩니다.
두 번째 줄에는 방 번호 목록의 정렬되지 않은 요소가 포함됩니다.

출력 형식
선장의 방 번호를 출력합니다.

샘플 입력
5
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

샘플 출력
8

질문 링크: https://www.hackerrank.com/challenges/py-the-captains-room/problem

솔루션(Python3)

if __name__ == '__main__':
    k = int(input())
    rooms = list(map(int, input().split()))
    roomSet = set(rooms)
    roomSum = sum(rooms)
    roomSetSum = sum(roomSet) * k
    captiansRoom = (roomSetSum - roomSum) // (k - 1)
    print(captiansRoom)

설명

이것의 논리는 간단한 수학입니다. 모든 고유 요소가 배열에 K번 존재하는 경우 해당 합계는 고유 요소를 K번 곱한 합계가 됩니다. 그러나 한 번만 존재하는 고유한 요소가 하나 있습니다. 따라서 roomSetSum 변수의 값은 주어진 배열 요소의 실제 합계보다 클 것입니다. x라고 가정해 보겠습니다.

다른 각도에서 보면 원하는 요소를 찾을 수 있습니다. z가 한 번만 존재하지만 배열에서 k-1번 누락되었다고 가정해 봅시다. 따라서 우리는 x가 z에 k-1을 곱한 것에 불과하다는 결론을 내릴 수 있습니다. 이제 우리가 해야 할 일은 리버스 엔지니어링을 수행하고 x를 찾는 것입니다. 방 배열, 즉 모든 요소를 ​​k 번 포함하지만 단일 요소는 한 번만 포함하는 배열) k-1로 나누면 짜잔! 답을 얻었습니다.