A jail has a number of prisoners and a number of treats to pass out to them.
감옥에 많은 수감자와 그들에게 무언가를 배포하는 여러 가지 방법이 있습니다
Their jailer decides the fairest way to divide the treats is to seat the prisoners around a circular table in sequentially numbered chairs.
간수가 간식을 나누어 주는 가장 공정한 방법은 일련 번호가 매겨진 의자에 원형 테이블 주위에 죄수들을 앉히는 것입니다.
A chair number will be drawn from a hat.
의자 번호는 모자에서 추출됩니다.
Beginning with the prisoner in that chair, one candy will be handed to each prisoner sequentially around the table until all have been distributed.
특정 의자에 앉은 죄수부터 시작하여 테이블을 돌아가며, 사탕이 다 떨어질 때까지 하나씩 나누어 줍니다.
The jailer is playing a little joke, though.
하지만, 간수가 장난을 칩니다.
The last piece of candy looks like all the others, but it tastes awful. Determine the chair number occupied by the prisoner who will receive that candy.
마지막 사탕은 엄청 맛이 없습니다. 어떤 의자에 앉은 사람이 마지막 사탕을 받는지 결정하세요.
For example, there are 4 prisoners and 6 pieces of candy.
예를 들어, 4명의 죄수와 6개 사탕이 있습니다.
The prisoners arrange themselves in seats numbered 1 to 4.
죄수들은 1~4가 붙인 자리에 앉습니다.
Let's suppose two is drawn from the hat.
모자에서 2가 나왔다고 가정합니다.
Prisoners receive candy at positions 2,3,4,1,2,3.
죄수들은 2,3,4,1,2,3 자리 순으로 사탕을 받습니다.
The prisoner to be warned sits in chair number 3.
3번 자리에 앉은 죄수가 마지막 사탕을 받을 걸로 경고됩니다.
Function Description
Complete the saveThePrisoner function in the editor below.
죄수를 구하는 함수를 완성하세요.
It should return an integer representing the chair number of the prisoner to warn.
이 함수는 마지막 사탕을 먹을것으로 예상되는 자리 번호를 리턴하여야 합니다.
saveThePrisoner has the following parameter(s):
죄수를 구하는 함수는 아래 인자를 가집니다.
- n: an integer, the number of prisoners / 죄수의 수
- m: an integer, the number of sweets / 사탕 수
- s: an integer, the chair number to begin passing out sweets from / 시작 좌석
Input Format
The first line contains an integer, t, denoting the number of test cases.
첫 줄은 test case가 몇번인지 알려주는 횟수로 정수입니다.
The next t lines each contain 3 space-separated integers:
두번째 줄부터는 세가지 인자가 space로 구분되어 들어 있습니다.
- n : the number of prisoners
- m : the number of sweets
- s : the chair number to start passing out treats at
sample
2
5 2 1
5 2 2
sample out
2
3
문제 해석
알고리즘 보다는 약간 수학적으로 접근 했다.
나의 접근 방식.
1. 간식 수를 죄수 숫자로 나눈 나머지를 구했다. (m%n)
- 간식 수보다 죄수 수가 많은 경우. 죄수 수의 배수 만큼의 간식은 어차피 나눠줘도 시작 좌석으로 돌아오기 때문에
시작 죄석에서 나머지 만큼만 진행한다.
2. 나머지에 시작 죄석 수를 더하고 1을 뺀다. (m%n + s -1)
- 여기까지 하면 해결한 걸로 알았다.
- test 해보니 (나머지 + 시작좌석숫자 - 1)이 죄수 수보다 큰 경우가 있다.
3. 때문에 해당 수를 죄수 수로 나누고 나머지만 남긴다. (m%n + s -1)%n
4. Test 결과 0이 나오는 케이스가 있었다.
- 0이 나오는 경우는 n을 리턴하도록 수정하였다.
최종 제출 코드
def saveThePrisoner(n, m, s):
# step1 : m%n -> 간식을 죄수로 나눈 나머지
# step2 : m%n + s - 1 -> 간식을 죄수로 나눈 나머지에서 시작 수를 더하고 1을 뺀다
# step3 : step2에서 나온 값이 죄수보다 클 경우가 있음(간식수가 죄수보다 작은 경우)
# 이를 위해 죄수 수로 나눠줌
# step4 : 단 죄수 수로 나눈 나머지가 0인 경우는 답이 n 그 자체이므로 보정해준다.
if (m%n + s -1)%n == 0:
return n
else :
return (m%n + s -1)%n
sample 예제에 없는 case들이 있어서 몇번 돌려보고 풀었다.
아래는 전체 case 예제 하나를 받아서 test하는 코드이다.
a=[[352926151,380324688,94730870],
[94431605,679262176,5284458],
[208526924,756265725,150817879],
[962975336,972576181,396355184],
[464237185,937820284,255816794],
[649320641,742902564,647542323],
[174512033,711706897,68977959],
[107283902,156676511,67149447],
[104513201,298399273,96292548],
[113378824,274011418,98103763],
[934815799,991959468,212396037],
[88325121,435452998,24617705],
[984873585,997634055,103050157],
[344218387,715364875,90658180],
[556065259,615709967,156417592],
[57109959,451440582,4188603],
[353972922,573651462,244520504],
[946486979,973168361,647886035],
[368127406,680428368,105517295],
[884634320,965112925,119757238],
[422557970,744431033,28932300],
[634954007,957414623,341366379],
[190265362,445253893,184632922],
[293315518,479153471,120684020],
[72410472,80198999,984948],
[784893322,849791807,360911386],
[846191883,880790237,510053756],
[297201660,812278057,198376746],
[945087694,999220046,465061514],
[786859800,831171414,378370933],
[528402029,859318899,224559950],
[522640531,755821672,28838424],
[864006909,879474138,806467486],
[613544440,943850900,258190755],
[734228459,928771704,265979283],
[542812502,597832172,330877768],
[541133561,748691081,126348492],
[51187317,524866691,1143193],
[885290374,990676850,373368385],
[147955933,450823700,138416059],
[100046465,587967212,32555061],
[233926824,996957988,31809378],
[785405778,835771758,689182705],
[444389615,870657324,72775880],
[702580369,895325888,345053199],
[968559651,974760313,326732084],
[299437419,514618345,254272806],
[901702945,930227426,727030891],
[721843209,736359383,225283784],
[833018320,883439261,806599246],
[267346244,307857609,46989880],
[299901304,892163356,210218436],
[565637506,795821687,158300457],
[107336562,781910357,54488503],
[513281286,916998022,254269425],
[413431205,611661371,188998419],
[740163288,938647312,571382392],
[44702121,296589002,43470596],
[771733011,919327188,317638907],
[718860003,815844769,495144331],
[377975600,438513404,111085209],
[424965480,928959619,20776133],
[234986523,732169039,205952749],
[377078343,981597420,219264561],
[612269027,791414524,580170106],
[232336090,616084008,81392003],
[75059328,274029861,53524881],
[239121359,646856043,141349731],
[923193147,943368157,206717532],
[12565064,536852817,11557940],
[360225746,970375527,284883902],
[213705306,380885426,14495860],
[659446919,699401237,73837176],
[335372713,785363124,7610828],
[538388654,859196325,110284314],
[118558760,713483972,83950807],
[896959032,961368580,8848444],
[25543240,521123082,2472730],
[258530682,935834352,194732411],
[465248213,679599042,334563499],
[331230504,637771661,76778140],
[976340152,988657462,243958260],
[552994811,922743535,540135280],
[626831986,839281366,24222267],
[157704591,253731033,59023773],
[806377559,859228114,238044289],
[838798445,996851254,268459446],
[847646888,928001503,755190846],
[877625009,999275937,874127074],
[847949466,893343194,10497830],
[35029316,784675240,8200127],
[111807455,690309882,23190325],
[355765714,554560093,311565654],
[1890615,614626804,976253],
[132293206,165429783,65360680],
[506726160,934170235,455394293],
[210041918,328800789,159203369],
[499999999,999999997,2],
[499999999,999999998,2],
[999999999,999999999,1]]
b=[[122129406],
[23525398],
[72975907],
[405956028],
[265162707],
[91803604],
[82636723],
[9258153],
[81152217],
[31978708],
[269539705],
[18445097],
[115810626],
[117586280],
[216062299],
[55859471],
[110226121],
[674567416],
[49690850],
[200235842],
[350805362],
[28872987],
[59090728],
[13206454],
[8773474],
[425809870],
[544652109],
[119049822],
[519193865],
[422682546],
[27074790],
[262019564],
[821934714],
[588497214],
[460522527],
[385897437],
[333906011],
[14136713],
[478754860],
[145371959],
[20243482],
[93060069],
[739548684],
[54653973],
[537798717],
[332932745],
[170016312],
[755555371],
[239799957],
[24001866],
[87501244],
[202677879],
[388484637],
[85042925],
[144704874],
[387228584],
[29703127],
[27144750],
[465233083],
[592129096],
[171623012],
[99804791],
[233162218],
[69626951],
[147046575],
[467740],
[27317429],
[70841696],
[226892541],
[8113004],
[174582190],
[181675979],
[113791493],
[122228525],
[431091984],
[86082218],
[73257991],
[12731011],
[96444034],
[83666114],
[52088792],
[256275569],
[356889192],
[236671646],
[155050214],
[290894843],
[426512254],
[835545460],
[118152992],
[55891557],
[22230414],
[42655476],
[154594318],
[1153181],
[98497256],
[376112207],
[67920321],
[499999999],
[1],
[999999999]]
for i,j in zip(a,b):
if (i[1]%i[0] + i[2] -1)%i[0] == j[0]:
pass
else :
print(i,j,(i[1]%i[0] + i[2] -1)%i[0])Save the Prisoner!
'개발이야기 > [Python]HackerRank' 카테고리의 다른 글
| [Hackerrank/python]Sales by Match (0) | 2020.09.24 |
|---|