[백준] 정렬 /파이썬 2217 로프, 1764 듣보잡

📌 2217 로프

www.acmicpc.net/problem/2217

2217번: 로프

처음 생각

n 개수를 받은후 돌면서 최대 중량을 list로 받음

제일 작은 최대 중량 * n 개가  로프들의 최대중량이라고 생각

import sys
input= sys.stdin.readline

n=int(input())

weight = list(int(input()) for _ in range(n))
weight.sort();

print(weight[0]*n)

역시나 오답.

오류: 로프를 전부 쓴 경우 < 최적의 로프를 쓴 경우의 최대 중량이 클 수 있다는 점을 간과했다.

 

유심히 생각해보니,

각 로프들이 들 수 있는 최대중량을 내림차순으로 정렬한 후에

최대중량 * 로프 개수 (+1 씩 증가)  이 값이 가장 큰  경우가 최대 중량이라는 생각이 들었다.

 

 

나의 풀이

import sys
input= sys.stdin.readline

n=int(input())

weight = list(int(input()) for _ in range(n))
weight.sort(reverse=True)
max_weight=0
for i in range(len(weight)):
    if max_weight<weight[i]*(i+1):
        max_weight=weight[i]*(i+1)
print(max_weight)

weight라는 list에 최대중량을 받아

반대로 정렬한 후

최대중량 * 최대중량을 들 수 있는 로프의 개수 를 max_weight에 넣고 비교하여 

가장 큰 값을 얻어냈다.

 

다른풀이

import sys
input= sys.stdin.readline

n=int(input())

weight = list(int(input()) for _ in range(n))

weight.sort()
weight_max=0
for i in weight:
    weight_max=max(i*n,weight_max)
    n-=1
print(weight_max)

다른 풀이를 찾아내니 weight_max를 돌며 바로바로 max를 계산하는 방법도 있었다.

다만 나의 풀이보다 살짝 느렸다.

내풀이는 비교대상이 하나이고 단순 연산이지만 다른풀이에서는 매번 max를 해주기 때문인 것 같다.

 

💙  어떤게 더 빠른 방법인지 고민하는 습관을 기르자. max 보단 <  단순연산자!

 

 

---

📌 1764 듣보잡

www.acmicpc.net/problem/1764

1764번: 듣보잡

문제보고 좀 웃겼다. 그리고 풀었는데 뭔가 찜찜했다.

이 쯤 이런문제가 나온다구?

 

듣도못한 사람의 list를 받고 

나름 시간 줄인다고 보도못한 사람을 받으면서 듣도못한 사람의 list에있나 찾았지만 

list에서 in으로 찾는거는 역시나 시간초과이다  ㅠㅠ

 

 

내풀이1

import sys
input = sys.stdin.readline

h,s = map(int,input().split())

hList = [input() for _ in range(h)]

ans=[]
for i in range(s):
    never_seen = input()
    if never_seen in hList:
        ans.append(never_seen)
print(len(ans))
for i in ans:
    print(i.strip())

역시나~~

 

내풀이2

import sys
input = sys.stdin.readline

h,s = map(int,input().split())

hList = list(input() for _ in range(h))
sList = list(input() for _ in range(h))

hSet=set(hList)
sSet=set(sList)

ans=[]
ans = sorted(list(hSet & sSet))
print(len(ans))
for i in ans:
    print(i.strip())

 

그렇담 list 말고 set으로 처리하자! 해서 만든 문제

list로 받고 -> set으로 바꿔서 교집합하고  -> list로 바꿔 중복 제거 

정답은 나왔지만 좋은 코드라는 느낌은 없다 ..ㅠ

 

다른 풀이

import sys
input = sys.stdin.readline

def binarySearch(list,ele,low,high):
    while low<=high:
        mid = (low+high)//2
        if list[mid] == ele:
            return True
        if ele > list[mid]:
            low = mid+1
        else:
            high = mid-1

    return False



h,s = map(int,input().split())

hList = [input().strip() for _ in range(h)]
sList = [input().strip() for _ in range(s)]
hList.sort()

ans=[]
for i in sList:
    if binarySearch(hList, i, 0,h-1):
        ans.append(i)
print(len(ans))
for i in sorted(ans):
    print(i)

다른 풀이 방법을 찾았는데

이분탐색 함수를 이용해서  SList를 돌며 이분탐색 함수를 통해 hList에 있는지 확인하는 방법이다.

이 역시 정답으로 나왔지만 시간이 set을 이용한것보다 2배가 나왔다.

 

아무래도  이분탐색은 데이터를 정렬하는 과정에서 시간이 소요 되는데

set은 집합이기 때문에 교집합연산으로 한번에 해결하기 때문에 더 빨랐던 것같다.

 

 

 

💙 오늘은 모든 풀이에 시간초과가 나와서 당황했지만 시간초과가 나오는 유형들을 알게되고 피하는 스킬을 알아냈다.

배열의 존재여부는 in이 아닌 set  교집합 혹은 이분탐색으로!

max 보다는 단순 연산자로!