[AlphaGo Study] [LeetCode] [JAVA] 448. Find All Numbers Disappeared in an Array

 

문제 설명

 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array.

 Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

입출력 예

Input	Output
[4, 3, 2, 7, 8, 2, 3, 1]	[5, 6]

입출력 예 설명

#예제

 n=8일 때, 위의 Input과 같이 저장되어 있다. 이 때, 5와 6이 없으므로 Output은 5, 6이 된다.

 

leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Find All Numbers Disappeared in an Array - LeetCode

---

문제를 풀기 전 THINK

• n개의 수를 저장하는 배열에서, 없는 수를 찾아 출력한다.
• nums[i]의 값을 index로 가지고 있는 boolean 배열 checkArray를 만든다.
• 있으면 true, 없으면 false로 저장한다.
• 다음의 for문에서, checkArray가 faluse이면 nums[i]의 값이 없는 것이므로 해당 i를 result에 추가한다.

위의 Input, Output으로 예를 들어보자면, 첫 번째 for문에서 checkArray[nums[0]] = checkArray[1] 이므로 checkArray[1]의 값은 true.

 

이렇게 쭉 해보면,

checkArray[1]	checkArray[2]	checkArray[3]	checkArray[4]	checkArray[5]	checkArray[6]	checkArray[7]	checkArray[8]
true	true	true	true	false	false	true	true

이 때, checkArray[5]와 checkArray[6]이 없으므로 해당 i값인 5와 6을 출력하는 것이다.

나의 Solution

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

public class FindAllNumbers {
	public List<Integer> findDisappearedNumbers(int[] nums) {
		List<Integer> result = new ArrayList<Integer>();
		boolean[] checkArray = new boolean[nums.length + 1]; 
		
		for(int i = 0; i < nums.length; i++) {
			// nums[i]의 값이 있으면 true
			checkArray[nums[i]] = true;
		} // for end
		
		for(int i = 1; i < nums.length; i++) {
			// checkArray가 false면
			// nums[Input]할 때 Input의 값이 없어서 nums[Input]의 값이 null이라는 뜻
			if(checkArray[i] == false) {
				result.add(i);
			} // if end
		} // for end
		
		return result;
	}

}