[백준] 1065번 : 한수 - JAVA [자바]

 

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

1065번: 한수

 

---

• 문제

 

 

※ 주의할 점

1. 1 보다 크고 입력받은 값보다 작거나 같은 한수의 개수를 출력한다.
2. 한수는 각 자리수가 등차수열을 이루는 수를 의미한다.

 

 

---

• 알고리즘

등차수열(arithmetic sequence). 즉 연속하는 두 항의 차이가 모두 일정한 수열을 의미한다.

예로들면 [ 1, 1, 1, 1, 1 ] , [ 1, 2, 3, 4, 5 ] , [ 1, 3, 5, 7 ,9 ] 등이 있다.

 

등차수열을 일반 항으로 나타낸다면 아래와 같다.

즉 두 항의 차이를 d 라고 할 때, n 번째 항은 초항과 (n-1) * d 의 합과 같다는 것이다.

 

우리가 풀 문제는 각 자리수가 등차수열을 이루고 있는지를 검사하는 문제다.

근데 잘 보면 1 ~ 1000 까지의 수 중 검사할 수는 100~1000 까지 밖에 없다.

 

생각해보자. 1 ~ 99 는 모두 등차 수열이다.

1 ~ 9 는 수가 하나 그 자체로 수열에 속한다.

 

10 ~ 99 또한 각 자리수의 차가 공차이고 그 수 자체로 수열을 이룬다.

예로들면 31 은 공차가 -2 인 수열이고, 38 은 공차가 5 인 수열이다.

 

그러면 우리가 알고리즘을 짤 때 생각해야 할 것은 100 보다 작은 수와 100 보다 큰 수의 케이스를 나누어 생각하면 되겠다.

 

 

 

그럼 하나하나씩 작성해보자.

1. 먼저 arithmetic_sequence 라는 함수와 해당 함수 안에 한수의 개수를 셀 cnt 라는 변수를 선언한다.

public static int arithmetic_sequence(int num){
	int cnt = 0;	// 한수 카운팅
    
	return cnt;
}

 

이 때, 우리가 입력받은 값을 알아야지 해당 수 보다 작거나 같은 한수의 개수를 셀 것이므로 int num 을 인자로 받아들이고 한수의 개수를 나타내는 cnt 를 return 할 것이기 때문에 위와같이 구성한다.

 

 

2. 다음으로 앞서 말했듯이 1 ~ 99 의 경우 그 수 자체가 수열이라고 했다. 즉, 케이스를 num 이 100 보다 작은 경우와 큰 경우를 나눈다.

어차피 문제에서의 입력은 1 에서 1000 까지 밖에 안들어온다.

 

그리고 num 이 100 보다 작을경우는 num 을 return 해주면 된다.

즉, 86이라는 수를 입력받더라도 1 ~ 86 까지는 모두 수열이기 때문에 86개의 수열이 존재하는 것이다.

for(int i = 0; i < num; i++){
	cnt++;
}

 

이렇게 해줘도 되지만 그냥 num 을 return 해주면 굳이 반복문을 돌 필요 없이 바로 출력을 할 수가 있다.

public static int arithmetic_sequence(int num){
	int cnt = 0;	// 한수 카운팅
    
	if(num < 100){
		return num;
	}
    
	else {
	}
    
	return cnt;
}

 

 

3. 본격적으로 else 문, 100 이상의 수들의 각 자릿수가 등차수열인지를 짜보자.

일단 100 이상의 수가 들어오면 한수의 최소 개수는 99개다. 그러므로 cnt = 99 로 초기화 해준다.

public static int arithmetic_sequence(int num){
	int cnt = 0;	// 한수 카운팅
    
	if(num < 100){
		return num;
	}
    
	else {
		cnt = 99; 
	}
    
	return cnt;
}

 

4. 다음으로 100 부터 입력받은 값(num)까지 반복하면서 한수의 개수를 세어주어야한다.

이때 각 자릿수를 변수를 둘 것이다.

 

그리고 i 라는 정수가 있을 때 각 자릿수는 다음과 같이 구한다. 

• 백의 자릿수 = i / 100
• 십의 자릿수 = (i / 10) % 10
• 일의 자릿수 = i % 10

 

특히 십의 자릿수는 먼저 i 에 10 을 나누어서 몫을 구한 뒤 해당 몫에 10 을 나눈 나머지를 구하면 십의 자릿수가 구해진다.

예로들어 372 라는 수가 있다면 372 / 10 = 37 이 되고 여기에 %10, 즉, 37 % 10 = 7 으로 372 의 십의 자릿수를 구할 수 있다.

public static int arithmetic_sequence(int num){
	int cnt = 0;	// 한수 카운팅
    
	if(num < 100){
		return num;
	}
    
	else {
		cnt = 99; 
        
		for(int i = 100; i <= num; i++){
			int hun = i / 100;	// 백의 자릿수
			int ten = (i / 10) % 10;	// 십의 자릿수
			int one = i % 10;
            
			if((hun - ten) == (ten - one)){	// 각 자릿수가 수열을 이루면
				cnt++;
			}
		}
	}
    
	return cnt;
}

그리고 조건문에서 주의를 해야할 것이 등차수열이므로 각 자릿수 순서대로 차이 값을 구해야 한다.

무슨 말이냐면 135 라는 수의 각 자릿수의 공차를 구하려면 백의 자리부터 차례대로 빼거나, 일의 자리부터 차례대로 빼야한다는 것이다.

 

즉, (1-3), (3-5) 를 하거나, (5-3), (3-1) 을 하라는의미다.

 

 

이렇게 짜면 함수를 다 구현한 것이다.

 

그럼 전체 코드를 보자.

 

---

• 풀이

- 방법 1 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		System.out.print(arithmetic_sequence(in.nextInt()));
		in.close();

		
	}

	public static int arithmetic_sequence(int num) {
		int cnt = 0; // 한수 카운팅

		if (num < 100) {
			return num;
		}

		else {
			cnt = 99;

			for (int i = 100; i <= num; i++) {
				int hun = i / 100; // 백의 자릿수
				int ten = (i / 10) % 10; // 십의 자릿수
				int one = i % 10;

				if ((hun - ten) == (ten - one)) { // 각 자릿수가 수열을 이루면
					cnt++;
				}
			}
		}

		return cnt;
	}

}

 

위와 같이 짜면 완성이다.

메인 함수는 따로 구성할 것이 입력밖에 없으니 별다른 설명은 하지 않겠다.

 

---

- 방법 2 

BufferedReader 을 사용하여 입력받는 방법이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		System.out.print(arithmetic_sequence(Integer.parseInt(br.readLine())));
		
	}

	public static int arithmetic_sequence(int num) {
		int cnt = 0; // 한수 카운팅

		if (num < 100) {
			return num;
		}

		else {
			cnt = 99;
			for (int i = 100; i <= num; i++) {
				int hun = i / 100; // 백의 자릿수
				int ten = (i / 10) % 10; // 십의 자릿수
				int one = i % 10;

				if ((hun - ten) == (ten - one)) { // 각 자릿수가 수열을 이루면
					cnt++;
				}
			}
		}

		return cnt;
	}

}

 

 

 

---

• 성능

위에서 부터 순서대로

 

채점 번호 : 18374422  -  BufferedReader 

채점 번호 : 18374414  -  Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

 

 

---

• 정리

아마 이 문제에서 틀린 분들은 대개 1000 을 입력 받았을 때의 예외처리 또는 고려하지 않아서 틀렸을 가능성이 가장 높을 것이다. 알고리즘 자체는 그리 어려운 문제가 아니므로 잘 이해했을 것이라 생각은 하지만..

 

만약 어렵거나 이해가 안되는 부분이 있다면 댓글로 물어보신다면 언제든 답변해드릴 것이다.