[BaekJoon] 1339 단어 수학 (Java)

🔗 문제 링크

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

📝 문제 풀이 설명

문제를 읽고 처음에는 자리수가 높은 알파벳 순으로 9, 8, 7, 6...로 변경하는 간단한 문제라고 생각을 하며 문제를 풀었다.
코드를 작성하고 주어진 테스트 케이스들은 전부 작동되었으나 코드 제출을 하였을때는 "실패했습니다"라는 결과로 돌아올 뿐이었습니다..😥😥😥

반례를 찾아본 결과 처음작성한 코드 아래에 첨부한 자료와 같이 가장 높은 자리가 아닌 자리수에서 중복된 숫자가 반복적으로 나온다면 상황에 따라 9, 8, 7... 순이 아닌 8, 9, 7.. 등의 순으로 배정되어야 할 수 있다는 것을 알게 되었다.

두번째 코드는 다른 사람의 풀이법을 참조하여 풀었습니다.

코드의 풀이는 내가 작성한 코드와 다르게 알파벳의 정보를 담는 배열을 만들고 단어를 순회하며 알파벳마다 자리수에 해당하는 값들을 더해주고 해당 배열을 정렬하여 값이 높은 순으로 9, 8, 7..등의 숫자를 배정하는 방식이었습니다.

구체적으로 설명해보면 다음과 같습니다.
예를들어 ABCD의 경우 A는 1000의 자리에 위치하여 코드의 value배열의 A값에 위치하는 곳에 +1000을 더해주며 B의 위치에는 100, C의 위치에는 10, D의 위치에는 1을 더해주는 식으로 모든 단어의 값들을 작업해줍니다.
이렇게 하면 각 알파벳마다 필요로 하는 값의 가중치가 정해지게 되며 해당 배열을 정렬하여 높은 수부터 9, 8, 7...을 곱하여 더해주면 최종 답이 나오게 됩니다.

※ 각 알파벳이 어떠한 숫자로 변경되는지는 꼭 알필요가 없음!!

👨🏻‍💻 처음 작성한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		boolean[] isChanged = new boolean[26]; // 해당 알파벳이 변경됐는지?
		int[] changeValue = new int[26]; // 각 알파벳이 변경되는 값의 정보
		
		int count = 9;
		
		int N = Integer.parseInt(br.readLine());
		String[] words = new String[N];
		
		// 숫자로 변환된 값들을 저장하는 list
		ArrayList<StringBuilder> changedString = new ArrayList<>();
		for (int i=0; i<N; i++) {
			changedString.add(new StringBuilder());
		}
		
		// 문자열을 저장하며 가장 큰 길이 구하기
		int maxLen = 0;
		for (int i=0; i<N; i++) {
			words[i] = br.readLine();
			if (words[i].length() > maxLen) maxLen = words[i].length();
		}
		
		// 문자열 최고길이부터 낮춰가며 각각 단어의 높은 자리수부터 숫자 할당
		for (int i=maxLen; i > 0; i--) {
			for (int j=0; j<N; j++) {
				if (words[j].length() >= i) {
					int charIdx = words[j].charAt(words[j].length() - i) - 'A';
					if (!isChanged[charIdx]) { 
						isChanged[charIdx] = true;
						changeValue[charIdx] = count;
						changedString.get(j).append(count);
						count--;
					}
					else changedString.get(j).append(changeValue[charIdx]);
				}
			}
		}
		
		// 최종 합 구하기
		int result = 0;
		for (StringBuilder i : changedString) {
			result += Integer.parseInt(i.toString());
		}
		
		System.out.println(result);

	}

}

📌반례
10
ABB
BB
BB
BB
BB
BB
BB
BB
BB
BB
정답값 : 1790
출력값 : 1780

👨🏻‍💻 두번째로 작성한 코드 (통과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int[] value = new int[26]; // 각 알파벳이 변경되는 값의 정보
		
		int N = Integer.parseInt(br.readLine());
		String[] words = new String[N];
		
		
		// 문자열을 저장하며 가장 큰 길이 구하기
		int maxLen = 0;
		for (int i=0; i<N; i++) {
			words[i] = br.readLine();
		}
		
		// 각 단어들의 알파벳의 위치에 해당하는 값들 1, 10, 100.. 을 각각의 알파벳 배열의 값에 더해준다.
		for (int i=0; i<N; i++) {
			int temp = (int) Math.pow(10, words[i].length()-1);
			for (int j = 0; j<words[i].length(); j++) {
				int charIdx = words[i].charAt(j) - 'A';
				value[charIdx] += temp;
				temp /= 10;
			}
		}
		
		Arrays.sort(value);
			
		// 최종 합 구하기
		int num = 9;
		int result = 0;
		for (int i=25; i>=0; i--) {
			if (value[i] == 0) break;
			
			result += (value[i]*num);
			num--;
		}
		System.out.println(result);

	}

}