프로그래머스 - 숫자 블록 [Java]

이 문제는 Map을 이용해서 풀었다.

 

도로의 길이가 10억이므로 배열로 만들면 메모리 초과가 나게 된다.

주목할 점은 end - begin이 5000밖에 안된다는 점이다. 따라서 해당 부분만 저장하면 된다는 생각을 했고, Map을 이용해서 해당 범위 안의 숫자들을 저장했다.

 

정직하게 반복문을 돌려 1부터 1,000만까지 계산하면 당연히 시간 초과가 난다. 1의 경우 2부터 10억까지를 루프를 돌리기 때문이다. 따라서 num * 2가 begin보다 작을 경우를 두어 이 때는 연산을 통해 한번에 시작 숫자를 찾아내야 한다.

 

위 부분만 구현해낼 수 있으면 한 번에 문제를 풀 수 있다.

import java.util.*;

class Solution {
    
    Map<Integer, Integer> numbers = new HashMap<>();
    int begin;
    int end;
    
    public int[] solution(long b, long e) {
        Long wrapBegin = b;
        Long wrapEnd = e;
        
        begin = wrapBegin.intValue();
        end = wrapEnd.intValue();
        
        for (int i = begin; i <= end; i++) {
            numbers.put(i, 0);
        }
        
        for (int num = 10000000; num >= 1; num--) {
            if (num * 2 < begin) {
                final int start = findFirst(num);
                
                calculate(start, num);
            } else if (inRange(num * 2)) {
                calculate(num * 2, num);
            }
        }
        
        final int[] answer = makeAnswer();
        
        return answer;
    }
    
    int[] makeAnswer() {
        List<Integer> results = new ArrayList<>();
        
        for (int i = begin; i <= end; i++) {
            final int number = numbers.get(i);
            
            results.add(number);
        }
        
        return results.stream().mapToInt(Integer::intValue).toArray();
    }
    
    int findFirst(final int addition) {
        final int temp = begin / addition;
        
        final int result = addition * temp;
        
        if (inRange(result)) {
            return result;
        }
        
        return result + addition;
    }
    
    void calculate(final int num, final int addition) {
        for (int i = num; i <= end; i += addition) {
            if (numbers.get(i).equals(0)) {
                numbers.put(i, addition);
            }
        }
    }
    
    boolean inRange(final int num) {
        if (begin <= num && num <= end) {
            return true;
        }
        return false;
    }
}