알고리즘 (6월 8일)

1. 문제 (코딩도장, 앞뒤가 같은 수)

https://codingdojang.com/scode/401?answer_mode=hide 

코딩도장

---

2. 생각

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, ... 과 같이, 0 이상의 앞뒤가 같은 수를 크기 순으로 나열할 때, n 번째 수를 계산하는 프로그램을 작성하라.

 

n은 1부터 시작하며 크기에는 제한이 없다.

 

• 1이상의 임의의 자연수 N를 입력받는다.
• while문을 이용하여 N의 자릿수를 찾아 count 변수에 저장한다.
• count == 1은 무조건 앞뒤가 같기 때문에 ArrayList에 저장한다.
• count == 2은 자연수 N을 자리별로 숫자를 구해서 storage 리스트에 임시 저장하고, 각 자리 숫자를 비교하여
  앞뒤가 같은 숫자인지 확인하고, 앞뒤가 같으면 ArrayList에 저장한다.
• 찾은 앞뒤가 같은 숫자들을 담고 있는 "specialNumbers" 리스트를 결과로써 출력한다.

---

3. 풀이 및 코드 분석

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class FindTheNumber {
	public static void main(String[] args) {
		ArrayList<Integer> specialNumbers = new ArrayList<>(Arrays.asList(0));
		ArrayList<Integer> storage = new ArrayList<>();
		Scanner scan = new Scanner(System.in);
		
		System.out.println("자연수 N을 입력하시오:");
		int N = scan.nextInt();
		
		int number=1, copyNumber;
		int count=0, countSame=0, m, n;
		
		while(specialNumbers.size()<N) {
			// 자리수 체크
			copyNumber = number;
			
			while(copyNumber != 0) {
				count++;
				copyNumber /= 10;
			}
				
			// 자리수가 하나일 경우
			if(count==1) {
				specialNumbers.add(number);
			}else { // 자리수가 2개 이상일 경우
				copyNumber = number;
				
				// 각 자리의 숫자를 뽑아서 리스트에 임시 저장
				while(copyNumber>0) {
					storage.add(copyNumber%10);
					copyNumber /= 10;
				}
				
				// 대응되는 위치의 숫자들 비교
				for(int j=0; j<=(count/2)-1; j++) {
					m = storage.get(j);
					n = storage.get(count-1-j);
					
					if(m==n) {
						countSame+=1;
					}
				}
				
				// 앞뒤가 같은 숫자인지 판단
				if(countSame==count/2) {
					specialNumbers.add(number);
				}
				
				// 초기화
				storage.clear();
				countSame=0;
			}
			
			// 초기화
			number++;
			count=0;
		}
			
		// 결과 출력
		System.out.printf("\n결과 : %d\n", specialNumbers.get(N-1));	
	}
}

---

4. 메모

 

• 자연수 N의 자리수 구하는 방법
  → 변수 count를 하나씩 더하고, 자연수 N을 10으로 나눈 몫을 다시 N에 저장한다. 그리고, while문을 통해 N이 0이
      아닐 때까지 반복하면 변수 count를 통해 N의 자리수를 구할 수 있다.
• 앞뒤가 같은 수 구하는 방법
  → 자연수의 각 자리수 값을 구해서 리스트에 저장한 뒤, 대응되는 위치의 값들을 뽑아서 비교하여 구할 수 있다.
  
• 숫자를 뒤집는 방법
  → https://www.programiz.com/java-programming/examples/reverse-number 

 

• 다른 풀이 방법 - 숫자들의 위치를 뒤집은 뒤, 뒤집힌 숫자와 과 비교하는 방법
  → 해당 방법이 코드가 간결하며, 속도가 상대적으로 빠르다.....ㅠㅠ

import java.util.Scanner;

public class FindTheNumber {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		// 자연수 N입력
		System.out.println("자연수 N을 입력하시오:");
		int N = scan.nextInt();
		
		// number = 차례대로 앞뒤가 같은 숫자인지 비교 대상, specialIdx = 앞뒤가 같은 숫자가 몇 번째인지 체크
		// specialNumber = 앞뒤가 같은 숫자 임시 저장
		int number=0, copyNumber, specialIdx=0, specialNumber=0;
		
		// N 번째 앞뒤가 같은 숫자가 나올때까지
		while(specialIdx!=N) {
			copyNumber = number;
			int reverse = 0;
			
			// number 뒤집기
			while(copyNumber!=0) {
				int digit = copyNumber%10;
				reverse = reverse*10 + digit;
				copyNumber/=10;
			}
			
			// 뒤집힌 숫자와 원래 숫자 비교
			if(reverse==number) {
				specialIdx++;
				specialNumber=number;
			}
			
			number++;
		}
		
		// 결과 출력
		System.out.printf("%d번쩨 앞뒤가 같은 숫자는 %d입니다. \n", specialIdx, specialNumber);
	}
}