[자바] 1339 단어 수학

자바 / 골4 / 그리디 알고리즘

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

 

처음에 풀었던 알고리즘의 방향이 틀렸어서 거의 처음부터 다시 짰어야 했다. 하지만 처음 생각했던 (예제의 경우들만을 고려한 아주 편협하고 단순한 알고리즘) 방향에서 안되는 케이스들로 확장시켜 나가려고 하니 도무지 감이 잡히지 않아 고민하다가 구글링을 통해 답을 얻었다.

나름의 교훈... 어떤 알고리즘이 막혔을 때는... 어쩌면 처음부터 틀려먹은 알고리즘이라 거기서 확장시켜 나가는 것이 아닌, 처음부터 다시 생각해야 할 수도 있다.

 

알고리즘

각 알파벳마다 어떤 자릿수에 있는 지를 계산하여, 해당 알파벳이 있는 자릿수의 모든 합이 클 수록, 높은 중요도(큰 숫자)를 부여한다.

예를 들면, GCF + ACDEB의 경우

A: 10000

B: 1

C: 10 + 1000

D: 100

E: 10

F: 1

이런 식이다. 모든 알파벳을 담을 수 있는 크기 26의 alp라는 배열을 선언하고, 각 알파벳의 위치에 해당 수를 저장한다.

alp[sarr[i].charAt(j) - 'A' + 0] += Math.pow(10, max - j - 1);

 

그리고 해당 배열을 내림차순으로 정리하면, 

{10000, 1010, 100, 10, 1, 1, 0, 0, 0, 0, .....} 이런 배열이 된다.

중요도가 가장 큰 알파벳에 가장 큰 숫자(9)를 부여해야 하므로, 

for(int i = 0; i < 10; i++)
{
        sum += alp[i] * (9 - i);
}

이 과정을 통해 최종 sum을 구한다.

 

 

부가적인 요소로, 자릿수가 다른 숫자가 입력으로 들어왔을 경우 자릿수를 맞춰주기 위해 적은 자릿수의 앞에 공백을 추가하는 코드이다. (+ alp 배열에 저장까지)

        for(int i = 0; i < N; i++)
        {
            String spaces = " ".repeat(max - sarr[i].length());
            sarr[i] = spaces + sarr[i];
            
            for(int j = 0; j < max; j++)
            {
                if (sarr[i].charAt(j) != ' ')
                {
                    alp[sarr[i].charAt(j) - 'A' + 0] += Math.pow(10, max - j - 1);
                }
            }
        }

 

또한 다음은, int나 long은 오름차순으로만 정리할 수 있고, 내림차순은 지원하지 않아서, int나 long 배열을 내림차순으로 정리하기 위해서는 int(long) 배열을 Integer(Long) 배열로 바꾸고, 내림차순으로 정리하고, 그 Integer(Long) 배열을 원래의 int 배열에 다시 저장하는 과정을 거쳐야 한다. 그 코드이다.

        Long[] longArray = Arrays.stream(alp).boxed().toArray(Long[]::new);
        Arrays.sort(longArray, Collections.reverseOrder());
        alp = Arrays.stream(longArray).mapToLong(Long::longValue).toArray();

 

 

 

다음은 전체 코드이다.

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

public class Main
{
    private static int N, max = 0;
    private static long sum = 0;
    private static String[] sarr;
    private static long[] alp = new long[26];
    

    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        sarr = new String[N];

        for(int i = 0; i < N; i++)
        {
            sarr[i] = br.readLine();
            if (max < sarr[i].length())
                max = sarr[i].length();
        }
        
        for(int i = 0; i < N; i++)
        {
            String spaces = " ".repeat(max - sarr[i].length());
            sarr[i] = spaces + sarr[i];
            
            for(int j = 0; j < max; j++)
            {
                if (sarr[i].charAt(j) != ' ')
                {
                    alp[sarr[i].charAt(j) - 'A' + 0] += Math.pow(10, max - j - 1);
                }
            }
        }

        Long[] longArray = Arrays.stream(alp).boxed().toArray(Long[]::new);
        Arrays.sort(longArray, Collections.reverseOrder());
        alp = Arrays.stream(longArray).mapToLong(Long::longValue).toArray();
        
        for(int i = 0; i < 10; i++)
        {
            sum += alp[i] * (9 - i);
        }

        System.out.println(sum);
    }
}