DAT, Count Sorting

# practice 1
a = [4, 9, 1, 4, 4, 2]
b = [1, 3, 4, 2, 5, 6, 7, 8, 9]

for i in range(len(b)):
    c = 0
    for j in range(len(a)):
        if a[j] == b[i]:
            c = 1
            break
    if c == 1:
        print('O',end=' ')
    else:
        print('X',end=' ')

# practice 2 -DAT
a = [4, 9, 1, 4, 4, 2]
b = [1, 3, 4, 2, 5, 6, 7, 8, 9]

bucket = [0]*20 # O,X를 담을 바구니

for i in range(len(a)): # a에 있는 애들을 먼저 바구니에 체크 해주기
    index = a[i] # 여기의 index는 바구니의 index 번호
    bucket[index] = 1 # 해당 index에만 1을 넣어줌 - a가 있는곳이 표시됨

for i in range(len(b)): #b와 bucket을 비교 - bucket안에 a의 숫자 유무 있으니까!
    if bucket[b[i]] == 1: # b[i]는 b의 값을 뜻하는데 이게 bucket의 인덱스 번호가 되며, 만약 1이라면 b in a
        print('O', end=' ')
    else:
        print('X', end=' ')

# practice 3
# n개의 숫자를 입력 받은 후
# 어떤 숫자가 몇 개 입력 되는지 출력

n = int(input()) # 10
arr = list(map(int, input().split())) # 1 2 4 1 4 3 5 8 7 3

bucket = [0] * n #바구니 만들기

for i in range(n): #우리가 반복 해야할 범위
    bucket[arr[i]] += 1 # arr[i]는 바구니의 인덱스. 우리는 각 숫자가 몇 번 나왔는지 궁금! 따라서 1씩 추가!

for i in range(len(bucket)): #이제 바구니를 돌며 각 인덱스의 값을 출력
    if bucket[i] > 0: # 없는 숫자들은 굳이 출력 안해도 되기 때문에 if문 이용
        print(i,'가',bucket[i],'개 있음')


# COUNTING SORT -- 우리의 목적 sort함수를 구현해 내는 것!
# 1. bucket등록, 0초기화
# 2. 누적 합 구하기
# 3. 값을 넣기

# practice 1
# n개의 숫자를 입력 받은 후 (1~100까지의 숫자를 입력 받는다 가정)
# counting sort 이용해 출력 하기

n = int(input()) # 9
arr = list(map(int,input().split())) # 4 7 9 1 3 5 2 3 4
bucket = [0]*101

#dat등록
for i in range(n):
    bucket[arr[i]] += 1 # arr의 값은 bucket의 index이며, arr 값에 해당하는 bucket index에 1을 추가하며 count

#누적합
for i in range(1, len(bucket)): # 시작을 1로하여 순회 (이때 bucket의 len값은 100으로 우리가 입력한 n보다 작음)
    bucket[i] += bucket[i-1]  #1부터 시작하기 때문에 그 전값을 더하여 누적

#값넣기
temp = [0]*101 # bucket과 같은 수의 temp list를 만들어줌
for i in range(n): # arr을 오름차순으로 배열하기 위해 for문을 돌려줌
    temp[bucket[arr[i]]] = arr[i] 
    # bucket의 index는 위와 같이 arr[i]이며, bucket의 값은 temp의 index가 되고, 이 자리에 arr[i] 값이 들어감
    bucket[arr[i]] -=1 
    # arr[i]중 같은 숫자가 있는데, 그 같은 숫자 중 뒤쪽에 해당하는 것을 고정해주는건데, 
    # 따라서 arr[i]를 배치함에 따라 해당 bucket index의 값을 1씩 차감해줘야 함

#출력하기
for j in temp:
    if j > 0: #temp가 0~100까지 인덱스를 가지므로,, 우리가 필요한 값 출력을 위해 0이상만 출력!
        print(j, end=' ') # 1 2 3 3 4 4 5 7 9

COUNT SORTING