[백준] 1089번 : 스타트링크 타워

1089번: 스타트링크 타워 (acmicpc.net)

1089번: 스타트링크 타워

어떻게 생각하고 문제를 풀었는가?

0~9의 숫자에 해당하는 문자들을 미리 생성한 후, 5줄의 문자열과 비교하여 가능한 숫자들을 찾아낸 후 평균을 낸다면 문제를 해결할 수 있을 것이라고 생각하였습니다.

그러나 가능한 숫자들을 모두 String 또는 Double로 생성하고 평균을 내는 코드에 대해서는 메모리 초과가 발생하였는데, 이를 해결하고자 경우의 수를 모두 저장하는 것이 아닌 각 자리에 대해서 가능한 숫자들을 N개의 Collection에 저장한 후 평균을 구하는 방식을 사용하고자 하였습니다.

그 결과 N개의 자리를 갖는 입력에 대해 최대 10^N이 아닌 10N의 공간 효율을 만들 수 있었습니다.

코드

import java.io.*;
import java.util.*;
//1089
class Main {
    static final String[] NUMS = {
            "####.##.##.####",
            "..#..#..#..#..#",
            "###..#####..###",
            "###..####..####",
            "#.##.####..#..#",
            "####..###..####",
            "####..####.####",
            "###..#..#..#..#",
            "####.#####.####",
            "####.####..####"
    };
    static String[] map = {"","","","",""};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<5; i++){
            map[i] = br.readLine();
        }
        HashSet<Double>[] set = new HashSet[N];
        for(int i=0; i<N; i++) set[i] = new HashSet<>();
        int strLen = 4*N-1;
        int totalSize = 1;
        int[] digitCount = new int[N];
        Arrays.fill(digitCount,1);
        for(int i=0; i<5; i++){
            for(int j=0; j<strLen; j+=4){
                int index = j/4;
                for(int k=0; k<10; k++){
                    double value = Math.pow(10, N-1-index)*k;
                    if(canNum(i,j,k)){
                        if(i==0){
                            set[index].add(value);
                        }
                    }else{
                        set[index].remove(value);
                    }
                }
                if(set[index].size()==0){
                    System.out.println("-1");
                    return;
                }
                if(i==4){
                    totalSize = totalSize * set[index].size();
                    for(int k=0; k<N; k++){
                        if(k!=index) digitCount[k] = digitCount[k]*set[index].size();
                    }
                }
            }
        }
        double sum = 0;
        for(int i=0; i<N; i++){
            double multi = (double) digitCount[i] / totalSize;
            sum += set[i].stream().mapToDouble(x -> x).map(x -> x * multi).sum();
        }
        System.out.println(sum);
        br.close();
    }
    static boolean canNum(int row, int index ,int compareTo){
        for(int i=0; i<3; i++){
            if(map[row].charAt(index+i)!='.' && map[row].charAt(index+i)!=NUMS[compareTo].charAt(row*3+i)) return false;
        }
        return true;
    }
}

N개의 HashSet을 사용하여 코드를 구현하였습니다.

첫번째 줄부터 가능한 수들을 각 자리에 해당하는 HashSet에 저장하고, 2~5번째 줄까지 검사하였을 때 불가능한 숫자들을 HashSet에서 삭제하여 가능한 숫자들을 얻어낼 수 있습니다.

각 자리의 숫자들은 k x 10^(N-1-index)로 구할 수 있으며, 평균을 내기 위해서 각 자리의 숫자들을 몇번 곱해야 모든 경우의 수를 나타낼 수 있는지 미리 기억한다면 더 빠르게 결과를 도출할 수 있습니다.