[백준] 정렬 /파이썬 - 10814 10815 1026

📌 10814 나이순 정렬

10814번: 나이순 정렬

두번째 기준이 가입한 순서인데 원래 가입한 순서로 정렬되어 있기 때문에 한 개의 조건으로만 정렬했다.

 

내풀이

import sys
input = sys.stdin.readline

n  = int(input())
members = [list(map(str,input().split())) for _ in range(n)]
members.sort(key=lambda x: (int(x[0])))
for i in members:
    print(*i)

근데 생각해보니 map으로 받을 필요가 없었다.

members = [list(input().split()) for _ in range(n)]

그래서 이렇게 해당 부분의 map을 지웠다.  

 

다른 풀이

for i in range(n):
    a,b = input().split()
    lists.append([int(a),b])

다른 풀이를 보니 이렇게 변수로 받아서 정렬로 넣는데 더 빨랐다.

보니까 for문을 돌며 하는  행위

나: 넣어줄 때마다 list로 바꾸고,

다른 풀이: 단순 인자를 묶어서 append 하기 때문에

메모리 차지와 속도에서 차이가 나는것으로 판단했다.

 

💙 작은 연습문제에서는 상관 없겠지만, 큰 서비스, 데이터를 관리할 때에는 속도도 신경써야 할 것이기 때문에 미리미리 연습을 해보자

 

---

📌 1026 보물

www.acmicpc.net/problem/1026

1026번: 보물

최소값을 만들어야 함

가장 큰수는 가장 작은수와 곱해져야함 

B의 자리는 바꿀 수 없으니

B의 수가 큰 순서대로 그 자리에 A의 작은 순서의 수들을 위치시켜야함

 

A를 오름차순으로 배열한 후

A를 돌며 B의 최대값과 곱해서 더해준 후 바로 최대값을 빼준다(remove)

 

내풀이

import sys
input = sys.stdin.readline
sum=0

n = int(input())
aArr = list(map(int,input().split()))
bArr = list(map(int,input().split()))
aArr.sort()
for i in aArr:
    bMax = max(bArr)
    sum+=i*max(bArr)
    bArr.remove(bMax)

print(sum)

처음 생각은 A sort하고 B reverse sort 하고 곱해주는 거였는데 B의 정렬을 바꾸면 안된다고 해서 말았다.

근데 어차피 합을 구하는 거니 정렬을 바꿔도 되는걸까? 애매하다고 생각한다 ㅎ

 

다른풀이

for i in range(n):
    sum+=A[i]*B[n-i-1]

 

다른 풀이를 보니 B를 둘다 오름차순 정렬해두고 n을 이용해서만 곱하는 방법도 있었다.

 

---

📌 10815 숫자카드

www.acmicpc.net/problem/10815

10815번: 숫자 카드

 숫자카드만 오름차순으로 정렬한 후 

숫자카드 여부를 판단할 4째 줄을 돌며 숫자가 있는지 확인하다.

단점: 매 카드마다 돌아아햠

 

import sys
input = sys.stdin.readline

n=int(input())
cardNum = list(map(int,input().split()))
m=int(input())
checkNum = list(map(int,input().split()))
isCard=[0]*m

for i in range(m):
    if(checkNum[i] in cardNum):
        isCard[i]+=1
print(*isCard)

역시나 시간초과되었다.

이유를 찾아보니

n과 m이 1부터 10만 사이로 주어지기 때문에 for문을 일일히 도는것은 사실  불가능하다는 평이다.

 

그러다 이분탐색에 대해서 알게 되었는데

---

 

✏️이분탐색 = 이진탐색

데이터가 정렬된 배열에서 특정한 값을 찾아내는데

중간값을 기준으로 크기를 비교하며 그 범위를 줄여나가는 방식이다.

 

예시로

2를 찾기 위해 정렬의 중간값을 찾아서 크기를 비교하고

그 크기보다 작으면 중간값 이하로 범위를 좁혀서 

 

다시 그 중간값과 비교하는 방식

 

 

 

 

 

---

다른 풀이1

def bin_search (ele,sort_list,start=0,end=None):
    if end == None:
        end = len(sort_list) - 1
    if start > end:
        return 0
    mid=(start+end)//2

    if ele == sort_list[mid]:
        return 1
    elif ele < sort_list[mid]:
        end=mid-1
    elif ele > sort_list[mid]:
        start = mid+1
    return bin_search(ele,sort_list,start,end)

n=int(input())
card_list = list(map(int,input().split()))
m=int(input())
check_list = list(map(int,input().split()))

card_list.sort()
ans=[]
for i in check_list:
    ans.append(bin_search(i, card_list))

print(" ".join(map(str,ans)))

블로그의 후기를 보고 참고하여 bin_search 라는 오름차순 리스트를 탐색할 수 잇는 function을 만들어 탐색했다.

 

근데 후기를 좀더 보니 dictionary 를 이용해 푸는 방법이 있었다.

 

다른풀이2

n=int(input())
card_list = list(map(int,input().split()))
m=int(input())
check_list = list(map(int,input().split()))

check_dict = { i:0 for i in check_list}

for i in card_list:
    if(i in check_dict.keys()):
        check_dict[i]=1

print(" ".join(list(map(str,check_dict.values()))))

이렇게 check_list의 값이 key이고 0을value  로 가진 값으로 만들고

card list를 돌며 값이 key에 존재하면 value+1 하는 방식

 

 

 

 

 

💙 금방 난이도가 높아진걸 느꼈다. 단순한 문제였지만 찾아보니 다양한 풀이들이 있었고 그걸 정리하는데 한참 걸렸다. 이제 알고리즘 시작인가보다.