[Algorithm] 혼자 놀기의 달인 ( Programmers - JavaScript, Python )

문제 설명

혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.

 

숫자 카드 더메에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준바힌 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.

 

준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.

 

그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.

 

이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.

 

그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.

 

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

 

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

 

 

 

---

 

 

 

제한사항

 

 

 

 

---

 

 

 

입출력 예

 

 

 

 

---

 

 

 

입출력 예 설명

1, 4, 7, 8이 속하는 상자의 그룹과 2, 5, 6이 속하는 상자의 그룹과 3이 혹하는 상자의 그룹이 존재합니다. 따라서 3번 상자를 고르지 않았을 때, 두 번의 시행에서 3과 4를 기록하며 최고 점수 12를 얻을 수 있습니다.

 

 

 

---

 

 

 

문제 풀이

[ 혼자 놀기의 달인 ]의 문제를 풀기 위해서는 테이블과 내가 어떤 박스를 열었는지를 확인할 수 있는 openBox 배열이 필요했다. 

 

우선적으로, 문제에서 맨 앞에 있는 박스는 뜯고 시작하기 때문에 기본 셋팅은 열고 시작하는 것으로 시작하였다. 그렇기 때문에 while문에서는 결국 2번째 박스부터 오픈하는것을 기반으로 시작된다.

 

while문은 openBox가 전부 true가 될 때까지 돈다. (그래야지 모든 박스를 열어본것이므로)

그리고 나면 테이블에 있는 밸류 값들을 기반으로 전부 계산해서 최댓값을 찾는것으로 문제가 해결 되었다.

 

추가적으로, 마지막 loop에서 나는 최댓값을 매번 비교해서 할당해주는 방식으로 변경했지만 내림차순이나 올림차순으로 정렬함으로써도 풀 수 있을 것이다.

 

 

javascript

function solution(cards) {
  let answer = 0;
 
  const openBox = Array.from({ length: cards.length }, (el, key) =>
    key === 0 ? true : false
  );
 
  const table = new Map();
  let tableIndex = 1;
  let cardIndex = 0;
  table.set(tableIndex, 1);
 
  while (openBox.includes(false)) {
    const num = cards[cardIndex] - 1;
    cardIndex = num;
 
    if (!openBox[num]) {
      table.set(tableIndex, (table.get(tableIndex) || 0) + 1);
    } else {
      tableIndex++;
 
      for (let j = 1; j < openBox.length; ++j) {
        if (!openBox[j]) {
          cardIndex = j;
          break;
        }
      }
    }
 
    openBox[num] = true;
  }
 
  const arr = [...table];
  for (let i = 0; i < arr.length - 1; ++i) {
    for (let j = i + 1; j < arr.length; ++j) {
      answer = Math.max(answer, arr[i][1] * arr[j][1]);
    }
  }
 
  return answer;
}

 

 

python

def solution(cards):
    answer = 0
 
    openBox = []
    for i in range(len(cards)):
        if (i == 0): openBox.append(True)
        else: openBox.append(False)
 
 
    table = {}
    tableIndex = 1
    cardIndex = 0
    table[tableIndex] = 1
 
 
    while not all(openBox):
        num = cards[cardIndex] - 1
        cardIndex = num
 
        if (not openBox[num]):
            if tableIndex in table:
                table[tableIndex] = table[tableIndex] + 1
            else:
                table[tableIndex] = 1
        else:
            tableIndex = tableIndex + 1
            for i in range(1, len(openBox)):
                if not openBox[i]:
                    cardIndex = i
                    break
 
        openBox[num] = True
 
    arr = []
    for key, value in table.items():
        arr.append([key, value])
 
    for i in range(len(arr) - 1):
        for j in range(i + 1, len(arr)):
            answer = max(answer, arr[i][1] * arr[j][1])
 
    return answer

 

 

 

 

 

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/131130?language=python3

프로그래머스