[백준 1339번] 단어 수학 / 자바 / 그리디 **

문제         

레벨: G4
알고리즘: 그리디
풀이시간:  50분
힌트 참조 유무: 유(아이디어 참조)

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

 

1 번째 시도   

[알고리즘 선택 과정]

• 입력 제한을 보니 DFS도 가능하다.
• 그러나 Greedy문제이기 때문에 Greedy로 풀어보겠다.

 

[Greedy란?]

• 탐욕적 알고리즘이라고도 불린다.
• 현재의 단계에서 최적을 선택해 마지막의 최적의 정답을 도출한다는 아이디어이다.
• 근시안적으로 현재만 보고 선택하는 것이 탐욕적 알고리즘이라고 불리는 게 어울린다.

 

[Greedy 과정]

• 알파벳이 주어진 순대로 탐색할 것이다.

 

• 납득이 가는 과정일 것이다. 그렇다면 어떨 때 알파벳의 숫자를 바꿔줘야 할까?
• 새로운 알파벳이 해당 숫자의 알파벳보다 자릿수가 높을 때 숫자를 바꿔줘야 한다.
• 만약 A B C가 9 8 7로 배정되었고 새로운 숫자 D가 들어왔는데 B보다 높은 자릿 수라면 B, C는 뒤로 밀려야 한다.
• A D B C는 9 8 7 6이된다.

 

[위 풀이법에 문제법]

• 최적의 해임을 보장하지 못한다.
• 위 문제는 자릿수마다 높은 숫자를 부여하는 것이 가장 높을 것이다가 전제되어야 하지만, 이를 확신할 수 없다.

 

[새로운 Greedy 풀이법]

• Keyword: 기여도 부여
• 자릿수마다 숫자를 갱신해주는 것이 아니라 기여도의 총 수로 숫자를 마지막에 부여해주는 것이다
• 예를 들어, AAA, ACDEB 가 있다고 해보자.
  •   AAA
    • A는 100의 자리, 10의 자리, 1의 자리에 해당하는 가중치를 가진다.
    • 따라서 A += 100 + 10 + 1
  • ACDEB
    • ACDEB = 10000 + 1000 + 100 + 10 + 1로 나타낼 수 있다.
    • 따라서 A += 10000, C += 1000, D += 100, E += 10, B += 1
  • 연산을 하면 A=10111, B = 1, C = 1000, D = 100, E = 10 이 된다.
    이제 이 가중치가 높은 순서대로 9, 8, 7, ...을 곱해주자.
  
  
  • 10111*9 + 1000*8 + 100*7 + 10*6 + 1*5 이므로 답은  99764 이다.
  •   여기서 알 수 있듯이, 특정 알파벳에 얼만큼의 가중치가 있는지는 신경 쓸 필요가 없다. 우리에게 필요한 것은 크기순으로 나열된 가중치들이다.

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


public class Main {
	static int N;
	static int [] arr = new int[26];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < str.length(); j++) {
				char c = str.charAt(j);
				arr[c-'A'] += (int)Math.pow(10, str.length() - 1 - j);
			}
		}
		
		Arrays.sort(arr);
		
		int num = 9;
		int turn = 25;
		int ans = 0;
		while(arr[turn] != 0) {
			ans += arr[turn]*num;
			turn--;
			num--;
		}
		
		System.out.print(ans);
	}
}

 

[배운 점]

이 문제가 그리드로 분류된 이유는 마지막 숫자를 할당해주는 방식 때문이다. 그러나, 난 이게 그리디인지 약간 모호하다는 생각이 든다. 계산된 값들을 정렬한 후 단순 숫자만 할당해주는 것이 그리드 방식일까? 너무 약한데? 내가 생각하는 건 1 -> 2 -> 3단계 차근차근 순회할 때마다 값을 갱신하는 것이 그리드라고 생각했다. 

 생각해보면 프로그래머스 광물캐기 문제를 풀 때 광물들을 다 정렬한 후 다이아, 철, 돌 곡갱이를 써가며 계산해가서 그리드 알고리즘이라고 불렀다. 

그렇다면 그리드 알고리즘은 이렇게 분류되지 않을까?

1.    1 -> 2 -> 3단계 차근차근 순회할 때마다 값을 갱신하는 그리드
2.    총합을 구한 후 어떠한 기준으로 정렬하여 부여하는 그리드

 
 그래서 이 문제를 통해 얻은 점은 기여도에 대한 아이디어와 그리드에 대한 분류이다.