[JS] 완전탐색(brute-force) : 자릿수의 합

개요

생각치도 못한 부분에서 틀려버렸습니다... 2중 loop를 돌긴 하지만, 숫자를 효율적으로 사용하지 못해 예상 테스트 케이스도 깨지 못해서 강의를 보았더니... 훨씬 좋은 내용이 있네요. 다시 풀어봐야겠습니다.

문제

N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력하는 프로그램을 작성하라.

자릿수의 합이 같은 경우 원래 숫자가 큰 숫자를 답으로 한다.

만약 235와 1234가 동시에 답이 될 수 있다면 1234를 답으로 출력한다.

 

▣ 입력설명

첫 줄에 N(3<=N<=100)개의 자연수가 주어진다.

각 자연수의 크기는 10,000,000를 넘지 않는다.

 

▣ 출력설명

자릿수의 합이 최대인 자연수를 출력한다.

 

▣ 입력예제 1

128 460 603 40 521 137 123

 

▣ 출력예제 1

137

코드

🤐 : 최초 작성, 틀린 코드

function solution(arr) {
  let answer = Number.MIN_SAFE_INTEGER;

  // 문자열 배열로
  arr = arr.map(String);

  let originItem = Number.MIN_SAFE_INTEGER;

  for (let item of arr) {
    let sum = 0;
    for (let i = 0; i < item.length; i++) {
      sum += Number(item[i]);
    }

    if (answer < sum) {
      answer = sum;
      originItem = item;
    } else if (answer === sum) {
      answer = originItem <= Number(item) ? Number(item) : originItem;
      originItem = item;
    }
  }

  return answer;
}

// 테스트
describe('자리수의 합', () => {
  it('기본 테스트 케이스1', () => {
    let arr = [128, 460, 603, 40, 521, 137, 123];
    expect(solution(arr)).toEqual(137);
  });	// passed

  it('기본 테스트 케이스2', () => {
    let arr = [460, 603, 40, 521, 127, 123, 235, 1234];
    expect(solution(arr)).toEqual(1234);
  });	// failed, 460이 나옴
});

- 주어진 배열의 원소를 full-scan 하는 형태로 짰는데, 효율성은 고사하고 정확도도 맞지 않습니다.

- 형변환을 어거지로 두 번 실행하는 것도 비효율적이고, 테스트 케이스2에서 460을 반환하면서 끝나버립니다.

---

🤩 : 반복 풀이하기

function solution(n, arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let max = Number.MIN_SAFE_INTEGER;

  for (let item of arr) {
    let sum = 0;
    let temp = item;
    /**
     * temp   temp % 10
     * 128    8
     * 12     2
     * 1      1
     * 0      break
     */
    while (temp) {
      sum += temp % 10;
      temp = Math.floor(temp / 10);
    }

    if (sum > max) {
      max = sum;
      answer = item;
    } else if (sum === max && item > answer) {
      answer = item;
    }
  }

  return answer;
}

// 테스트
describe('자리수의 합', () => {
  it('기본 테스트 케이스1', () => {
    let arr = [128, 460, 603, 40, 521, 137, 123];
    expect(solution(7, arr)).toEqual(137);
  });	// passed

  it('기본 테스트 케이스2', () => {
    let arr = [460, 603, 40, 521, 127, 123, 235, 1234];
    expect(solution(7, arr)).toEqual(1234);
  });	// passed
});

- 가장 큰 차이점은 각 자릿수를 10으로 나누어 나머지끼리 더하는 부분입니다. 코드가 더 깔끔해지고 가독성도 좋네요.

- 이 코드를 내장 함수를 사용하여 조금 더 줄여보자면...

 

😎 : 코드 줄이기

function solution(n, arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let max = Number.MIN_SAFE_INTEGER;

  for (let item of arr) {
    // while문을 변형
    let sum = item.toString().split('').reduce((a, b) => a + Number(b), 0);
    if (sum > max) {
      max = sum;
      answer = item;
    } else if (sum === max && item > answer) {
      answer = item;
    }
  }

  return answer;
}

- reduce를 사용하여 각 자릿수의 값을 더해줍니다. 결과는 위와 같습니다.

생각해야 할 것

주어진 배열을 처리할 때, 배열이 가진 원소의 타입에 따라 어떻게 로직을 처리할 건지 많은 선택지를 염두에 두고 있어야 합니다. 무작정 코드를 짜려고 하니 이렇게 허점이 보이네요. 개선해야겠습니다.