백준 : 한수 (1065)

*** 본 풀이는 java언어를 사용하였습니다 ***

문제 보러가기

 

요약

정수의 각 자리가 등차수열을 이루면 한수다.

한수의 개수를 출력하라.

각 자리가 등차수열이란??

처음에는 한수라는 용어가 잘 이해가 안갔는데, 간단하게 예를 들면 다음과 같다.

 

예시 1 )

123이라는 수가 있다면 각 자리의 수는 1, 2, 3이다.

수는 +1 씩 일정하게 증가하는 등차수열 이므로, 이것은 한수다.

 

예시 2 )

111이라는 수가 있다면 각 자리의 수는 1, 1, 1이다.

수는 +0 씩 일정하게 증가하는 등차수열 이므로, 이것 또한 한수다.

 

예시 3 )

110이라는 수가 있다면 각 자리의 수는 1, 1, 0이다.

첫 번째 수와 두 번째 수의 차이는 +0이다.

두 번째 수와 세 번째 수의 차이는 -1이다.

따라서 일정하게 증가하는 수가 아니므로 등차수열이 아니다. 즉, 한수가 아니다.

 

위 예시만 보면 한수가 어떻게 구해지는지 이해할 수 있었을 것이다.

그럼 다음의 예시는 한수일까?

12

 

첫 번째 수와 두 번째 수의 차이는 +1이다.

하지만 세 번째 수는 없으므로, 그냥 차이가 +1 인 등차수열이 된다.

즉, 12는 한수다.

 

그렇다면 2는?

자리 수가 1 자리 수의 경우는 비교할 수 가 없어 한수로 인정을 한다.

즉, 2는 한수다.

 

이러한 개념을 이해하고 있다면 문제를 쉽게 풀 수 있을 것이다.

 

풀이

1, 2 자리 수의 경우 모든 수가 한수가 되기 때문에 그냥 다음과 같이 수 자체를 리턴하면 된다.

if (1 <= n && n < 100) return n;

 

3 자리 수의 경우부터 한 수를 계산하면 되는데

int형으로 들어온 수를 비교하기 위해 char[]로 형변환을 해서 배열로 만들었다.

private static int getHansuCountWhenOverOneHundred(int n) {
    int result = 99;
    for (int i = 100; i <= n; i++) {
        char[] numbers = String.valueOf(i).toCharArray();
        if (isArithmetic(numbers)) result++;
    }
    return result;
}

 

한수인지 체크하는 isArithmetic(char[] numbers)라는 메서드로 리팩토링 하였다.

private static boolean isArithmetic(char[] numbers) {
    int diff = numbers[1] - numbers[0];
    boolean isArithmetic = true;
    for (int j = 2; j < numbers.length; j++) {
        if ((diff + numbers[j - 1]) != numbers[j]) {
            isArithmetic = false;
            break;
        }
    }
    return isArithmetic;
}

먼저 첫 번째의 수와 두 번째의 수의 차이 (공차)를 diff 변수에 넣어서

두 번째 수에서 공차를 더한 값이 세 번째 수여야 등차수열이므로 이 부분을 체크하였다.

 

제출 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print(Solution.solution(scanner.nextInt()));
    }
}

class Solution {
    public static int solution(int n) {
        if (1 <= n && n < 100) return n;
        return getHansuCountWhenOverOneHundred(n);
    }

    private static int getHansuCountWhenOverOneHundred(int n) {
        int result = 99;
        for (int i = 100; i <= n; i++) {
            char[] numbers = String.valueOf(i).toCharArray();
            if (isArithmetic(numbers)) result++;
        }
        return result;
    }

    private static boolean isArithmetic(char[] numbers) {
        int diff = numbers[1] - numbers[0];
        boolean isArithmetic = true;
        for (int j = 2; j < numbers.length; j++) {
            if ((diff + numbers[j - 1]) != numbers[j]) {
                isArithmetic = false;
                break;
            }
        }
        return isArithmetic;
    }
}

 

테스트 코드

import org.junit.Test;

import static org.assertj.core.api.Assertions.assertThat;

public class SolutionTest {

    @Test
    public void testCase_1() {
        assertThat(Solution.solution(110)).isEqualTo(99);
    }

    @Test
    public void testCase_2() {
        assertThat(Solution.solution(1)).isEqualTo(1);
    }

    @Test
    public void testCase_3() {
        assertThat(Solution.solution(210)).isEqualTo(105);
    }

    @Test
    public void testCase_4() {
        assertThat(Solution.solution(1000)).isEqualTo(144);
    }
}

 

회고

한수라는 개념을 이해하고 난 뒤에는 쉽게 문제를 풀 수 있었다.

100 이상의 수 부터는 100 부터 n까지 일일히 for문을 돌고

한수인지 체크하는 구조까지 이어지면 사실상 이중 for문으로 돌아가기 때문에

(1000 이하의 수 이므로 사실상 큰 성능체감은 아니지만)

브루트 포스 방식으로 효율성 측면에서는 좋지 않을 것 같다.