백준 [BOJ 1065] 한수

https://www.acmicpc.net/problem/1065

1065번: 한수

 

 

 

알고리즘 스터디를 진행하면서 이전에 풀지 못했던 문제를 맞닥뜨렸다. 왜 문제를 풀지 못했는지 과오를 되풀이 하지 않기 위해 스스로 진단하는 것이 중요하다고 판단하였다.

 

 

무엇을 몰랐는지

문제

 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 
등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. 
N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 


1. 문제에서 말하는 등차수열과 한수의 정확한 정의와 연관 관계를 이해하지 못했음
2. 문제의 X와 입력 값을 혼동함 -> 입력 값은 n

 

따라서 문제에 접근도 하지 못했다.

 

무엇을 깨달았는지

문제에 접근하는 것 조차 하지 못해 다른 사람들의 문제 접근 방법을 찾아보았다.

 

1. 공차수열의 조건

1) 항이 3개 이상이고, 공차가 같으면 공차수열이다.

1, 1, 1 => 공차는 모두 0
1, 2, 3 => 공차는 모두 1
3, 2 ,1 => 공차는 모두 -1

2) 3개 미만의 항을 가지는 공차수열이라면 한수로 취급한다. 항이 3개 이상이여야 비교할 숫자 대상이 존재하여 공차를 구할 수 있다.

여기서, 항이 1개 혹은 2개 일 때는 모두 한수가 된다.

문제에서는 입력 값을 자릿수 별로 항을 만든다.

예를 들어 입력값이 1이면 항은 1이다. 1 다음으로 오는 항이 없어 비교할 대상이 없다. 1은 한수이다.
예를 들어 입력값이 12이면 항은 1, 2이다. 1과 2는 비교 가능하지만 2 다음으로 오는 항이 없어 비교할 수 없다. 12는 한수이다.
예를 들어 입력값이 123이면 항은 1, 2, 3이다. 1과 2의 공차는 1, 2와 3의 공차는 1, 123은 한수이다.
예를 들어 입력값이 124이면 항은 1, 2, 4이다. 1과 2의 공차는 1, 2와 3의 공차는 4, 123은 한수가 될 수 없다.

 

어떻게 풀었는지

위의 공차를 구하는 방식에 의거하여 조건문으로 분기를 나누어 로직을 만들었다. 

1. 100 미만의 입력 값이 들어온 경우
입력 값이 모두 한수가 되므로 입력 값 그대로 반환하였다.

 

2. 100 이상의 입력 값이 들어온 경우

0) 한수의 개수를 세는 변수에 99로 초기화 해주었다. (2자릿수 이하의 숫자는 모두 한수이므로)

let hansuCnt = 99;

1) 반복문 만들기 (100부터 입력 값까지 반복하는 반복문)

for(let i = 100; i <= inputNumber; i++) {}
 

2) 반복문의 초기값 i의 각 자릿수 별로 배열을 만들고 마지막 항과 마지막항의 이전 항을 빼주어 공차를 구해 Set 타입의 변수에 넣어주었다.

const set = new Set();
set.add(arr[arr.length-1] - arr[arr.length-2]);

3) 배열의 마지막 원소를 삭제하고 배열의 길이가 1이 될 때까지 2)를 반복 (1개의 항만 남는다면 더 이상 공차를 구할 수 없으므로)

arr.pop();

4) 더 이상 연산할 수 없으면 set의 크기 값이 1이면 한수의 개수를 세는 변수에 값을 1증가 시켜주었다.

numberCnt.size === 1 && (hansuCnt += 1);

5) 반복문이 끝나면 한수의 개수를 반환

return hansuCnt;

 

나의 풀이

let [inputNumber] = require("fs")
  .readFileSync(0)
  .toString()
  .trim()
  .split(" ");
 
const checkHansu = (inputNumber) => {
  let hansuCnt = 0;
  const number = parseInt(inputNumber, 10);
 
  if (number < 100) {
    return number;
  } else {
    hansuCnt += 99;
 
    for (let i = 100; i <= number; i++) {
      const numberArr = i.toString().split("");
      const numberCnt = new Set();
 
      while (numberArr.length !== 1) {
        const a = parseInt(numberArr[numberArr.length - 2]);
        const b = parseInt(numberArr[numberArr.length - 1]);
 
        numberCnt.add(a - b);
 
        numberArr.pop();
      }
 
      numberCnt.size === 1 && (hansuCnt += 1);
    }
  }
 
  return hansuCnt;
};
 
console.log(checkHansu(inputNumber));