문제 요약
상자에는 1부터 N까지의 숫자가 하나씩 적힌 카드가 무작위로 들어 있다.
어떤 상자를 열면 카드에 적힌 번호의 상자를 다음으로 열어야 한다.
이미 열었던 상자를 다시 열려고 하면 하나의 상자 그룹이 완성된다.
첫 번째 그룹과 겹치지 않는 상자들 중 하나를 선택해 두 번째 그룹을 만들고, 두 그룹의 크기를 곱한 값이 점수다.
만들 수 있는 점수의 최댓값을 구해야 한다.
핵심 아이디어
상자 번호를 1부터 N까지로 생각하자.
각 상자는 카드에 적힌 숫자에 해당하는 다음 상자를 하나만 가리킨다.
상자 i -> cards[i]번 상자모든 카드 번호가 중복되지 않고 1부터 N까지 한 번씩 등장하므로, 전체 상자 구조는 여러 개의 서로 겹치지 않는 사이클로 나뉜다.
예를 들어 다음 카드 배열을 생각해보자.
cards = [8, 6, 3, 7, 2, 5, 1, 4]1번 상자에서 시작하면 다음과 같이 이동한다.
1 -> 8 -> 4 -> 7 -> 1이렇게 만들어진 상자 그룹은 크기가 4인 하나의 사이클이다.
게임의 두 그룹은 서로 다른 사이클 두 개를 선택하는 것과 같다.
따라서 모든 사이클의 크기를 구한 뒤, 가장 큰 두 크기를 곱하면 최고 점수를 얻을 수 있다.
방문 배열
한 상자가 어느 그룹에 포함되었는지 확인하기 위해 방문 배열을 사용한다.
visited = [False] * len(cards)이미 방문한 상자에서 다시 시작하면 같은 사이클을 중복해서 계산하게 된다.
따라서 아직 방문하지 않은 상자에서만 새로운 그룹 탐색을 시작한다.
if visited[start]:
continue카드 번호와 배열 인덱스
상자 번호와 카드 번호는 1부터 시작하지만 파이썬 리스트의 인덱스는 0부터 시작한다.
현재 상자의 카드 번호가 cards[current]일 때, 다음 상자의 인덱스는 다음과 같다.
current = cards[current] - 1예를 들어 카드에 8이 적혀 있다면 8번 상자를 열어야 한다.
리스트에서는 8번 상자가 인덱스 7이므로 1을 뺀다.
사이클 크기 구하기
방문하지 않은 상자에서 시작한다.
current = start
group_size = 0현재 상자를 방문 처리하고 다음 상자로 이동한다.
while not visited[current]:
visited[current] = True
group_size += 1
current = cards[current] - 1이미 방문한 상자를 만나면 현재 그룹의 탐색을 종료한다.
입력이 순열이므로 새로운 탐색은 이전 그룹으로 들어가지 않고 반드시 자기 자신의 시작 그룹으로 돌아온다.
계산한 그룹 크기를 배열에 추가한다.
group_sizes.append(group_size)가장 큰 두 그룹 선택
모든 그룹의 크기를 구한 뒤 내림차순으로 정렬한다.
group_sizes.sort(reverse=True)그룹이 두 개 이상이면 가장 큰 두 크기를 곱한다.
return group_sizes[0] * group_sizes[1]전체 상자가 하나의 사이클이면 두 번째 그룹을 만들 수 없다.
이 경우 점수는 0이다.
if len(group_sizes) < 2:
return 0풀이 과정
- 각 상자의 방문 여부를 저장할 배열을 만든다.
- 모든 상자를 순회한다.
- 방문하지 않은 상자에서 카드 번호를 따라 이동한다.
- 이미 방문한 상자를 만날 때까지 그룹 크기를 센다.
- 모든 그룹 크기를 내림차순으로 정렬한다.
- 가장 큰 두 그룹의 크기를 곱해 반환한다.
Python 코드
def solution(cards):
box_count = len(cards)
visited = [False] * box_count
group_sizes = []
# 방문하지 않은 상자에서 새로운 그룹을 찾는다.
for start in range(box_count):
if visited[start]:
continue
current = start
group_size = 0
# 카드 번호가 가리키는 다음 상자를 따라간다.
while not visited[current]:
visited[current] = True
group_size += 1
current = cards[current] - 1
group_sizes.append(group_size)
group_sizes.sort(reverse=True)
# 전체 상자가 하나의 그룹이면 두 번째 그룹을 만들 수 없다.
if len(group_sizes) < 2:
return 0
return group_sizes[0] * group_sizes[1]코드 설명
visited
visited = [False] * box_count상자가 이미 어느 그룹에 포함되었는지 기록한다.
한 번 찾은 사이클의 모든 상자는 다시 확인할 필요가 없다.
current
current = cards[current] - 1현재 상자 안의 카드 번호가 가리키는 다음 상자로 이동한다.
카드 번호는 1부터 시작하므로 파이썬 인덱스로 바꾸기 위해 1을 뺀다.
while 조건
while not visited[current]:아직 열지 않은 상자라면 계속 열고, 이미 열었던 상자를 만나면 해당 그룹 탐색을 끝낸다.
정렬
group_sizes.sort(reverse=True)최대 점수는 가장 큰 두 그룹을 선택했을 때 만들어진다.
따라서 내림차순 정렬 후 첫 번째와 두 번째 값을 곱하면 된다.
예시
다음 입력을 살펴보자.
cards = [8, 6, 3, 7, 2, 5, 1, 4]상자 그룹은 다음과 같이 나뉜다.
1 -> 8 -> 4 -> 7 -> 1
그룹 크기: 4
2 -> 6 -> 5 -> 2
그룹 크기: 3
3 -> 3
그룹 크기: 1가장 큰 두 그룹의 크기는 4와 3이다.
4 x 3 = 12따라서 정답은 12다.
시간 복잡도
상자의 개수를 N이라고 하자.
각 상자는 전체 탐색 과정에서 한 번만 방문한다.
O(N)그룹 크기 배열을 정렬하는 비용은 O(N log N)이지만, 이 문제에서는 N이 최대 100이므로 충분히 빠르다.
공간 복잡도
방문 배열과 그룹 크기 배열을 사용한다.
O(N)정리
이 문제는 카드 번호가 다음 상자를 가리키는 순열에서 사이클의 크기를 구하는 문제다.
방문하지 않은 상자에서 시작
카드 번호를 따라 다음 상자로 이동
이미 방문한 상자를 만날 때까지 그룹 크기 계산
모든 그룹 크기 수집
가장 큰 두 그룹의 크기를 곱해 반환상자 그룹은 서로 겹치지 않는 사이클이라는 점을 파악하고, 각 상자를 한 번만 방문하는 것이 핵심이다.
