[백준알고리즘/함수] 1065번 문제 : 한수(자바/JAVA)

안녕하세요

백준 알고리즘 단계별로 풀어보기 6단계 함수의 한수를 풀어봤습니다

이번에는 문제를 이해하는게 어려워서 시간이 오래걸렸던 문제였습니다

처음 보고 수십 번 읽어봤습니다...;;

이제 제가 풀은 방법에 대해서 설명을 해보겠습니다

 

---

1065번 문제 한수의 링크입니다

www.acmicpc.net/problem/1065

1065번: 한수

 

문제

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

 

입력

첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.

 

출력

첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.

 

 

---

 

 

문제 풀이

먼저 문제를 풀기 전에 등차수열이란 무엇인지 알아보겠습니다

수학에서, 등차수열(等差數列, 문화어: 같은차수렬, 영어: arithmetic progression, AP 또는 arithmetic sequence)은 연속하는 두 항의 차이가 모두 일정한 수열을 뜻한다. 예를 들어 1, 3, 5, 7, 9, ...은 등차수열이다. 이때 두 항의 차이는 이 수열의 모든 연속하는 두 항들에 대해서 공통적으로 나타나는 차이므로, 공차(common difference)라고 한다. 예를 들어, 앞의 수열의 공차는 2이다.

출처 : ko.wikipedia.org/wiki/%EB%93%B1%EC%B0%A8%EC%88%98%EC%97%B4

 

계속해서 이어지는 수를 등차수열이라고 합니다

간단하게 말하면 연속적으로 이어지는 수를 등차수열이라고 합니다

Ex) 123, 135, 147, 246, 369 등등

또한 1-99까지는 무조건 이어질 수 밖에 없으므로 등차수열이라고 정의를 합니다

이 문제의 포인트는 숫자 전체를 보면 안 되고 개별로 봐야한다는 점입니다

이제 제가 풀은 방식에 대해서 알아보겠습니다!

 

---

첫 번째 방식입니다

먼저 1000인 경우는 등차수열에서 제외해야하므로 Count -1을 해줍니다

반복문을 사용 1 ~ 99까지는 무조건 등차수열이므로 더해줍니다

3자리 정수의 경우 등차수열을 판별하는 방법은 먼저 첫째 자릿수와 둘째 자릿수를 빼서 공차를 구해줍니다

둘째 자릿수에서 공차를 더한 값이 셋째 자릿수와 같은 경우 등차수열로 판별합니다

맨 처음 풀었을 때는 1 ~ 99까지도 계산공식이 있을 것 같은데 그냥 등차수열로 처리를 해버려서 약간 찜찜함이 있었습니다

또한 등차수열인지 판별하는 방식도 다른 좋은 방법이 있을 것 같다는 생각이 계속 들어서 고민을 많이했습니다

결국에는 다른 사람들이 풀은 알고리즘을 확인하니 다들 비슷하게 풀어서 안도(?)를 했습니다 ㅎ

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

public class Main {
	public static void main(String[] args)  throws IOException {
		// 수열 N 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		int N = Integer.parseInt(br.readLine());
		
		// 결과 출력
		System.out.print(count(N));
	}
	
	// 등차수열의 개수를 구할 메소드
	public static int count(int N)
	{
		// 첫째 자릿수, 둘째 자릿수, 셋째 자릿수 변수 선언
		int a;
		int b;
		int c;
		
		// 등차수열의 공차를 구해 넣을 변수 선언
		int Su;
		
		// 등차수열의 개수를 넣을 변수
		int count = 0;
		
		// N이 1000인 경우 -1
		if(N == 1000)
			count--;
		
		// 반복문을 사용 등차수열을 구한다
		for(int i = 1; i <= N; i++)
		{			
			// 100보다 작으면 등차수열
			if(i < 100) {
				count++;
				continue;
			}
			
			// 첫째 자릿수와 둘째 자릿수를 빼서 공차를 계산
			a = i % 10;
			b = (i / 10) % 10;
			Su = b - a;
			
			// 셋째 자릿수 계산
			c =  (i / 100) % 10;
			
			// 둘째 자릿수에 공차를 더한 값이 셋째 자릿수와 같으면 등차수열
			if(b + Su == c)
				count++;
		}
		
		// 결과 return
		return count;
	}
}

 

---

두 번째 방식입니다

if문을 사용 100보다 작은 경우 입력한 값을 그대로 return합니다

100보다 큰 경우 등차수열인지 아닌지 판별합니다

첫째 자릿수 - 둘째 자릿수 == 둘째 자릿수 - 셋째 자릿수로 등차수열인지 아닌지 판별합니다

첫 번째 방식보다 많이 심플해졌습니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// 수열 N 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		// 결과 출력
		System.out.print(count(N));
	}

	// 등차수열의 개수를 구할 메소드
	public static int count(int N) {
		// 100보다 작으면 등차수열
		if (N < 100) {
			return N;
		} else {
			// 첫째 자릿수, 둘째 자릿수, 셋째 자릿수 변수 선언
			int a;
			int b;
			int c;
			int count = 99;

			// N이 1000인 경우 -1
			if (N == 1000)
				count--;

			// 반복문을 사용 등차수열을 구한다
			for (int i = 100; i <= N; i++) {
				// 첫째 자릿수, 둘째 자릿수, 셋째 자릿수 계산
				a = i % 10;
				b = (i / 10) % 10;
				c = (i / 100) % 10;

				// 첫째 자릿수 - 둘째 자릿수 == 둘째 자릿수 - 셋째 자릿수가 같다면 등차수열
				if (a - b == b - c)
					count++;
			}

			// 결과 return
			return count;
		}
	}
}

 

---

속도 비교

 

첫 번째 방식이 정제되지 않은 느낌이라 역시 속도나 메모리가 더 나온 것을 확인할 수 있습니다 ㅎ

이상 백준 알고리즘 1065번 한수를 풀은 내용이었습니다!

 

이전 문제 : 2021.05.09 - [알고리즘/알고리즘JAVA] - [백준알고리즘/함수] 4673번 문제 : 셀프 넘버(자바/JAVA)