코딩테스트 9일차(2025.01.23) - 혼자 놀기의 달인(프로그래머스)

내 풀이

1~100까지 숫자가 하나씩 적혀있음

 

2이상 100 이하의 자연수 하나 정해 카드 준비

준비한 카드 수만큼 작은 상자를 준비

 

게임 방법:

준비된 상자에 카드 한 장씩 넣고, 상자 무작위로 섞음 -> 일렬로 나열 후 1번부터 번호붙힘

1. 상자를 선택, 숫자카드 확인2. 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자 확인3. 계속해서 해야함4. 열어야 하는 상자가 이미 열려있을 때까지 반복

 

5. 만약 1번 상자를 열었다고 가정하자. 1번 상자를 제외하고 남는 상자가 없으면그대로 게임이 종료되며 이때 희득하는 점수는 0점

 

그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 떄까지 상자를 연다.

 

1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수

 

문제: 상자안에 들어있는 카드 번호가 순서대로 감긴 배역 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return하도록 solution함수를 완성하기

def solution(cards):
    answer = 4 * (len(cards) - 5)
    return answer

결과: 틀림

정답

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. 초기설정

def solution(cards):
    answer = []

 

• cards: 주어진 카드 배열로, 각 값은 다음 상자의 위치를 나타낸다.
• answer: 각 순환 그룹을 저장할 리스트다. 그룹은 중복 없이 저장된다.

2. 외부 반복문으로 각 카드에서 그룹 생성

for i in range(len(cards)):
    tmp = []

 

• for i in range(len(cards)): 모든 카드 위치를 시작점으로 하여 그룹을 탐색한다. 
• tmp: 현제 그룹의 상자 번호를 저장하는 임시 리스트

3. 순환 그룹 탐색 (while 루프)

while cards[i] not in tmp:
    tmp.append(cards[i])
    i = cards[i] - 1

• while cards[i] not in tmp: 현제 상자가 이미 탐색한 그룹에 포함되지 않았을 때 계속 탐색함
• tmp.append(cards[i]): 현재 상자를 그룹에 추가함
• i = card[i] - 1: 현재 카드가 가리키는 다음 상자의 인덱스로 이동함

이 과정은 순환 구조를 탐색하며, 반복이 종료되면 tmp에는 하나의 순환 그룹이 저장된다. 

 

4. 중복 그룹 제거

answer.append([] if sorted(tmp) in answer else sorted(tmp))

• sorted(tmp): 그룹을 정렬하여 중복된 그룹을 탐지할 수 있도록 한다. (정렬은 [1,8,4,7]과 [7,4,8,1]을 동일한 그룹으로 인식하게 한다.)
• if sorted(tmp) in answer: 이미 탐색된 그룹이라면 빈 리스트([])를 추가하여 중복을 방지한다.
• answer.append(...): 중복되지 않는 경우에만 그룹을 추가한다. 

 

5. 그룹 정렬 및 최대 점수 계산

answer.sort(key=len)
return len(answer[-1]) * len(answer[-2])

• answer.sort(key=len): 그룹을 크기 순으로 정렬함
• 가장 큰 그룹은 마지막 (answer[-1]), 두 번째로 큰 그룹은 answer[-2]에 위치하게 된다.
• len(answer[-1] * len(answer[-2]): 두 그룹 크기의 곱(점수)을 변환한다. 

틀린 이유

처음에는 곱하기를 활용하는 것이 점수를 최대화할 수 있는 방법이라고 생각했다. 따라서, 하나의 실수가 반드시 있어야 한다고 가정하고, 8개의 카드를 사용할 때는 1개의 실수를 제외한 7개의 카드만 고려하는 방식으로 접근했다.

 

초기 접근 방식

처음에는 "4 X n" 형태의 계산이 최고의 점수를 만들 수 있을 것이라고 판단했다. 예를 들어,

• 8개의 카드:
  4 X 3 = 12점
• 9개의 카드:
  5 X 4 = 20점
• 10개의 카드:
  6 X 4 = 24점

이러한 계산을 통해 각 경우에서 최대 점수를 만들 수 있다고 생각했다.

 

문제점 발견

하지만, 마지막에는 각 카드가 반드시 연속하는 숫자일 필요가 없고, 불연속한 숫자로도 점수를 만들 수 있다는 가능성을 인지했다. 그러나 이를 활용하는 방법을 떠올리지 못했고, 연속된 수만을 사용한 초기 전략에 머물렀다.

 

하지만, 이 방법은 순화 탐색 알고리즘과 완전 탐색 알고리즘이 필요한 문제였다. 

고찰

순환 탐색 알고리즘이란?

순환 탐색 알고리즘은 데이터가 순환 구조(Loop)를 이루고 있는 경우, 특정 규칙에 따라 시작점에서 이동하며 반복되는 패턴(순환)을 탐지하고 이를 탐색하는 알고리즘이다.

이는 순환 그래프나 연결 리스트에서 자주 나타나며, 방문한 노드를 추적하거나 루프 종료 조건을 설정하여 순환 그룹을 찾는다.

 

완전 탐색 (Brute Force)알고리즘이란?

완전 탐색(Brute Force) 알고리즘은 모든 가능한 경우의 수를 탐색하여 정답을 찾는 방법이다. 최적화보다는 모든 경우를 다 시도하며, 조건에 부합하는 해를 찾거나 최댓값/최솟값을 계산한다.

 

순환 탐색 알고리즘과 완전 탐색 알고리즘을 공부해야겠다는 생각이들었다.