[Codility] Lesson 4 - Frog River One 풀이 (java)

Codility Frog River One 문제풀이

문제 요약

https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

FrogRiverOne coding task - Learn to Code - Codility

• 배열 A[N] 와 int X가 주어진다 
• N, X 은 최대 10만, 최소 1, not empty 이다
• 배열 A[N] 값은 최소 1, 최대 X 이다
• A[0] 에서 시작하여 A[N] 까지 값을 확인한다
• 1 ~ X 범위의 모든 숫자를 확인가능한 A 배열의 index값을 출력하라
• 만약 숫자 누락이 발생한다면 -1 을 출력하라

 

풀이

• N 이 최대 10만 밖에 안되기 때문에 값의 유무를 배열에 저장하면된다.
• Exist[i] = i번 값이 나타난 최소 index
• O(N) 만큼의 시간복잡도를 사용하여 Exist[i] 배열에 반영하고 
• O(N) 만큼의 시간복잡도를 사용하여 누락여부 및 최소 인덱스( Max(Exist[i]))를 계산한다. 
• 최종 시간복잡도 O(2N)

class Solution {
    public int solution(int X, int[] A) {
        int[] countArray = new int[X+1];
		int result = 0;
		
		// 초기값 -1 세팅
		for(int i = 1; i < countArray.length; i++) {
			countArray[i] = -1;
		}
		
        // A[i]는 countArray의 index로 사용
        // i는 countArray의 value로 사용
		for(int i = 0; i < A.length; i++) {
			if(countArray[A[i]] == -1 
            || countArray[A[i]] >= i) {
				countArray[A[i]] = i;
			}
		}
		
        // countArray 을 탐색하며 -1 리턴 조건 탐색
		for(int i = 1; i < countArray.length; i++) {
			if(countArray[i] < 0) {
				result = -1;
				break;
			}else if(result < countArray[i]){
				result = countArray[i];
			}
		}
		
		return result;
    }
}