[알고리즘] 프로그래머스 2단계 - 멀리 뛰기

프로그래머스 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12914

 

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

 

입출력 예제

n

4

 

result

5

 

결과적으로 시간초과와 메모리로 실패했다.

추후에 객체와 변수 선언 최소화를 하고 진행하면서 수정해야겠다.

import java.util.*;

class Solution {
    public long solution(int n) {

        ArrayDeque<LinkedList<Integer>> deque = new ArrayDeque<>();
		
        // 순서보장을 위해서 링크드 리스트를 키로 설정
        HashMap<LinkedList<Integer>, Integer> map = new HashMap<>();
		
        // 1번 시작
        deque.add(new LinkedList<>(Arrays.asList(1)));
		
        // 2번으로 시작
        deque.add(new LinkedList<>(Arrays.asList(2)));
		
        int cnt = 0;

        int sum = 0;

        while (!deque.isEmpty()) {
            LinkedList<Integer> pop = deque.pop();
			
            //총 합 계산 후 카운트
            sum = pop.stream().mapToInt(i -> i).sum();

            if (sum > n) {
                continue;
            } else if (sum == n) {
                cnt++;
            }
	
    		// 여기서 새로운 메모리 할당되서 메모리 오버되는 것 같다.
            LinkedList<Integer> addOneList = new LinkedList<>(pop);
            LinkedList<Integer> addTwoList = new LinkedList<>(pop);
			
            // 1번
            addOneList.add(1);

			// 2번
            addTwoList.add(2);

			// 존재 여부 체크
            if (map.getOrDefault(addOneList, 0) == 0) {
                deque.add(addOneList);
                map.put(addOneList, 1);
            }
            if (map.getOrDefault(addTwoList, 0) == 0) {
                deque.add(addTwoList);
                map.put(addTwoList, 1);
            }

            sum = 0;
        }
        return cnt;
    }
}