링크 : https://school.programmers.co.kr/learn/courses/30/lessons/131130
문제 설명
각각 1부터 n까지 숫자가 차례대로 적혀있는 카드가 있고, 카드들은 각각의 상자 속에 1장씩 있습니다. (1card -> 1box)
게임의 룰은 다음과 같습니다.
1. 임의의 상자를 선택하여 선택한 상자 안에 숫자 카드를 확인할 수 있습니다.
2. 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다.
3. 2번 과정을 열어야 하는 상자가 이미 열려있을 때까지 반복합니다. 이렇게 연 상자들은 1번 상자 그룹니다.
4. 1번 상자 그룹을 제외하고 남는 상자가 없다면 게임이 종료되며, 이때 획득하는 점수는 0점입니다.
5. 그렇지 않다면 다시 1~3과정을 반복하여 더이상 남은 상자가 없을 때까지 2, 3 ,... i번 상자그룹을 만듭니다.
6. 게임이 종료되며 가장 긴 상자 그룹 2개의 길이를 곱한 값이 점수가 됩니다.
제한조건
상자, 카드 개수 : 2~100
카드의 원소는 카드의 길이 이하인 임의의 자연수입니다.
카드에는 중복되는 원소가 존재하지 않습니다.
예시 : [8,6,3,7,2,5,1,4] > 결과 : 12점. ((1,4,7,8), (2,5,6), (3)) 총 3개의 상자그룹이 생기고, 가장 긴 길이 2개는 4*3
코드
def solution(cards):
groups = []
opend = set()
for card in cards:
if card in opend:
continue
opend.add(card)
group = set([card])
next = card-1
while cards[next] not in group:
group.add(cards[next])
opend.add(cards[next])
next = cards[next]-1
groups.append(group)
groups.sort(key = lambda x: -len(x))
answer = len(groups[0]) * len(groups[1]) if len(groups) > 1 else 0
return answer
아이디어
1. 상자를 앞에서부터 하나씩 확인하며 만약에 이미 열은 상자라면 건너뛴다.
2. 처음 열어보는 상자라면, 그룹을 하나 만들고 상자 속 카드 번호에 맞는 상자를 하나씩 계속 열어가며, 그룹에 추가한다.
3. 만약에 다음 상자가 이미 그룹에 속한 상자라면 1바퀴 돌게 된 것이니 2번 과정을 종료하고 그룹을 기록해준다.
4. 1~3과정을 반복한 후, 기록해놓은 그룹을 내림차순으로 정렬하고 가장 앞에 두 그룹의 길이를 곱하면 점수가 나온다.
'알고리즘' 카테고리의 다른 글
백준 - 부분합 (0) | 2023.01.09 |
---|---|
백준 - RGB거리 (0) | 2022.12.20 |
프로그래머스 - 모두 0으로 만들기 (0) | 2022.12.19 |
프로그래머스 - 오픈채팅방 (0) | 2022.12.17 |
프로그래머스 - 길 찾기 게임 (0) | 2022.12.15 |