[Algorithm] 백준 정렬 파트 (2108,18870)

백준 알고리즘 단계별로 풀어보기 중
정렬 단계를 모두 풀어봤다. 그중 2108번과 18870에서
어려움을 겪어 기록을 남기게 되었다.

개요

정렬은 이전 기록에서 다룬 적이 있다.

[Algorithm] 정렬 방법, 구현(선택, 버블, 삽입, 병렬, 퀵, 계수)

때문에 백준 알고리즘 정렬 단계에서 대부분의 문제들을 무난하게 풀어냈다.

정렬 단계

 

하지만, 2108번과 18870번에서 어려움을 겪어 이에 대한 기록을 남기려고 한다.

 

2108번

2108번: 통계학

이 문제는 계수 정렬을 사용해야 한다.

문제에서 정수의 절댓값을 4000으로 한정했기 때문에

계수 정렬이 가장 효율적일 것이라고 추측했어야 했는데 그러지 못했다.

 

문제에서는 입력 수의 개수와 개수만큼의 수를 입력으로 주고,

산술 평균, 중앙값, 최빈값, 범위를 구하라고 한다.

 

최빈값은 가장 많이 나온 정수를 뜻하며, 여러 개일 경우 두 번째로 작은 값을 출력하라고 한다.

이 최빈값을 구하는 과정에서 어려움을 겪었다.

import sys
input=sys.stdin.readline
N=int(input())
arr=[0]*8001
max=0
count=1
for i in range(N):
    n=int(input())
    arr[n+4000]+=1
    if arr[4000+n]>max:
        max=arr[4000+n]
        num=n
        count=1
    elif arr[4000+n]==max:
        count+=1
result=[]
for i in range(8001):
    if arr[i]>0:
        for _ in range(arr[i]):
            result.append(i-4000)
print(round(sum(result)/N))
print(result[N//2])
if count==1:
    print(num)
else:
    print(arr.index(max,arr.index(max)+1)-4000)
print(result[N-1]-result[0])

위 코드가 내가 해결한 코드이다.

 

최빈값에 대해서는 계수 정렬을 위해 먼저 정해진 범위만큼에 대한 배열에 

해당 정수가 나온 개수를 값으로 설정한다.

이 과정에서 최빈값을 찾아내고, 해당 최빈값을 가지는 정수의 개수를 count에 기록한다.

 

count가 1일 경우엔 최빈값이 하나이므로 그 수를 출력하고,

2 이상일 경우 최빈값이 두 개 이상이므로 두 번째로 작은 수를 출력해야 한다.

따라서 첫 번째 최빈값의 인덱스+1부터 끝까지 최빈값을 찾아냄으로써 두 번째로 작은 수를 찾아내는 방법을 사용했다.

 

18870번

18870번: 좌표 압축

이 문제에서는 계속 시간 초과 오류가 났다.

 

처음 set을 이용해 문제를 풀어야겠다는 생각은 해냈지만,

각 요소에 대한 좌표를 압축하는 데에 시간 복잡도가 O(N) 임에도 시간 초과 오류가 났다.

 

해답은 dict 자료형을 사용하는 것이다.

이렇게 되면 O(1)의 시간 복잡도로 문제를 해결할 수 있다.

import sys
input=sys.stdin.readline
n=int(input())
arr=list(map(int,input().split()))
sArr=list(sorted(set(arr)))
dict={sArr[i]:i for i in range(len(sArr))}
for i in arr:
    print(dict[i], end=' ')

위처럼 배열을 set 형태로 바꾸고 정렬해주면,

각 요소의 인덱스가 해당 요소의 압축된 좌표임을 알 수 있다.

이를 dict에 저장하고 출력하면 쉽게 해결할 수 있다.