1339번 : 단어 수학

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

1339번: 단어 수학

 

 

문제

 

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); sc.nextLine();
        String srr[] = new String[n];
        int pri[] = new int[26];

        for(int i=0;i<n;i++) {
            String str = sc.nextLine();
            srr[i] = str;
            int len = str.length();
            for(int j=0;j<len;j++) {
                int p = (int)(Math.pow(10,(len-j)));
                pri[str.charAt(j)-65]+=p;
            }
        }

        int alpha[] = new int[26];
        int v=9;
        for(int i=0;i<26;i++) {
            int max=0,index=0;
            for(int j=0;j<26;j++) {
                if(max<pri[j]) {
                    max=pri[j];
                    index=j;
                }
            }
            if(max!=0) {
                alpha[index] = v--;
                pri[index] = -1;
            }
        }

        int sum=0;
        for(int i=0;i<n;i++) {
            int len = srr[i].length();
            int t=0;
            for(int j=0;j<len;j++) {
                t+=alpha[srr[i].charAt(j)-65];
                t*=10;
            }
            sum+=t/10;
        }
        System.out.println(sum);
    }
}

 

 

해결방법

일단 문자열을 읽어 알파벳마다 우선순위를 배열 pri에 저장하였다. 우선순위를 정하는 방법은 문자열 길이를 세서 판단하였다. 아래와 같이 3가지 방법을 시도해보았다.

 

1. "ABCDF" => A=5, B=4, ... 이런 방식으로 우선순위를 배열 pri에 저장하였는데 이 방식은 옳지 않다. 이유는 우선순위가 같은 알파벳 A, B가 있을 때 A가 더 많이 있는 경우 A의 우선순위를 좀 더 높여줘야 하는데 높이려고 1을 더한다면 우선순위가 아예 다른 알파벳을 침범하기 때문이다. 추가적으로 아무 값도 더할 수 없는 문제가 생긴다.

AD => pri[]에 저장된 알파벳 A의 값, pri[]에 저장된 알파벳 D의 값

AD => 2,1
BD => 2,(1+1)
CE => 2,1
-알파벳 D와 A, B, C의 우선순위가 같아지는 문제 발생! D와 E만 구별해야 한다.

ADB => 3,2,1 
BEG => (3+?),2,1 
CFH => 3,2,1
-이 경우엔 알파벳 B의 우선순위에 아무 값도 더할 수 없다.

 

2. "ABCDF" => A=50, B=40, ... 이런 방식으로 우선순위를 배열에 저장하였는데 이 방식도 옳지 않다. 이유는 위의 예시와 같다. 뭘 더하든 우선순위가 아예 다른 알파벳을 침범하거나 아무 값도 더할 수 없는 문제가 생긴다.

 

3. "ABCDF" => A=10^5, B=10^4, ... 이런 방식으로 우선순위를 매긴다면 위의 문제가 다 해결이 된다.

AD => pri[]에 저장된 알파벳 A의 값, pri[]에 저장된 알파벳 D의 값

AD => 100,10
BD => 100,(10+10)
CE => 100,10
-알파벳 D와 A, B, C의 우선순위가 같아지는 문제 해결, D와 E도 구분 가능

ADB => 1000,100,10 
BEG => (1000+10),100,10 
CFH => 1000,100,10
-알파벳 B의 우선순위에 값을 더하여 A, B, C 구분 가능

 

3번의 방법으로 우선순위를 매긴 후 우선순위에 따라 숫자 9부터 차례대로 배열 alpha에 할당하고 연산을 진행하여 문제를 해결하였다.

 

3번의 시도만에 성공했는데 처음 풀어본 골드 문제였는데 역시 골드 문제는 어려운 것 같다.