[JAVA][BOJ][S4] 1755. 숫자놀이

1755번: 숫자놀이

문제

79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 먼저 온다.

문제는 정수 M, N(1 ≤ M ≤ N ≤ 99)이 주어지면 M 이상 N 이하의 정수를 숫자 하나씩 읽었을 때를 기준으로 사전순으로 정렬하여 출력하는 것이다.

입력

첫째 줄에 M과 N이 주어진다.

출력

M 이상 N 이하의 정수를 문제 조건에 맞게 정렬하여 한 줄에 10개씩 출력한다.

풀이

보통은 정렬을 이용해서 풀 것 같은 문제지만 잘 생각해 보면 배열이나 리스트, 정렬 없이도 풀 수 있는 문제다 주어진 값이 연속된 수가 아니라면 정렬을 사용해 정석으로 풀어야 한다 이 문제는 범위에 있는 수가 연속적이기 때문에, 규칙을 찾아서 배열에 저장하고 경우의 수만 잘 나눠서 계산하면 정렬 없이도 간단하게 풀 수 있다

코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		// 숫자의 사전 순서
		int[] dic = {8,5,4,9,1,7,6,3,2,0};
		
		// 줄바꿈을 위한 변수
		int cnt = 0;
		
		// 배열의 크기만큼 for문 돌리기
		for(int i = 0; i<10; i++) {
			// 1~9 출력
			// dic[i]이 M보다 크거나 같고 N보다 작거나 같다면 출력 저장
			if(dic[i]>=M && dic[i]<=N) {
				sb.append(dic[i]).append(" ");
				
				// 10개마다 엔터 치기
				if(++cnt%10 == 0) sb.append("\n");
			}
			
			// 11~99 출력
			// dic[i]를 십의자리로 가진 숫자
			
			// dic[i] = 5라고 했을 때,
			// M이 48이라면 48, 49도 계산해야 하기 때문에 M-10
			if(dic[i]*10>=M-10) {
				// 일의자리 구하기
				for(int k = 0; k < 10; k++) {
					// dic[i]를 십의자리로 가지고 dic[k]를 일의자리로 가진 숫자 구하기
					int num = dic[i]*10 + dic[k];
					// num이 10보다 작거나(위에서 이미 구함)
					// num이 M 이상 N 이하의 조건에서 벗어날 경우 continue
					if(num < 10 || num<M || num>N) continue;
					
					// 조건을 만족하면 출력 저장
					sb.append(num).append(" ");
					
					// 10개마다 엔터 치기
					if(++cnt%10 == 0) sb.append("\n");
				}
			}
		}
		
		// 출력하기
		System.out.println(sb);

	}

}

결과

 

#자바 #java #boj #백준 #알고리즘