[Codility(코딜리티)] Lesson3. PermMissingElem (100%)

Lesson 3 Time Complexity - PermMissingElem (Java Solution)

app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

PermMissingElem coding task - Learn to Code - Codility

---

문제

배열 A가 주어지는데, N개의 다른 정수들로 구성되어있다

배열은 1~N+1 범위안의 정수들로 구성된다 

그것은 정확히 1개의 정수가 빠진다는 것을 의미한다 

그 1개의 정수를 출력한다

 

예를 들면, A = {2,3,1,5} 배열이 주어진다

A[0] = 2, A[1] = 3, A[2] = 1, A[3] =5

 

N=4, 1~5까지의 정수들에서 4가 빠졌다

그 빠진 정수 4를 출력한다

해결

우선 Map을 하나 만들어서, Key를 1~N+1까지 넣는다

그리고 A 배열에서 하나씩 값을 꺼내어 map에서 해당 키를 제거한다

결국 1개의 키만 남을 것이고 그거를 꺼내어 출력한다

public class PermMissingElem {
    public int solution(int[] A) {
        HashMap<Integer, String> map = new HashMap<>();
        for (int i=1; i<=A.length+1; i++) map.put(i, "ok");
        for (int i : A) map.remove(i);
        return map.keySet().stream().findFirst().get();
    }
 }

자바 11에서는 100%로 이지만,

 

자바 8에서는 80%가 나왔다. 이전 Lesson2와 같은 문제이다

비트연산 XOR 풀이

자바 8로는 계속 100%가 안나와서 다른 방법을 생각해봤다 

생각해보니, 어제 풀었던 Lesson2의 OddOccurrencesInArray와 거의 비슷한 문제다

 

https://jackjeong.tistory.com/16

[Codility(코딜리티)] Lesson2. OddOccurrencesInArray (Arrays)

문제 내용만 다를 뿐, 쌍으로 존재하지 않는 정수를 구하면 된다

이 문제도 비트연산 XOR로 풀어보았다

List에 A배열 담고, A의 배열 길이가 N이면 1~N+1의 값을 추가로 담는다

그리고 이 List의 모든 값을 비트연산 XOR을 수행하면 

같은 값은 0이 되고 정답만 남을 것이다

public class PermMissingElem {
    public int solution(int[] A) {
        List<Integer> list = new ArrayList<>();
        for (int i : A) list.add(i);
        for (int i=1; i<=A.length+1; i++) list.add(i);
         
        // reduce()로 연산하면 결과값은 같았지만, 점수는 80%가 나온다
        //return list.stream().reduce((a, b) -> a ^ b).get();
        
        int result = 0;
        for (int i : list) {
            result = result ^ i;
        }
        return result;
    }
}

stream()으로 바꾼 후, reduce로 연산했더니 위와 같은 결과로 자바 8에서 80%가 나왔다

그래서 단순 for 문을 돌면서 비트연산 XOR를 수행했더니 자바 8에서도 100%가 나왔다