문제 설명
혼자 노는 것을 잘하는 범희는 어느 날 방구석에 쌓인 숫자 카드를 보고 혼자 할 수 있는 재미있는 게임을 생각해 냈다.
번호가 매겨진 덱에는 총 100장의 카드가 포함되어 있으며 각 카드에는 1-100의 번호가 매겨져 있습니다.
2에서 100 사이의 자연수를 설정하고 그 수 이하의 숫자 카드를 준비하고 준비된 카드 수만큼 작은 상자를 준비하여 게임을 시작합니다.
준비된 상자에 카드를 하나씩 넣고 상자를 무작위로 섞은 다음 일렬로 배열하십시오. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 번호가 1부터 순차적으로 증가합니다.
'추천 관련글,
.jpg?type=w800 "안면거상 리프팅 탄력을 위한")
그런 다음 임의의 상자를 선택하여 선택한 상자의 숫자 카드를 봅니다.
다음으로 체크한 카드의 번호에 해당하는 상자를 열어 안에 있는 카드의 번호를 확인합니다.
마찬가지로 열려는 상자가 이미 열려 있을 때까지 해당 번호가 있는 상자를 계속 열어 두십시오.
이렇게 열린 상자는 상자 그룹 1입니다.
이제 상자 그룹 1을 따로 놓아 다른 상자와 섞이지 않도록 합니다.
상자 그룹 1 외에 남은 상자가 없으면 그대로 게임이 종료되며 이때 획득한 점수는 0점입니다.
그렇지 않은 경우 나머지 상자에서 다른 임의의 상자를 선택하고 이미 열린 상자를 만날 때까지 같은 방식으로 엽니다.
이렇게 열린 상자는 상자 그룹 2입니다.
상자 그룹 1의 상자 수에 상자 그룹 2의 상자 수를 곱하면 게임 점수가 나옵니다.
순차적인 카드 번호 배열 매개 변수로 주어진 카드로 해결 기능을 완료하여 범희가 이 게임에서 달성할 수 있는 최고 점수를 얻고 반환합니다.
제한
- 2 ≤ 카드 길이 ≤ 100
- 지도의 요소 카드 길이보다 작거나 같은 자연수.
- 지도에는 중복 요소가 없습니다.
- 카드(i) 필드 i + 1의 카드에 적힌 숫자를 의미합니다.
I/O 예시
| 카드 | 결과 |
| (8,6,3,7,2,5,1,4) | 12 |
I/O 예시 설명
1, 4, 7, 8을 포함하는 박스 그룹, 2, 5, 6을 포함하는 박스 그룹, 3을 포함하는 박스 그룹이 있습니다.
따라서 상자 3을 선택하지 않은 경우 두 시도 모두에서 3과 4를 얻고 최고 점수인 12를 얻을 수 있습니다.
설명
- 가장 이상한 설명 문제 중 하나… ㅡ.ㅡ?
- 최소한의 경우에 설명된 대로 합시다.
- 2장의 카드를 뽑았습니다.
- 그런 다음 카드는 (1, 2)이고 상자는 2입니다.
- (1, 2), (2, 1)을 섞자
- 숫자 1, 2를 입력하면 됩니다.
- 그런 다음 임의의 상자 (1) 또는 (2)를 선택하면.
- 그리고 만약 (1) 당신이 상자 (1)을 다시 열어야 한다면 그것은 불가능하다
- (2) 동일합니다.
끝.
- 그러면 (1)에서 열린 그룹이 첫 번째 상자 그룹입니다.
- (2)는 상자 2 그룹입니다.
- 섞이지 않도록 따로 보관하십시오.
- 남은 상자가 없으면 게임이 종료됩니다.
- 그러나 Box 1 그룹만 있는 경우 점수는 0점입니다.
- 남은 상자가 없으면 게임이 종료됩니다.
- 따라서 게임의 점수는 상자 그룹 1에 속하는 상자의 수와 상자 그룹 2의 화난 상자 수의 곱입니다.
- 이 게임에서 얻을 수 있는 가장 높은 점수를 찾으세요.
- 단, 상자 안의 카드 번호 순으로 배열한 것이 카드입니다.
- 카드 번호의 순서가 의미가 있습니까? 무작위 순서로 배열?
- 아… 카드가 무작위로 섞인 순서인가요?
- 하지만 그 후에 다른 상자를 선택하라는 지시를 받았습니까?
- 2장의 카드를 뽑았습니다.
- 무엇?? (ㅡ.ㅡ) 다시 사냥을 해보자…
- 입력/출력 예제에서 (8,6,3,7,2,5,1,4)는 상자에 있는 카드의 순서입니다.
- (8), (6), (3), (7), (2), (5), (1), (4) 8개의 상자가 있고,
- 랜덤으로 하나를 선택하면
- 8 -> 4 -> 7 -> 1 -> 8
- 6 -> 5 -> 2 -> 6 -> 5 …
- 3 -> 3 …
- 7 -> 1 -> 8 …
- 2 -> 6 -> 5…
- 5 -> 2 -> 6…
- 1 -> 8…
- 4 -> 7…
- 아…… 참석할 방문객이 있습니까?
- 알겠습니다.
- 입력/출력 예제에서 (8,6,3,7,2,5,1,4)는 상자에 있는 카드의 순서입니다.
- 무지가 가자를 암호화합니다!
import collections
def solution(cards):
len_cards = len(cards)
unvisited = (True) * len_cards
scores = collections.Counter()
for i in range(len_cards):
if unvisited(i) == True:
scores(i) = 0
pos = i
while True:
unvisited(pos) = False
pos = cards(pos) -1
scores(i) += 1
print(unvisited, scores, cards, pos)
if unvisited(pos) == False:
break
answer = scores.most_common(2)
answer = answer(0)(1) * answer(1)(1)
return answer
테스트 1
입력값 〉 (8, 6, 3, 7, 2, 5, 1, 4)
기댓값 〉 12
실행 결과 〉 테스트를 통과하였습니다.
출력 〉 (False, True, True, True, True, True, True, True) Counter({0: 1}) (8, 6, 3, 7, 2, 5, 1, 4) 7
(False, True, True, True, True, True, True, False) Counter({0: 2}) (8, 6, 3, 7, 2, 5, 1, 4) 3
(False, True, True, False, True, True, True, False) Counter({0: 3}) (8, 6, 3, 7, 2, 5, 1, 4) 6
(False, True, True, False, True, True, False, False) Counter({0: 4}) (8, 6, 3, 7, 2, 5, 1, 4) 0
(False, False, True, False, True, True, False, False) Counter({0: 4, 1: 1}) (8, 6, 3, 7, 2, 5, 1, 4) 5
(False, False, True, False, True, False, False, False) Counter({0: 4, 1: 2}) (8, 6, 3, 7, 2, 5, 1, 4) 4
(False, False, True, False, False, False, False, False) Counter({0: 4, 1: 3}) (8, 6, 3, 7, 2, 5, 1, 4) 1
(False, False, False, False, False, False, False, False) Counter({0: 4, 1: 3, 2: 1}) (8, 6, 3, 7, 2, 5, 1, 4) 2- 제출하다!
- 무엇? 테스트 케이스 2 실패…
정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.3MB)
테스트 2 〉 실패 (런타임 에러)
테스트 3 〉 통과 (0.04ms, 10.2MB)
테스트 4 〉 통과 (0.07ms, 10.2MB)
테스트 5 〉 통과 (0.03ms, 10.2MB)
테스트 6 〉 통과 (0.06ms, 10.1MB)
테스트 7 〉 통과 (0.05ms, 10.1MB)
테스트 8 〉 통과 (0.08ms, 10.2MB)
테스트 9 〉 통과 (0.05ms, 10.3MB)
테스트 10 〉 통과 (0.05ms, 10.1MB)- 아.. 아까 이슈글 읽을때 확인했는데 코딩을 안했네요.
- 상자 그룹이 하나만 있는 경우 0입니다.
import collections
def solution(cards):
len_cards = len(cards)
unvisited = (True) * len_cards
scores = collections.Counter()
for i in range(len_cards):
if unvisited(i) == True:
scores(i) = 0
pos = i
while True:
unvisited(pos) = False
pos = cards(pos) -1
scores(i) += 1
if unvisited(pos) == False:
break
answer = scores.most_common(2)
if len(answer) == 1:
return 0
else:
return (answer(0)(1) * answer(1)(1))
정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.1MB)
테스트 2 〉 통과 (0.06ms, 10.2MB)
테스트 3 〉 통과 (0.06ms, 10.3MB)
테스트 4 〉 통과 (0.05ms, 10.3MB)
테스트 5 〉 통과 (0.03ms, 10.2MB)
테스트 6 〉 통과 (0.06ms, 10.1MB)
테스트 7 〉 통과 (0.05ms, 10.2MB)
테스트 8 〉 통과 (0.06ms, 10.2MB)
테스트 9 〉 통과 (0.05ms, 10.2MB)
테스트 10 〉 통과 (0.09ms, 10.2MB)- 마스터의 솔루션.
- 목록만 가능할까요?
- 속도가 빠르지 않습니다.
def solution(cards):
answer = ()
for i in range(len(cards)):
tmp = ()
while cards(i) not in tmp:
tmp.append(cards(i))
i = cards(i) - 1
answer.append(() if sorted(tmp) in answer else sorted(tmp))
answer.sort(key=len)
return len(answer(-1)) * len(answer(-2))
정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.3MB)
테스트 2 〉 통과 (7.19ms, 10.1MB)
테스트 3 〉 통과 (2.24ms, 10.3MB)
테스트 4 〉 통과 (0.16ms, 10.2MB)
테스트 5 〉 통과 (0.15ms, 10.1MB)
테스트 6 〉 통과 (0.61ms, 10.1MB)
테스트 7 〉 통과 (0.14ms, 10.1MB)
테스트 8 〉 통과 (0.23ms, 10.1MB)
테스트 9 〉 통과 (0.16ms, 10.1MB)
테스트 10 〉 통과 (0.19ms, 10.3MB)- DQ를 작성하는 것이 빠릅니다.
- 정렬할 필요가 없습니다…
- Decue는 사전보다 빠릅니다.
import heapq
def solution(cards):
answer = 1
alist = ()
visit = (0)*len(cards)
for i in range(len(cards)):
cnt = 0
a = cards(i)-1
while True:
if visit(a) == 1:
break
else:
visit(a) = 1
a = cards(a)-1
cnt += 1
heapq.heappush(alist,-cnt)
a = heapq.heappop(alist)
b = heapq.heappop(alist)
answer = a*b
return answer
정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.1MB)
테스트 2 〉 통과 (0.03ms, 10.2MB)
테스트 3 〉 통과 (0.03ms, 10.2MB)
테스트 4 〉 통과 (0.05ms, 10.3MB)
테스트 5 〉 통과 (0.02ms, 10.3MB)
테스트 6 〉 통과 (0.02ms, 10.1MB)
테스트 7 〉 통과 (0.03ms, 10.2MB)
테스트 8 〉 통과 (0.03ms, 10.2MB)
테스트 9 〉 통과 (0.06ms, 10.1MB)
테스트 10 〉 통과 (0.04ms, 10.1MB)- 만약을 대비해서 while sum( ) > 0: 으로 변경했는데 그렇게 많지는 않죠?
import collections
def solution(cards):
len_cards = len(cards)
unvisited = (True) * len_cards
scores = collections.Counter()
while sum(unvisited) > 0:
i = unvisited.index(True)
scores(i) = 0
pos = i
while True:
unvisited(pos) = False
pos = cards(pos) -1
scores(i) += 1
if unvisited(pos) == False:
break
answer = scores.most_common(2)
if len(answer) == 1:
return 0
else:
return (answer(0)(1) * answer(1)(1))
정확성 테스트
테스트 1 〉 통과 (0.02ms, 9.99MB)
테스트 2 〉 통과 (0.04ms, 10.2MB)
테스트 3 〉 통과 (0.04ms, 10.2MB)
테스트 4 〉 통과 (0.06ms, 10.3MB)
테스트 5 〉 통과 (0.03ms, 10.2MB)
테스트 6 〉 통과 (0.03ms, 10.2MB)
테스트 7 〉 통과 (0.11ms, 10.2MB)
테스트 8 〉 통과 (0.14ms, 10.2MB)
테스트 9 〉 통과 (0.10ms, 10.2MB)
테스트 10 〉 통과 (0.08ms, 10.3MB)