백준 10816번 : 숫자카드 2

카운팅 정렬에 대해 배웠다 생각하고 가볍게 생각하고 들어갔다가 한시간 헤매고 온 문제이다.. 정확히는 카운팅 정렬은 할 줄 알지만 내 머릿속에 생각나는 대로만 구현하려고 하다보면 항상 시간 복잡도를 넘고는 한다. 여유가 된다면 시간 복잡도에 대한 간단한 정리를 해서 문제 푸는데 헛 시간을 보내지 않는 연습을 해야할 것 같다.

---

제출 코드 - 메모리 : 365172KB, 시간 608ms, 시간복잡도 : O(n + m)

import sys

input = sys.stdin.readline

N = int(input())

arr_N = list(map(int, input().split()))

M = int(input())

arr_M = list(map(int, input().split()))

arr = [0] * 20000001

for idx in arr_N:

    arr[idx] += 1

for idx in arr_M:

    print(arr[idx], end =' ')

 

내가 이겼다 이 악마야.

---

 

문제를 이해하는 것은 간단하다. N에 주어진 배열들이 M에 해당하는 데이터들이 몇번 나오는지 보는 것이다. 하지만 구현을 기준으로 하다보면 숫자를 보곤 놀랄 것이다. 배열 속 정수의 크기는 -10,000,000 부터 10,000,000까지이며 총 500,000개까지 주어질 수 있는 어마무시한 갯수다. 질문게시판 가보면 시간 초과를 굉장히 많이 보신 것 같은데, 내가 정답률 낮추는데에 기여를 하고 왔다.

 

첫번째 제출
O(n * m)

import sys

input = sys.stdin.readline

N = int(input())

arr_N = list(map(int, input().split()))

M = int(input())

arr_M = list(map(int, input().split()))

arr = [0]* M

for i in arr_N:

    for j in range(M):

        if i == arr_M[j]:

            arr[j] += 1

result = arr[:M:]

print(*result)

 

처음에는 빈 배열은 M 개 만큼만 만들었고, N 배열을 돌리면서 M의 인덱스를 찾아 빈 배열에 카운팅을 해주는 방법이었다. 이 과정에서 최악의 경우 arr_N 이 500,000개, M도 500,000개를 가정하면 250,000,000,000번에 if문까지 들어갔으니 시간초과가 날 수 밖에 없었다. 아직 기분은 좋았다. 그 이유는 내가 생각했던 구현이 되었을 때의 기분은 좋다. 디버깅 필요없이 답이 바로 나왔으니... 아직은.. 좋았다.

두번째 제출
O(n * m)

import sys

input = sys.stdin.readline

N = int(input())

arr_N = list(map(int, input().split()))

M = int(input())

arr_M = list(map(int, input().split()))

arr = [0] * 500000

for i in arr_N:

    if i in arr_M:

        arr[arr_M.index(i)] += 1

print(*arr[:M:])

 

그래 그러면 input의 개수로 들어올 수 있는 최대 갯수는 500,000개니까 그 크기의 배열을 넣고 가보자! 하며 for문을 하나 줄였지만.. 내 뇌는 index 메서드를 사용해야한다더라.. 이 역시 arr_M이 500,000개를 가정하면 찾으러 다녀야하기 때문에 시간 초과가 발생하더라. 그럼 이번엔 if문을 없애볼까며 고민했다.

세, 네번째 제출
O(n * m)

 

import sys

input = sys.stdin.readline

N = int(input())

arr_N = list(map(int, input().split()))

M = int(input())

arr_M = list(map(int, input().split()))

for i in arr_M:

    print((arr_N.count(i)), end = ' ')

 

 

import sys

input = sys.stdin.readline

N = int(input())

arr_N = list(input().split())

M = int(input())

arr_M = list(input().split())

for i in arr_M:

    print((arr_N.count(i)), end = ' ')

 

 

그래 아싸리 카운팅을 쓰자며 출력하는 코드를 단 두줄로 짰을때, 제법 내가 대단해진줄 알았다. 개깔끔해!! 라며 좋아하던 기쁨도 잠시.. 아뿔싸. count도 결국 시간복잡도가 O(n)이라는 것을 간과했다. 그치.. 이렇게 풀리면 실버가 아니겠지.. 그래도 input의 배열을 불러올때 정수 변환식도 필요없다 생각해서 삭제했다. 이러면서 조금씩 성장하는게 아닐까?

 

다섯번째 제출
O(n * m)

import sys

input = sys.stdin.readline

N = int(input())

arr_N = list(input().split())

dct = {}

M = int(input())

arr_M = list(input().split())

for i in range(M):

    dct[arr_M[i]] = 0

for j in arr_N:

    if j in arr_M:

        dct[j] += 1

for k in arr_M:

    print(dct[k], end = ' ')

 

이번엔 잘 사용하지 않는 dict를 사용해봤다. 질문게시판보면 딕셔너리로 많이 풀던데.. 왜 나는 맨날 시간복잡도가 하나 마나 같은지 모르겠다. key - value를 정수-카운트로 만들어서 등장할때마다 카운팅을 증가시켰다. list와 다른점은 찾을때 시간 복잡도가 보통 O(1)이라고 해서 사용을 한것인데 결국 cnt올리는 과정에서 시간복잡도가 매우 커지는 것 같았다.

 

전혀.. 성장하지 않았어..?

 

대망의 여섯번째 제출
O(n + m)

import sys

input = sys.stdin.readline

N = int(input())

arr_N = list(map(int, input().split()))

M = int(input())

arr_M = list(map(int, input().split()))

arr = [0] * 20000001

for idx in arr_N:

    arr[idx] += 1

for idx in arr_M:

    print(arr[idx], end =' ')

 

처음 생각했던 방식을 제대로 사용했어야 하는데, 제대로 공부를 안해놓으니 카운팅 정렬을 어떻게하는지도 모르고 막 사용했던 것 같다. 심지어 카운팅 정렬 끝까지 가는 것도아니고 중간만 하면되는 것인데.. 일단 배열의 범위를 N과 M이 나올 수 있는 모든 경우에 여유 한칸까지 20,000,001개를 생성한다. 이후 N배열의 데이터를 순회하면서 해당 데이터 idx를 그대로 0으로 이루어진 arr 배열에 카운팅을 넣어준다.

이후 출력 역시 반복문을 통해 idx 호출을 하여 표현해주었다. 이렇게 하면 반복문은 한개로만 풀이가 가능하기 때문에 시간 복잡도가 개선되었다는 것을 알 수 있다.

 

6개의 모든 코드의 시간 복잡도를 확실히 알기위해 GPT에 확인해보니 굉장히 친절하더라.. 각 구간별 시간 복잡도를 계산해주며 개선 방향도 알려준다. 제일 마음에 들었던 것은. 

마지막줄 보니 이전 코드보다 효율적으로 개선되었단다.. 고마워 ㅠㅠ