[코테]코딜리티 - FrogRiverOne

문제

문제 요약

• 개구리가 강을 건너야함. 현재 위치는 0임.
• X + 1만큼의 강건너편으로 가기 위하여 떨어지는 나뭇잎 개수의 배열 A가 주어짐.
• 개구리가 건널 수 없으면 -1을 리턴함.
• A는 중복이 가능한 숫자로 이루어진 배열임.
• 개구리는 건너야하는 모든 구간에 나뭇잎이 떨어져야 건너갈 수 있음.
• 예를 들어 배열에 1~5까지의 원소가 있으면 1~5까지 나뭇잎이 다 떨어져 있는 상태여야함.
• 배열의 요소 하나하나가 나뭇잎의 위치번호임.
• 1 <= N, X <= 100,000
• 1 <= 각 요소 <= X

문제 분석

다음 단계에 따라 문제를 분석하였다.

• 먼저 개구리의 위치에서 X까지는 가기 위해서는 1씩 증가되는 위치에 모든 나뭇잎이 깔려야함.
• 배열의 정수는 반복되어 주어질 수 있음.
• 개구리가 밟고 지나가야하는 나뭇잎은 순서대로 나열되지 않음.
• 개구리가 강을 건너지 못하는 즉, 요소 중 빠진 숫자가 있거나 부족하면 -1을 리턴함.
• 최악의 범위는 배열의 길이 100,000과 X의 범위 100,000임. 숫자를 비교해서 판단하려면 O(n^2)의 시간복잡도 즉, 100억번의 연산이 필요함.
• 시간 복잡도를 단축하기 위하여 중복을 허용하지 않는 자료구조를 이용하여 해당 자료구조의 길이를 통해 결과를 도출
• 이렇게 진행할 경우 시간 복잡도는 o(n)의 시간복잡도를 가짐.

슈도코드

배열의 요소를 담을 Set을 선언(중복불허)

for(A의 길이만큼 수행){
	Set에 요소를 하나씩 add
    
    if(Set의 길이가 X와 동일하면) return 인덱스;
}

반복문이 정상종료되면 return -1;

구현코드

import java.util.Set;
import java.util.HashSet;

pubilc class Solution{
	public int solution(int X, int[] A){
    	Set<Integer> set = new HashSet<>();
        
        for(int i = 0; i < A.length; i++){
        	set.add(A[i]);
            
            if(set.size() == X) return i;
        }
        
        return -1;
    }
}

위와 같은 코드는 Time Out을 몇번을 치루고야 나왔다. 이전의 코드는 정확성은 100%이지만 퍼포먼스 측면은 0%이었다. 코드는 다음과 같다.

시간초과 코드

import java.util.List;
import java.util.ArrayList;

pubilc class Solution{
	public int solution(int X, int[] A){
    	List<Integer> list = new ArrayList<>();
        
        for(int i = 1; i <= X; i++){
        	list.add(i);
        }
        
        for(int i = 0; i < A.length; i++){
        	// 매개변수로 Object를 넣어줘야 value를 찾아 삭제함.
			list.remove(Integer.valueOf(A[i]);
            if(list.size() == 0) return i;
        }
        
        return -1;
    }
}

여기서 나는 시간복잡도를 O(X+n)으로 판단했는데 문제는 그게 아니었다. List의 자료구조 특성상 remove를 하기 위해 인덱스가 아닌 value를 찾는 것은 list를 순회하며 수행된다는 사실을 고려하지 않은 것이다. 문제를 다 풀고서야 TimeOut을 보고 깨달았다. 다른 분들은 이런 실수를 하지 않기 바라는 마음에서 적어본다.