[백준] 1110번 : 더하기 사이클 - JAVA [자바]

 

 

 

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

1110번: 더하기 사이클

 

 

 

---

• 문제

 

그렇게 어렵지는 않은 문제다.

 

알고리즘 자체가 매우 단순한 유형이라 조금만 살펴보면 금방 풀 수 있다.

 

 

---

• 2가지 풀이방법을 제시한다.

 

 

Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다.

 

 

 

---

• 알고리즘

먼저 N 이라는 정수가 주어진다고 가정하자.

 

그러면 N의 1의 자릿수는 새로운 수의 10의 자리로,

N의 1의 자릿수와 10의 자릿수를 더한 값의 1의 자릿수는 새로운 수의 1의 자리로 가면 된다.

(만약 N 이 한 자릿수 정수라면 앞에 0을 붙여서 더한다.)

 

즉 아래의 그림과 같은 구조다.

 

그럼 위의 알고리즘을 하나씩 구성해보자.

먼저 주어진 수를 N 이라 하고 새로운 수를 T로 가정한다.

 

먼저 주어진 수 N의 일의 자릿수는 새로운 수(T)의 십의 자릿수로 간다.

T = (N % 10) * 10	// T의 십의 자릿수

즉 10으로 나눈 나머지 값에 10을 곱하면 T의 십의 자릿수가 된다.

---

그러면 각 자릿수의 합은 어떻게 구할까?

먼저 N의 십의 자릿수는 나누기 10 을 하면 N이 한 자릿수이면 0, 그 외에는 십의 자릿수가 그대로 반환된다.

그리고 N의 일의 자릿수는 나머지인 % 을 쓰면 된다.

 

이 두개를 더한 뒤 10으로 나눈 나머지가 N의 각 자릿수의 합의 일의 자릿수가 T의 일의 자릿수가 되겠다.

T = ((N / 10) + (N % 10)) % 10	// T의 일의 자릿수

 

정리하면, 위 두개의 값을 더한 것이 바로 새로운 수 T 가 되는 것이다.

즉, T 는 아래와 같다.

T = ((N % 10) * 10) + (((N / 10) + (N % 10)) % 10)

 

그리고 이를 반복하기 위해 while 문을 작성하여 내부에 위의 알고리즘을 넣어주자.

 

단, 주의할 점이 위에서는 T를 새로운 수로 가정했는데, 실제로는 반복문에서 N 값을 계속 새로운 값으로 대체해주어야 하는 것이니 T 를 N으로 고친다.

while(true){
	N = ((N % 10) * 10) + (((N / 10) + (N % 10)) % 10);
}

 

마지막으로 가장 처음 입력값과의 비교를 해야하므로 다음 3가지를 추가한다.

1. 처음 입력값을 복사한 변수 copy
2. 반복문이 몇 번 반복되었는지 세어주는 변수 count
3. 처음 입력값과 새로운 변수가 같을 경우 반복문을 종료하기 위한 조건문

int N = input();	//입력
int copy = N;		//변수 복사
int count = 0;

while(true){
	N = ((N % 10) * 10) + (((N / 10) + (N % 10)) % 10);
	count++;

	if(copy == N){
		break;
	}
}

 

위와 같은 알고리즘을 구성하면 된다!

 

물론 if문을 쓰지 않고도 쓸 수 있다.

단 주의해야 할 것이 최소 1번은 반복문을 돌아야한다는 점이다.

그렇기 때문에 do-while 문을 써야 한다.

 

int N = input();	//입력
int copy = N;		//변수 복사
int count = 0;

do {
	N = ((N % 10) * 10) + (((N / 10) + (N % 10)) % 10);
	count++;
} while(copy != N);

 

위와 같이 짤 수도 있다.

편의에 따라 여러분이 선택하여 코딩하면 된다.

 

 

그리고 괄호를 굳이 칠 필요가 있냐는 질문이 있을 수 있어서 미리 말하고자 한다.

앞으로 필자던 독자던 상관없이 자바를 다루는 사람이라면 Casting (캐스팅) 을 해주어야 할 때가 생긴다. (또는 형 변환)

 

이럴 때 괄호는 매우 중요한 역할을 하는데, 괄호가 캐스팅보다 우선순위라는 점이다.

그렇기 때문에 연산 순서라던가 어떤 알고리즘에 있어 순서도가 중요한 경우 괄호를 쳐주는 것이 명시적으로 우선순위를 두는 것이기 때문에 어지간하면 괄호를 쳐주는 것이 좋다.

 

 

 

---

• 풀이

- 방법 1 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int N = in.nextInt();
		in.close();
        
		int cnt = 0;
		int copy = N;
        
		while (true) {
			N = ((N % 10) * 10) + (((N / 10) + (N % 10)) % 10);
			cnt++;

			if (copy == N) {
				break;
			}
		}
		System.out.println(cnt);
	}
}

 

질문 게시판에 보니까 자바로 할 때 시간초과가 나는 경우가 발생한다는 질문이 있는데 이는 대부분 "정확하지 않은 알고리즘"으로 인해 반복이 불필요하게 더 돌아가는 상황이 왔기 때문이다.

Scanner 로도 0.1 초 정도 밖에 안걸리니 알고리즘만 정확하면 충분히 풀 수 있는 시간이다.

 

 

 

 

 

---

 

- 방법 2 

 

 

BufferedReader 을 쓰는 방식이다.

이 방법도 입력만 달라졌을 뿐 알고리즘 자체는 같기 때문에 어렵지 않게 쓸 수 있다.

그리고 이번에는 do-while문으로 써보고자 한다.

 

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));

		int N = Integer.parseInt(br.readLine());
		
		int cnt = 0;
		int copy = N;
        
		do {
			N = ((N % 10) * 10) + (((N / 10) + (N % 10)) % 10);
			cnt++;
		} while (copy != N);
		
		System.out.println(cnt);
	}
}

 

 

 

막상 풀어보니 어렵지 않게 느껴지지 않는가? (아니면 어쩔 수 없고...)

 

두 코드의 성능 비교를 해보자.

 

---

• 성능 차이
  
  
  

위에서 부터 순서대로

 

채점 번호 : 17973384  -  BufferedReader

채점 번호 : 17973382  -  Scanner

 

시간을 보면 BufferedReader 와 Scanner 의 성능차이를 볼 수 있다.

심지어 메모리도 아낀다.

 

위의 이유가 궁금하다면 아래 더보기에 있는 링크를 들어가서 보면 좋을 것 같다.

 

 

 

https://st-lab.tistory.com/41

JAVA [자바] - 입력 뜯어보기 [Scanner, InputStream, BufferedReader]