[BaekJoon] 2608 로마 숫자 (Java)

1.  문제 링크

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

2.  문제

요약

• 로마 숫자는 아래와 같은 7개의 기호로 이루어집니다.
  • I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000
• 수를 만드는 규칙은 아래와 같습니다.
  1. 보통 큰 숫자를 왼쪽에, 작은 수를 오른쪽에 쓰고 그 값은 모든 숫자의 값을 더한 값이 됩니다.
  2. V, L, D는 한 번만 사용할 수 있고, I, X, C, M은 연속해서 세 번까지만 사용할 수 있습니다. 같은 숫자가 반복되면 그 값은 모든 숫자의 값을 더한 값이 됩니다.
  3. 작은 숫자가 큰 숫자의 왼쪽에 오는 경우가 있는데 해당 경우는 다음과 같습니다.
     • IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900
     • 각각은 한 번씩만 사용할 수 있습니다.
     • IV와 IX는 같이 쓸 수 없으며 XL과 XC, CD와 CM 또한 같이 쓸 수 없습니다.
  4. 모든 수는 가능한 적은 개수의 로마 숫자들로 표현해야 합니다.
• 로마 숫자로 이루어진 두 수를 입력받아 그 둘을 더한 값을 아라비아 숫자와 로마 숫자로 출력하는 문제입니다.
• 입력: 첫 번째 줄과 두 번째 줄에 하나씩 2000보다 작거나 같고 두 수의 합이 4000보다 작은 로마 숫자로 표현된 수가 주어집니다.
• 출력: 첫 번째 줄에 입력으로 주어진 두 수를 더한 값을 아라비아 숫자로 출력하고 두 번째 줄에는 로마 숫자로 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;

public class Main {
	public String[] findSumNum(String[] nums) {
		String[] result = new String[2];
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		map.put("I", 1);
		map.put("V", 5);
		map.put("X", 10);
		map.put("L", 50);
		map.put("C", 100);
		map.put("D", 500);
		map.put("M", 1000);
		map.put("IV", 4);
		map.put("IX", 9);
		map.put("XL", 40);
		map.put("XC", 90);
		map.put("CD", 400);
		map.put("CM", 900);
		
		int result_num = 0;
		for(int i = 0; i < nums.length; i++) {
			for(int j = 0; j < nums[i].length(); j++) {
				char cur_alphabet = nums[i].charAt(j);
				if((cur_alphabet == 'I' || cur_alphabet == 'X' || cur_alphabet == 'C') && j < nums[i].length() - 1) {
					String temp = Character.toString(cur_alphabet) + Character.toString(nums[i].charAt(j + 1));
					if(map.containsKey(temp)) {
						result_num += map.get(temp);
						j++;
						continue;
					}
				}
				result_num += map.get(Character.toString(cur_alphabet));
			}
		}
		result[0] = Integer.toString(result_num);
		
		String result_str = "";
		ArrayList<Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
		list.sort(Entry.comparingByValue(Collections.reverseOrder()));
		while(result_num != 0) {
			int temp = 0;
			for(Entry<String, Integer> e : list) {
				temp = result_num / e.getValue();
				if(temp != 0) {
					for(int i = 0; i < temp; i++) {
						result_str += e.getKey();
					}
					result_num = result_num % e.getValue();
					break;
				}
			}
		}
		result[1] = result_str;
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] nums = new String[2];
		for(int i = 0; i < 2; i++) {
			nums[i] = br.readLine();
		}
		br.close();
		Main m = new Main();
		String[] result = m.findSumNum(nums);
		for(int i = 0; i < result.length; i++) {
			System.out.println(result[i]);
		}
	}
}

4.  접근

• 주어진 숫자들을 key에는 로마 숫자로, value에는 아라비아 숫자로 설정하여 HashMap에 저장해줍니다.
• 주어진 두 로마 숫자를 더하기 위해서는 아라비아 숫자로 변경해줘야 하기 때문에 두 로마 숫자를 아라비아 숫자로 변경합니다.
• 첫 번째 문자부터 마지막 문자까지 각 문자에 해당하는 아라비아 숫자를 더해나가며 아라비아 숫자를 구해주는데 이 때, 작은 숫자가 큰 숫자의 왼쪽에 있는 경우를 주의해야 합니다.
• 해당 경우는 처음 문자가 "I", "X", "C"이기 때문에 만약 현재 확인하고 있는 문자가 앞의 세 문자 중 하나라면, 다음 문자까지 확인하여 작은 숫자가 큰 숫자의 왼쪽에 있는 경우인지 확인하고 맞다면 해당 경우에 대한 숫자를 더해주고 그렇지 않다면 문자 하나씩 나타내는 숫자를 더해갑니다.
• 위 방법으로 두 로마 숫자의 아라비아 숫자를 구한 후에 두 아라비아 숫자를 더해줍니다.
• 이젠 더한 아라비아 숫자를 로마 숫자로 변경해야 합니다.
• 기본적으로 큰 숫자가 왼쪽에 존재하기 때문에 로마 숫자가 어떤 아라비아 숫자를 의미하는지 나타내는 HashMap의 값들을 아라비아 숫자 기준으로 내림차순으로 정렬합니다.
• 위에서 두 로마 숫자를 더해 나온 아라비아 숫자를 HashMap에 있는 수들로 각각 나눠주는데, 순서는 큰 숫자부터 차례대로 나눠줍니다.
• HashMap의 각 숫자에서의 몫을 구하고, 만약 몫이 0이 아니라면 나눠준 HashMap의 아라비아 숫자에 해당하는 로마 숫자를 몫에 해당하는 개수만큼 이어 붙여주고 나눈 후의 나머지를 이용하여 다음 로마 숫자를 구합니다.