[백준] 20164 홀수 홀릭 호석 JavaScript

혅·2024년 11월 17일

백준, 프로그래머스 -JavaScript-

목록 보기

176/215

문제

호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 홀수 홀릭에 빠진 호석이는 가지고 있는 수 N을 일련의 연산을 거치면서, 등장하는 숫자들에서 홀수를 최대한 많이 많이 보고 싶다.

하나의 수가 주어졌을 때 호석이는 한 번의 연산에서 다음과 같은 순서를 거친다.

수의 각 자리 숫자 중에서 홀수의 개수를 종이에 적는다.
수가 한 자리이면 더 이상 아무것도 하지 못하고 종료한다.
수가 두 자리이면 2개로 나눠서 합을 구하여 새로운 수로 생각한다.
수가 세 자리 이상이면 임의의 위치에서 끊어서 3개의 수로 분할하고, 3개를 더한 값을 새로운 수로 생각한다.
호석이는 연산이 종료된 순간에 종이에 적힌 수들을 모두 더한다. 그렇게 최종적으로 얻은 수를 최종값이라고 하자. 예를 들어, 시작하는 수가 82019 라고 하자. 그럼 아래와 같이 나누게 되면 5개의 홀수를 볼 수 있기 때문에, 최종값이 5가 된다.

시작할 때 호석이가 가진 수를 N 이라고 했을 때, 만들 수 있는 최종값 중 최솟값과 최댓값을 구해주자.

1 ≤ N ≤ 109-1, N 은 자연수이다.

입력

첫번째 줄에 호석이가 처음 시작할 때 가지고 있는 수 N 이 주어진다.

출력

첫 번째 줄에 호석이가 만들 수 있는 최종값 중에서 최솟값과 최댓값을 순서대로 공백으로 구분하여 출력한다.

예제 입력

514

예제 출력

4 4

내가 했던 풀이 방법

max와 min 값을 0과 Infinity로 초기화해준다.
cut 함수를 재귀적으로 호출한다. num은 문자열로 된 숫자로 해당 자리수들 중에 홀수의 개수를 count에 추가해준다.
num이 1자리 수이라면 max, min 값을 처리하고 return 한다. 2자리 수라면 각 자리수의 합을 cut에 재호출해준다.
자리 수가 그 이상일 경우, 모든 경우를 다 찾아주어야 한다. 무조건 1자리 수 이상은 가져야 하므로, index를 1부터 시작하고, 두 번째 수는 i+1번째부터 시작한다. 쉽게 말해 12345라는 수가 있다면, 처음에는 1/2/345로 수를 자르고 1/23/45 다음은 1/234/5, 12/3/45 ... 순으로 자른다. 자른 수를 모두 더해준 값을 cut에 다시 호출해준다.
cut 호출이 모두 끝난 뒤 min과 max 값을 출력한다.

코드

var fs = require('fs');
let N = fs.readFileSync(0, 'utf-8').toString().trim();

let max = 0;
let min = Infinity;

function cut(num, count) {
  for (let i = 0; i < num.length; i++) {
    if (Number(num[i]) % 2 !== 0) count++;
  }

  if (num.length === 1) {
    max = Math.max(max, count);
    min = Math.min(min, count);
    return;
  } else if (num.length === 2) {
    const sum = (Number(num[0]) + Number(num[1])).toString();
    cut(sum, count);
  } else {
    for (let i = 1; i < num.length; i++) {
      for (let j = i + 1; j < num.length; j++) {
        let part1 = num.slice(0, i);
        let part2 = num.slice(i, j);
        let part3 = num.slice(j);

        const sum = (Number(part1) + Number(part2) + Number(part3)).toString();
        cut(sum, count);
      }
    }
  }
}

cut(N, 0);

console.log(min, max);