[BOJ1339] 단어 수학 (Java, 그리디, 완전 탐색)

문제 링크

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

 

풀이

- 완전 탐색 + 비트마스킹, 그리디 풀이

- 각 알파벳을 0 ~ 9 숫자로 중복 없이 치환하여서 최대값을 구하는 문제 (같은 알파벳은 같은 숫자로 바껴야 하고, 중복 숫자x)

 

처음 완전 탐색 + 비트 마스킹으로 풀이했다. 

그런데 공간복잡도와 시간복잡도가 너무 높이 나왔다.

그래서 그리디 풀이 방법을 고민했는데, 아이디어가 전혀 떠오르지 않아 블로그를 참고하여 풀이했다

 

1) 완전 탐색 + 비트 마스킹

- 중복을 제외한 알파벳을 구한다 

- 알파벳별로 9~0 사이의 숫자를 할당하면서 완전 탐색을 수행한다

- 이때 숫자 사용여부를 비트 마스킹 기법을 사용하였다 ( 9 ~ 0 자리의 비트를 표현하면 되므로 int 로 충분)

- idx 가 알파벳 수(중복제외)와 같을 때, 치환하고 최대값을 구한다

 

2) 그리디

- 각 문자열 알파벳 자리에 해당하는 10의 제곱근으로 치환하여 가중치를 쌓는다 (int[] alphabet = new int[26])

- 가중치를 오름차순 정렬해서 뒤에서부터 숫자 1씩 감소하며 곱한 후 결과 누적 (정렬한 순간부터 알파벳은 의미없어짐)

- 개인적으로 탐욕 알고리즘이라지만, 수학 문제에 더 가깝지 않았나 싶음

 

입력 예시가 아래와 같을 때

2
GCF
ACDEB

int[] alphabets = new int[27];
for(String word : words) {
    int len = word.length();
    for(char c : word.toCharArray()) {
        alphabets[c - 'A'] += (int) Math.pow(10, --len);
    }
}

 

각 알파벳은 아래와 같은 가중치(10의 제곱값)를 가지게 된다 

- GCF = 100G , 10C, 1F

- ACDEB = 10000A, 1000C, 100D, 10E, 1D 

- int[] alphabets 누적치 : A = 10000, C = 1010, D = 100, G = 100, E = 10, D = 1, F = 1

 

오름차순 정렬한 순간부터 알파벳은 의미가 없어진다. 가중치 높은 순서대로 높은 숫자를 할당하여 곱한 결과를 누적한다

10000 * 9 = 90000
1010 * 8 = 8080
100 * 7  = 700
100 * 6 = 600
10 * 5 = 50
1 * 4 = 4
1 * 3 = 3
----------
결과값 99437

 

 

 

참고. 공간 복잡도, 시간 복잡도 비교

공간 복잡도 약 20배, 시간 복잡도 약 10배의 차이를 보였다

위에가 그리디, 아래가 완전 탐색 풀이

 

제출 코드1. 완전 탐색

import java.util.*;
import java.io.*;

public class Main {
    private static StringBuilder sb = new StringBuilder();
    private static InputProcessor inputProcessor = new InputProcessor();

    public static void main(String[] args) {
        input();
        pro();
        output();
    }

    private static int n, result;
    private static String[] words;
    private static int[] alphabet;
    private static Character[] alphabets;

    private static void input() {
        n = inputProcessor.nextInt();
        words = new String[n];

        Set<Character> unique = new HashSet<>();
        for(int i = 0; i < n; i++) {
            words[i] = inputProcessor.next();

            for(char c : words[i].toCharArray()) {
                unique.add(c);
            }
        }

        alphabets = unique.toArray(Character[]::new);
        result = Integer.MIN_VALUE;
        alphabet = new int[27];
    }

    private static void pro() {
        rec(0, 0, alphabets.length);

        sb.append(result);
    }

    private static void rec(int used, int idx, int len) {
        if(idx == len) {
            int sum = 0;
            for(String w : words) {
                sum += convert(w);
            }

            result = Math.max(result, sum);
            return;
        }

        for(int i = 9; i >= 0; i--) {
            if((used & (1 << i)) != 0) continue;

            int j = alphabets[idx] - 'A';

            used |= (1 << i);
            alphabet[j] = i;

            rec(used, idx + 1, len);

            alphabet[j] = -1;
            used &= ~(1 << i);
        }
    }

    private static int convert(String word) {
        int result = 0;
        for(char c : word.toCharArray()) {
            result *= 10;
            result += alphabet[c - 'A'];
        }

        return result;
    }

    private static void output() {
        try (BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            bw.write(sb.toString());
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static class InputProcessor {
        private BufferedReader br;
        private StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String result = "";

            try {
                result = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return result;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}

 

 

제출 코드2. 그리디

import java.util.*;
import java.io.*;

public class Main {
  private static StringBuilder sb = new StringBuilder();
    private static InputProcessor inputProcessor = new InputProcessor();

    public static void main(String[] args) {
        input();
        pro();
        output();
    }

    private static int n;
    private static String[] words;

    private static void input() {
        n = inputProcessor.nextInt();

        words = new String[n];
        for(int i = 0; i < n; i++) {
            words[i] = inputProcessor.nextLine();
        }
    }

    private static void pro() {
        int[] alphabets = new int[27];
        for(String word : words) {
            int len = word.length();
            for(char c : word.toCharArray()) {
                alphabets[c - 'A'] += (int) Math.pow(10, --len);
            }
        }

        Arrays.sort(alphabets); // 오름차순

        int multipleNumber = 9;
        int result = 0;
        for(int i = 26; i >= 0; i--) {
            if(alphabets[i] == 0) break;

            result += (alphabets[i] * multipleNumber);
            multipleNumber -= 1;
        }

        sb.append(result);
    }

    private static void output() {
        try (BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            bw.write(sb.toString());
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static class InputProcessor {
        private BufferedReader br;
        private StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String result = "";

            try {
                result = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return result;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}