[프로그래머스] 모음사전 풀이 / JavaScript

프로그래머스

 

작성 코드 (1차 시도 / 통과)

function solution(word) {
  let aptSet = { A: 0, E: 1, I: 2, O: 3, U: 4 };
  let result = 0;
  let i = 4;
  for (const w of word) {
    let wi = i;
    let mid = 0;
    while (wi > -1) {
      mid += 5 ** wi;
      wi -= 1;
    }
    result += mid * aptSet[w] + 1;
    i -= 1;
  }
  return result;
}

구현 로직

아무리 생각해봐도 수학적 접근밖에 떠오르지 않아 머리싸매고 패턴 생각해보다가 우연히 얻어걸려 발견한 구조인데 통과하고 다른 사람 풀이들을 보니 같은 로직을 생각하신 분이 많네요.

입출력 예시를 보면 AAAAE, AAAE가 6, 10인데 I가 갑자기 큰 수(1563)가 나온게 조금 의아했습니다. 사전 형식이긴 하지만 I 한글자로 저렇게 큰 순번을 계산하려면 자릿수를 계산하는 방법밖에 없겠다고 생각했습니다. 그리고 word의 최대 길이는 5이기 때문에 각 자리를 5^4, 5^3, 5^2, 5^1, 5^0이라고 한번 가정해봤습니다.

 

I의 자리를 계산하면 5^4입니다. 한참 부족하죠. 그런데 그 이전 자리들까지 계산해서 더하면 781이 됩니다. 여기에 2를 곱하면 1562가 되는데.. 입출력 예시에서 나온 1563과 값이 비슷합니다. 1이 더해진건 아마도 A가 추가될 때 순번이 1씩 증가하니 그런게 아닐까 생각했습니다.

문제는 781에서 2를 왜 곱해야하는지인데 이 값이 어디서 나와야하는 걸까.. 생각해보다 다른 word도 한번 계산을 해봤습니다.

 

AAAE에서 E의 자리를 위와 같은 방식으로 계산하면 (5^1 + 5^0) * 2 + 1= 13입니다. 수가 결과값보다 커져버렸고 여기에 추가로 곱해지는 값은 글자마다 다르다는 걸 알게되었습니다. 글자마다 다르다는 건 결국 index값이였죠. E의 index는 1입니다. 그래서 E의 자리의 값은 6 * 1 + 1 = 7이 됩니다. 3이 부족한데 AAA가 문제에서 3이라는 걸 알려주었죠. 이 부분을 통해서 문제에 적용되는 점화식을 발견했고 아래와 같습니다.

 

각 글자의 값 = (글자가 위치하는 자릿수와 그 이전 자릿수들의 합) * (글자의 index) + 1

 

위 식으로 EIO를 계산하면 (5^4 + 5^3 + 5^2 + 5^1 + 5^0) * 1 + 1 + (5^3 + 5^2 + 5^1 + 5^0) * 2 + 1 + (5^2 + 5^1 + 5^0) * 3 + 1 = 1189가 됩니다.

 

아래는 동일한 로직인데 더 짧고 효율성이 좋은 코드로 작성해주신 분이 계셔서 첨부합니다. 이전 자릿수를 더해주는 계산을 저는 반복문으로 했지만 781 / 5 ** 자릿수로 계산한 부분이 더 효율적으로 보이네요.

// 윤응구님 코드 인용
let solution = (word) =>
  [...word].reduce(
    (a, c, i) => a + "AEIOU".indexOf(c) * ~~(781 / 5 ** i) + 1,
    0
  );