[프로그래머스] 혼자 놀기의 달인 (javascript)

https://school.programmers.co.kr/learn/courses/30/lessons/131130

프로그래머스

1. 문제를 읽으면서, 박스를 열어보고 박스 안의 숫자 index에 위치한 박스를 열어보고 박스 안의 숫자 index에 위치한 박스를 열어보고 박스 안의 숫자 index에 위치한 박스를 열어보고.... 를 보며 재귀구조라고 생각했다. n 값의 범위도 최대 100이길래 재귀로 푸는 문제임을 확신할 수 있었다.

2. 박스를 계속 열다가, 박스 안 카드 숫자의 위치에 해당되는 박스가 열려있으면 박스 열기를 멈추고, 그것을 한 사이클이라 하자. 근데 한 사이클을 돌고 나서 다음 사이클을 돌 때, 열 수 있는 박스가 없으면 획득하는 점수는 0이 된다.

3. 문제를 잘못 읽어서 헤맨 부분이 있었다. 문제에서는 두 사이클을 돌았을 때, 각 사이클마다 열었던 카드의 개수를 곱해야 한다. 즉, 두 사이클만 구해서 곱하면 된다. 그런데, 나는 모든 사이클을 다 돌고 해당 숫자를 곱했다... 어쩐지 답이 안나오더라.

4. 숫자는 1부터 시작하지만,,, 실제로 박스 배열에서 idx로 접근할 때는 0부터 시작함에 주의해야한다.

코드 전문

function solution(cards) {
  // 박스를 여는 함수 (재귀구조)
  function openBox(cardIdx, opendCards, opendCnt) {
    let nextCardIdx = opendCards[cardIdx] - 1;

    opendCnt += 1;
    opendCards[cardIdx] = null;

    if (opendCards[nextCardIdx] === null) {
      return opendCnt;
    }

    return openBox(nextCardIdx, opendCards, opendCnt);
  }

  let answer = 0;

  // 첫 번째 사이클
  for (let cardIdx = 0; cardIdx < cards.length; cardIdx++) {
    let opendBoxes = [...cards];
    let firstGroupResult = openBox(cardIdx, opendBoxes, 0);

    // 두 번째 사이클
    for (let cardIdx2 = cardIdx + 1; cardIdx2 < cards.length; cardIdx2++) {
      if (opendBoxes[cardIdx2]) {
        let secondGroupResult = openBox(cardIdx2, opendBoxes, 0);
        if (firstGroupResult * secondGroupResult > answer)
          answer = firstGroupResult * secondGroupResult;
      }
    }
  }
  return answer;
}

 

상자를 여는 함수

// cardIdx: 현재 연 박스의 idx
// opendCards: 연 박스인지 아닌지 관리하는 배열
// opendCnt: 연 박스 개수
function openBox(cardIdx, opendCards, opendCnt) {
    // 현재 박스에 들어있는 카드 -> 다음에 열 박스의 idx가 됨
    // idx는 0부터 시작하지만, 숫자는 1부터 시작하므로 1을 뺀다
    let nextCardIdx = opendCards[cardIdx] - 1;
	
    // 박스를 열었으므로 cnt를 하나 올리고, opendCards에서 null로 변경
    opendCnt += 1;
    opendCards[cardIdx] = null;

    // 다음에 열 박스가 null이라면(=이미 열린 박스라면) 현재까지 연 박스의 개수를 return
    if (opendCards[nextCardIdx] === null) {
      return opendCnt;
    }
    // 그게 아니라면 재귀로 다음 박스를 열어본다
    return openBox(nextCardIdx, opendCards, opendCnt);
}

 

 

싸이클 2번 돌기

// 첫 번째 싸이클
for (let cardIdx = 0; cardIdx < cards.length; cardIdx++) {
	// 열린 박스인지 아직 열지 않은 박스인지 관리할 배열
    let opendBoxes = [...cards];
    // 재귀.. 열린 박스가 몇 개인지 저장한다.
    let firstGroupResult = openBox(cardIdx, opendBoxes, 0);
	
    // 두 번째 싸이클
    for (let cardIdx2 = cardIdx + 1; cardIdx2 < cards.length; cardIdx2++) {
    	// 열리지 않은 상자일 때만 openBox 실행한다.
        if (opendBoxes[cardIdx2]) {
            let secondGroupResult = openBox(cardIdx2, opendBoxes, 0);
            // 이렇게 하면 싸이클을 2번 돌 때만 값을 저장할 수 있다.
            // 싸이클을 한 번만 돌았을 경우에는 어차피 게임 결과가 0이므로...
            if (firstGroupResult * secondGroupResult > answer)
                answer = firstGroupResult * secondGroupResult;
        }
    }
}