AbsDistinct

🔗 문제 링크

https://app.codility.com/programmers/lessons/15-caterpillar_method/abs_distinct/start/

❔ 문제 설명

A non-empty array A consisting of N numbers is given. The array is sorted in non-decreasing order. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.

For example, consider array A such that:

A[0] = -5
A[1] = -3
A[2] = -1
A[3] = 0
A[4] = 3
A[5] = 6

The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.

Write a function:

def solution(A)

that, given a non-empty array A consisting of N numbers, returns absolute distinct count of array A.

For example, given array A such that:

A[0] = -5
A[1] = -3
A[2] = -1
A[3] = 0
A[4] = 3
A[5] = 6

the function should return 5, as explained above.

⚠️ 제한사항

• N is an integer within the range [1..100,000];

• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647];

• array A is sorted in non-decreasing order.

---

💡 풀이 (언어 : Python)

DFS, BFS 관련 문제라는 것을 알고도 쉽게 코드를 작성하지 못하였다. 한 번 배워서 바로 활용하는 것은 역시 불가능한 것 같다. 다른 사람의 풀이를 보고 다시 연습하며 작성해보았다.
다음에 유사한 문제를 만나면 그땐 제대로 활용할 수 있으면 좋겠다.

def solution(A):
    # 이미 카운트된 숫자인지 체크할 딕셔너리. 리스트보다 조회가 빨라서 사용했다.
    dic = {key : 0 for key, value in dict.fromkeys(A).items()}
    count = 0
    for i in range(len(A)):
        # 이미 앞에서 나온 수는 카운트 안하고 다음으로 넘어감
        if dic.get(A[i]) != 0:
            continue
        # 새로 나온 숫자와 그 반대 부호 수는 딕셔너리에서 value를 1로 해주고 개수 카운트    
        else:
            dic[A[i]], dic[-A[i]] = 1, 1
            count += 1

    return count