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

풀이 ① - 클래스 Word 정의 후, Word[]를 정렬

1. 아이디어

1) 0 "zero" ~ 9 "nine" 을 String[]에 저장

2) for 문으로 m ~ n 사이의 정수들을 한 숫자(digit)씩 읽어서,
정수의 값과 영어로 읽은 값을 Word[]에 저장

3) Word[] 를 사전 순으로 정렬

• implements Comparable<Word>
  => public int compareTo(Word w) 메소드 오버라이딩

4) 정렬된 Word[] 에서 정수 값들을 차례로 출력

2. 자료구조

• Word[]: 각 정수들의 정수 값 int, 영어로 읽은 문자열 String 저장

3. 시간 복잡도

1) 각 정수의 값과 영어로 읽은 문자열을 Word[]에 저장: O(n)

2) 정렬: O(n log n)

3) 정렬된 문자열들을 정수로 출력: O(n)

=> 총 시간 복잡도: O(2n + n log n) (n: 정수 개수)
=> n 최대값 대략 100 대입: 200 + (100 x 2) = 400 << 2억

코드

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

class Word implements Comparable<Word> {
	public int number;
	public String strByDigit;	// 정수 number 를 한 숫자씩 영어로 읽은 문자열

	public Word(int number, String strByDigit) {
		this.number = number;
		this.strByDigit = strByDigit;
	}

	public int compareTo(Word w) {
		return strByDigit.compareTo(w.strByDigit);
	}
}

public class Main_Comparable {
	static int m, n;					// m 이상 n 이하의 정수
	static String[] numberStrArr;		// "zero" ~ "nine" 저장
	static StringBuilder sb = new StringBuilder();
	static Word[] words;

	static void solution() {
		// 1) 정수 값과 정수를 영어로 읽은 문자열을 Word[] 에 저장
		for (int i = m; i <= n; i++) {
			String strNumber = String.valueOf(i);			// "80" 형태 문자열
			StringBuilder strByDigit = new StringBuilder();
			// 한 숫자(문자)씩 읽은 결과 문자열 ("eight zero" 형태)

			for (int j = 0; j < strNumber.length(); j++) {
				int digit = Character.getNumericValue(strNumber.charAt(j));
				strByDigit.append(numberStrArr[digit])
						.append(" ");
			}

			words[i - m] = new Word(i, strByDigit.toString());
		}

		// 2) Word[]를 사전 순으로 정렬
		Arrays.sort(words);

		// 3) 정렬된 Word[] 에서 정수 값을 꺼내어 출력
		int count = 1;
		for (Word w : words) {
			int number = w.number;
			sb.append(number).append(" ");

			if (count % 10 == 0)
				sb.append("\n");

			count++;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st = new StringTokenizer(br.readLine());

		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		words = new Word[n - m + 1];

		numberStrArr = new String[] {
				"zero", "one", "two", "three", "four",
				"five", "six", "seven", "eight", "nine"
		};

		solution();
		System.out.println(sb);
	}
}

풀이 ② - ArrayList 정렬 후, HashMap으로 맵핑

1. 아이디어

1) 0 "zero" ~ 9 "nine" 을 String[]에 저장

2) for 문으로 m ~ n 사이의 정수들을 한 숫자(digit)씩 읽어서,
영어로 읽은 값을 ArrayList, HashMap에 저장

• HashMap<String, Integer>: 정수를 영어로 읽은 문자열이 Key, 정수 값이 Value

3) ArrayList를 사전 순으로 정렬

4) 정렬된 ArrayList의 요소를 HashMap의 Key로 하여,
HashMap에서 정수 값들을 꺼내 차례로 출력

2. 자료구조

• List<String>, ArrayList<String>: 정수를 한 숫자씩 영어로 읽은 문자열을 저장

• Map<String, Integer>, HashMap<String, Integer>
  : 정수를 영어로 읽은 문자열이 Key, 정수 값이 Value

3. 시간 복잡도

1) 각 정수를 영어로 읽은 문자열을 ArrayList에 저장: O(n)

2) 정렬: O(n log n)

3) 정렬된 ArrayList의 문자열들을 HashMap에 맵핑하여 정수 출력: O(n)

=> 총 시간 복잡도: O(2n + n log n) (n: 정수 개수)
=> n 최대값 대략 100 대입: 200 + (100 x 2) = 400 << 2억

코드

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

public class Main_HashMap {
	static int m, n;					// m 이상 n 이하의 정수
	static String[] numberStrArr;		// "zero" ~ "nine" 저장
	static StringBuilder sb = new StringBuilder();

	static List<String> list = new ArrayList<>();
	static Map<String, Integer> map = new HashMap<>();

	static void solution() {
		// 1) 정수를 영어로 읽은 문자열을 List 와 HashMap 에 저장
		for (int i = m; i <= n; i++) {
			 String strNumber = String.valueOf(i);			// "80" 형태 문자열
			 StringBuilder strByDigit = new StringBuilder();
			 // 한 숫자(문자)씩 읽은 결과 문자열 ("eight zero" 형태)

			 for (int j = 0; j < strNumber.length(); j++) {
				 int digit = Character.getNumericValue(strNumber.charAt(j));
				 strByDigit.append(numberStrArr[digit])
						 .append(" ");
			 }

			 list.add(strByDigit.toString());
			 map.put(strByDigit.toString(), i);
		}

		// 2) List 를 사전 순으로 정렬
		Collections.sort(list);

		// 3) 정렬된 List 의 문자열들을 HashMap 에 맵핑하여, 정수를 꺼내어 출력
		int count = 1;
		for (String s : list) {
			int num = map.get(s);
			sb.append(num).append(" ");

			if (count % 10 == 0)
				sb.append("\n");

			count++;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st = new StringTokenizer(br.readLine());

		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());

		numberStrArr = new String[] {
				"zero", "one", "two", "three", "four",
				"five", "six", "seven", "eight", "nine"
		};

		solution();
		System.out.println(sb);
	}
}