Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 냄새와 휴리스틱
- Dxerr.h
- 가장 긴 증가하는 부분 수열2
- SerialDate 리펙터링
- 백준
- 코딩테스트
- 2166번
- programmers
- 1300번
- 코딩 테스트
- 10830번
- 2156번
- 프로그래머스
- Adapater Pattern
- springboot
- 9장
- java
- Design Pattern
- 클린코드
- java의 정석
- 17장
- 2206번
- Spring
- 11758번
- 1043번
- DxTrace
- Design Patterns
- 11286번
- BOJ
- 자바의 정석
Archives
- Today
- Total
Don't give up!
[백준] 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)로 구할 수 있으며, 평균을 내기 위해서 각 자리의 숫자들을 몇번 곱해야 모든 경우의 수를 나타낼 수 있는지 미리 기억한다면 더 빠르게 결과를 도출할 수 있습니다.
'Coding Test > BOJ' 카테고리의 다른 글
[백준] 1051번 : 숫자 정사각형 (java) (0) | 2021.07.19 |
---|---|
[백준] 1013번: Contact (java) (0) | 2021.07.16 |
[백준] 1107번 : 리모컨 (java) (0) | 2021.07.16 |