📝정렬의 개념
🤷♂️정렬은 어디에 사용될까?
✏️문제풀이
[S2]18870] 좌표 압축
🟧 시도 1
딕셔너리를 이용해서 받은 값들을 딕셔너리에 저장하되 값은 전부 0으로 두고, 정렬된 값에 따라 키에 맞는 정렬된 순서값을 부여하는 방법으로 진행하였다.
첫 예제 입력인
5
2 4 -10 4 -9
에서는 정답이 나왔으나, 두번째인
6
1000 999 1000 999 1000 999
에서는 원하던 값이 나오지 않아 다른 방법을 찾았다.
# 딕셔너리를 이용해서 해당 숫자가 몇 번째 인지 저장하는 건 어때
n = int(input())
ary = list(map(int,input().split()))
ary2 = ary[:]
ary2.sort()
dic = {}
for i in range(n):
dic[ary[i]] = 0
for j in range(n):
if dic[ary2[j]] == 0:
dic[ary2[j]] = j
for k in range(n):
print(dic[ary[k]])🟧 시도 2
이미 중복된 값에서까지 값을 찾아내는 것이 문제이니 이미 중복된 값을 제거하는 set함수를 적용시킨 후 예제를 입력하니 모두 정답은 나왔다.
# 딕셔너리를 이용해서 해당 숫자가 몇 번째 인지 저장하는 건 어때
n = int(input())
ary = list(map(int,input().split()))
ary2 = ary[:]
ary2 = list(set(ary2))
ary2.sort()
dic = {}
for i in range(n):
dic[ary[i]] = 0
print(ary2)
for j in range(len(ary2)):
if dic[ary2[j]] == 0:
dic[ary2[j]] = j
for k in range(n):
print(dic[ary[k]], end=' ')[S3]2108] 통계학
🟧 시도 1
다른 사람들도 마찬가지겠지만 최빈값을 출력하는데 있어서 조금 애를 먹었다. 최빈값을 얻기 위해 받은 숫자들을 딕셔너리로 표현하고 해당 숫자가 등장할 때마다 값을 올려준 후 sorted를 통해 딕셔너리의 value를 기준으로 정렬을 했는데 문제점이 최빈값이 2개가 있을 경우 최빈값 중에서 두 번째로 작은 값을 출력하는 부분이었다.
첫째 시도 코드에서는 단순 정렬함수를 사용하였기 때문에 다른 방법을 찾아야했다.
num = int(input())
ary = []
b_sur = int(num/2)
for i in range(num):
ary.append(int(input()))
ary.sort()
# 연산 시작
avg = round(sum(ary)/num)
mid_value = ary[b_sur]
ranges = ary[-1] - ary[0]
# 최빈값 구하기
# 딕셔너리 사용?
dic = {}
ary_cp = ary[:]
ary_cp = list(set(ary_cp))
for i in range(len(ary_cp)):
dic[ary_cp[i]] = 0
# 이미 등장했다면 값만 올려주자
for j in range(num):
dic[ary[j]] += 1
most_value = sorted(dic, reverse=True, key=lambda x:dic[x])
print(avg,mid_value, most_value,ranges)🟧 시도 2 (정답)
이런 저런 방법들을 시도하고 시간을 많이 소요하다가 아이디어가 도저히 떠오르지 않아 서칭을 했다. 찾아보니 뭔가 라이브러리를 사용하는 것은 마음에 들지 않아 라이브러리 사용이 없는 아이디어를 찾다보니 딕셔너리는 똑같이 사용하면서 최빈값 배열을 따로 만들어 해결하는 아이디어를 본 후 만들어보았다. 예제도 다 맞게 입력되고 분명 정답인 것 같았는데, 제출해보니 계속 틀렸습니다가 나와 혹시나 하고 pypy3로 제출하니 정답이 맞았다. 뭔가 찜찜한 기분이 들었지만 다른 예제를 확인할 수도 없고 논리적으로 맞는 것 같아 이대로 이해하고 넘어갔다.
import sys
input=sys.stdin.readline
num = int(input())
ary = []
b_sur = int(num/2)
for i in range(num):
ary.append(int(input()))
ary.sort()
# 연산 시작
avg = round(sum(ary)/num)
mid_value = ary[b_sur]
ranges = ary[-1] - ary[0]
##########################################
# 최빈값 구하기
dic = {}
ary_cp = ary[:]
ary_cp = list(set(ary_cp))
for i in range(len(ary_cp)):
dic[ary_cp[i]] = 0
for j in range(num):
dic[ary[j]] += 1
mx=max(dic.values())#빈도수 중 최대값 구하기
if(mx == 1 and len(ary) == 1):
most_v = ary[0]
elif(mx == 1 and len(ary) > 1):
most_v = ary[1]
else:
mx_dic=[]
for i in dic:
if mx==dic[i]:
mx_dic.append(i)
if len(mx_dic)>1:
most_v = mx_dic[1]
else:
most_v = mx_dic[0]
print('---')
print(avg)
print(mid_value)
print(most_v)
print(ranges)[G2]13415] 정렬 게임
[G5]11000] 강의실 배정
🟧 시도 1
배열에 시간들을 모두 넣어두고, 시작 시간을 기준으로 정렬하였다. 이 후 하나씩 pop을 해서 만약 겹쳐지는 시간들이 있다면 해당 시간을 제외하는 형식으로 진행하였고 시간초과가 발생했다.
이렇게 블로그에 정리하면서보니 애초에 논리가 틀렸다. 흐름을 타듯이 시작과 끝이 맞아 떨어지면 시작 시간을 다시 바꾸고 pop을 진행해야하는데 그렇게 하지 못했다.
n = int(input())
q = []
for i in range(n):
s, e = map(int, input().split())
q.append([s, e])
q.sort()
# 가장 빠른 시간부터 강의 시작
# 만약 겹치는 강의 시간이 있다면 그 강의 시간으로 연강
cnt = 0
while q:
start = q.pop(0)
cnt += 1
end = start[1]
find = 0
for i in range(len(q)):
if(q[i][0] == end):
find += 1
if(find >= 1):
q.pop(i)
print(cnt)🟧 시도 2 (정답)
시도 1의 논리부터 틀렸으나,N이 최대 20만이나 들어올 수 있는데 진행을 하면서 한 번씩 그 배열을 들여다봐서는 해결할 수 없을 것 같았다.
뭔가 지금 내가 선택한 강의의 끝 시간과 다른 강의들 중 시작 시간이 같은 게 있다면 묶어주는 논리가 필요한 것 같은데 어떻게 구현을 잘해야할지 감이 오지 않았다.
다른 방법으로는 예전 연결요소의 개수 문제랑 무언가 비슷한 점이 있다고 생각했다. 연결요소들이 있다는 것이 즉, 강의실의 시작과 끝이 연결된다는 의미이기도 하니까.
이런 저런 아이디어들을 고민하던 중에 문제의 알고리즘 분류에 우선순위 큐를 발견하고 우선순위 큐를 적용해보기로 했다. 사실 어떻게 우선순위 큐를 적용할지 감이 잘 오지 않았다. 우선 비교를 시작할 처음 집어야 할 건 가장 낮은 시간의 종료 시간이니까 그걸 우선순위 큐에 넣고 진행할 생각을 해보았다. 큐에 첫 번째에 있는 게 지금 가장 낮은 종료 시간이니까 그 내용을 가지고 다른 스케쥴들을 비교하며 맞아 떨어진다면 최소 힙을 팝시키고 현재 비교중인 것을 집어넣는 논리로 진행해보았다.
# 다른 방법
# 트리처럼 서로 연결되어 있으면 세는 연결요소?
import heapq
import sys
input=sys.stdin.readline
n = int(input())
schedule = []
P_q= []
for i in range(n):
s, e = map(int, input().split())
schedule.append([s, e])
# 시작 시간 기준으로 정렬
schedule.sort()
# 우선순위 큐에 시작 시간이 젤 빠른 거 삽입
heapq.heappush(P_q, schedule[0][1])
# 스케쥴 돌면서 종료시간, 최소 시작 시간 비교
for i in range(1, n):
if(schedule[i][0] < P_q[0]): # 최소 시작 시간이 현재 강의보다 늦게 끝나면?
heapq.heappush(P_q, schedule[i][1])
else:
heapq.heappop(P_q)
heapq.heappush(P_q,schedule[i][1])
print(len(P_q))[G5]2710] 선 긋기
🟧 시도 1
처음 문제 자체를 이해하는 것에 어려움을 겪었다.
선분을 그은 횟수 N이 주어지는데
1 3
2 5
3 5
6 7
두 점이 x,y라고 한다면 (1,3) (2,5) (3,5) (6,7)이 되서 선분이 3개가 나오는게 아닌가 하는 생각이 들었다. 이 부분은 솔직히 아직도 이해되지 않는다. 선택한 두 점의 위치가 x,y라고 주어졌으면 선분이 3개가 나올텐데..아무튼
회의실 배정과 결이 비슷하지만 좀 다른 문제 같았다. 종료되는 점을 가지고 다음에 오는 선분들의 시작점을 비교하면서 큐에 넣어오는 끝점이 더 크거나 같은 경우 큐를 팝시키고 해당 선분의 끝점으로 바꾸고 계속 진행해는 방식으로 하였다.
논리를 어느 정도 만들고 나니 선분 전체의 길이를 구하는 것이 조금 곤란했다. 선분이 그이다 끊기는 경우가 발생하는데 이때 선분의 길이를 어떻게 처리를 할 것인가에 대해서 많은 고민을 하였고, 간단하게 먼저 떠오른 방법이 하다 끊긴 것을 flag변수로 표현하여 계속 그이고 있다면 flag가 1이고 아니라면 시작점을 저장해주는 방식으로 진행하였다. 끝으로 마지막인데 선분이 남아있다면 그것을 처리해주는 방식으로 진행하였지만 정답이 아니었다.
import heapq
import sys
input=sys.stdin.readline
n = int(input())
xy= []
P_q = []
for i in range(n):
s,e = map(int, input().split())
xy.append([s,e])
xy.sort()
heapq.heappush(P_q, xy[0][1])
length = 0
end = 0
flag = 0
for i in range(0, n-1):
if(P_q[0] >= xy[i+1][0]): # 우선순위 큐에 값보다 다음 좌표가 작거나 같으면 합쳐서 긋자.
if(flag == 0):
start = xy[i][0]
heapq.heappop(P_q)
heapq.heappush(P_q, xy[i][1])
flag = 1
else:
heapq.heappush(P_q, xy[i][1])
length += (heapq.heappop(P_q) - start)
if(i+1 == n-1):
length += xy[i+1][1] - xy[i+1][0]
flag = 0
print(length)