[알고리즘] 배열을 반복해 순차적으로 값을 변경 및 수정하기

0. 들어가며 

프로그래머스 순위 탐색 문제를 풀다가 배열을 참조해서 순차적으로 배열을 변경하는 경우가 의외로

많이 있는 것 같아서 정리하였다. 

1. 사용 방식

예를 들어 [a, b, c, b, e]라는 배열이 있는데, 이것을 [-, b, c, d, e], [-, -, c, d, e], ... [a, b, c, d, -] 순으로 

모든 경우의 수를 다 만들어야 하는 상황이 있을 것이다. 

 

그럴 경우에 반복문을 통해서 만들어도 되지만 그렇게 만들려면 배열의 길이는 고정되야하고 

배열의 속성 개수에 따라 반복문 개수도 변경되기 때문에 일반적으로 재귀함수를 사용한다. 

 

2. 코드 구현 

const info = [
  "java backend junior pizza 150",
  "python frontend senior chicken 210",
  "python frontend senior chicken 150",
  "cpp backend senior pizza 260",
  "java backend junior chicken 80",
  "python backend senior chicken 50",
];

function loop(key, index, score, map) {
  const joinKey = key.join(" ");
  const arr = map[joinKey];
  if (arr) {
    arr.push(score);
  } else {
    map[joinKey] = [score];
  }

  for (let i = index; i < key.length; i++) {
    const newKey = [...key];
    newKey[i] = "-";

    loop(newKey, i + 1, score, map);
  }
}

const map = {};

for (const item of info) { 
  // item은 info의 값
  const key = item.split(" ");
  const score = parseInt(key.pop());

  loop(key, 0, score, map);
}

프로그래머스에서 사용된 코드의 일부분을 가지고 왔다. 

 

function loop(key, index, score, map) {
  const joinKey = key.join(" ");
  
  // ...
  
  map[joinKey] = [score];

  for (let i = index; i < key.length; i++) {
    const newKey = [...key];
    newKey[i] = "-";

    loop(newKey, i + 1, score, map);
  }
}

핵심은 loop 함수이다.  매개 변수로 4개를 받는데 

• key : 기준 배열 
• index : 몇 번째 값을 변경할 지를 나타내는 index
• score : 점수를 나타냄 ( 의미 없음 )
• map : 틀이 되는 객체 ( 틀이 되는 배열이라고 생각하면 됨 )

 

재귀 함수 loop에서 현재 배열 key를 for문으로 반복하고 있다. 

for (let i = index; i < key.length; i++) {
  const newKey = [...key];
  newKey[i] = "-";

  loop(newKey, i + 1, score, map);
}

여기서 let i 는 index를 가지고 있는데,

이게 처음엔 0 이고 만약 loop를 이동하다 보면 i + 1이기 때문에 1, 2, 3 ... 이 될 것이다. 

 

그래서 0번째를 " - " 로 바꾸고 다시 loop에선 1번째를 " - " 로 바꾸는 방식으로 반복한다. 

그렇게 하면 중복은 발생하지 않고 모든 경우의 값을 만들 수 있다.