#5052 전화번호 목록

🔗https://www.acmicpc.net/problem/5052

생각

제한 시간 : 1초
전화번호의 수 × 테스트 케이스 : 10,000 × 50 = 500,000
O(NlogN)보다 작거나 같은 구조를 설계해야 가능할 듯 싶다!

구현

직관적으로 생각하면 그냥 한 번호마다 모든 리스트를 돌며 그 번호와 일치하는 접두어를 가진 번호가 없는지 확인하면 된다.
하지만 그렇게 구현하면 O(N²) 이 나오므로 쓰면 안됨
비슷한 접두어를 가지고 있는 번호끼리 모여있도록 해서 번호 리스트를 한번만 훑게 만들어 접두어 유무를 검사하는게 가장 좋고 그렇기 때문에 sort로 번호 리스트를 정렬해야 한다.

여기서 중요한 점은, 여느 때와 다름없이 int로 입력을 받아 정렬을 하게 된다면
911, 9112400, 3872400 을 정렬할 때, 자릿수 때문에 911, 3872400, 9112400 으로 정렬을 하게 된다. 이를 막기 위해 문자열로 입력을 받고 정렬 시켜서 3872400, 911, 9112400 과 같이 사전순으로 정렬을 하게 해야 한다.
→ 여기까지 O(NlogN)
이 이후에는 리스트를 한 번 돌면서, i+1번째 번호가 i번째 번호를 접두어로 가지고 있는지 검사함으로써 일관성을 검사할 수 있다.
→ 여기까지 O(NlogN+N)=O(NlogN)

코드

import sys
T=int(sys.stdin.readline().rstrip())
phonenum=[]

for _ in range(T):
    phonenum.clear()
    n=int(sys.stdin.readline().rstrip())
    phonenum=[sys.stdin.readline().rstrip() for _ in range(n)]
    phonenum=sorted(phonenum)
    
    for i in range(n-1):
        length=len(phonenum[i])
        if phonenum[i]==phonenum[i+1][:length]:
            print("NO")
            break
        if i==n-2:
            print("YES")

#2470 두 용액

🔗https://www.acmicpc.net/problem/2470

생각

제한 시간 : 1초
수 : 100,000
O(NlogN)으로 만들면 되겠다!

구현

처음 생각

용액의 특성 값의 합이 제일 작게 나오는 경우는 무조건 세 가지 중에서 나오겠지 생각 했다.
제일 큰 양수 + 제일 작은 음수
제일 큰 음수 + 그 다음으로 작은 음수
제일 작은 양수 + 그 다음으로 작은 양수
무조건 이 세가지 경우에서 0과 제일 가까운 게 나올거라 생각해서 positive와 negative로 양수 음수 배열을 나누어 정렬한 다음, 세가지의 합을 비교하면 될거라 생각했는데 오답!
당연함... 이 외에도 많은 경우가 있음...

이후 생각

이렇게 경우를 나누기에는 너무 수많은 경우가 있다고 생각 돼서 도대체 어케 풀어야 하나 찾아보니 많은 사람들이 이진탐색을 이용해 풀고 있었다. 분명 이진탐색 문제도 많이 풀어봤는데... 왜 몰랐지?
얼마나 문제를 풀어야 문제를 보고 바로 아, 이진탐색으로 풀어야 하겠구나! 라고 생각 할 수 있을까 ㄱ-

코드

import sys

n=int(sys.stdin.readline().rstrip())
value=list(map(int,sys.stdin.readline().split()))


def binary_search(start,end,target): #이진탐색
    global answer1
    global answer2
    
    while(start<end):
        result=value[start]+value[end]
        if abs(result)<abs(target):
            target=result
            answer1=value[start]
            answer2=value[end]
            if result==0:
                break
        #0과 가장 가까운 합을 찾기 위해 범위를 계속 줄여준다. 근데 이렇게 찔끔 줄이는게 이진 탐색이 맞는건가??
        if result<0:
            start+=1
        else:
            end-=1

value=sorted(value)#정렬
answer1=value[0]
answer2=value[-1]
#target은 처음 특성값의 합을 설정해 놓는다.
#start와 end는 용액의 특성값 중 최소, 최대로 설정한다. (value[0], value[-1]) 그치만 인덱스를 이용해 탐색하기 위해 특성값의 인덱스를 넣어 주었다.
binary_search(0,len(value)-1,value[0]+value[-1])
print(answer1,answer2)

#1202 보석 도둑

🔗https://www.acmicpc.net/problem/1202

생각

제한 시간 : 1초
수 : 600,000

구현

처음 생각

가방 -> 오름차순 정렬
보석 -> 내림차순 정렬 후
가방 리스트 × 보석 리스트를 돌며, 보석이 해당 가방에 넣을 수 있는 무게용량보다 작은지 확인 후 넣는 방법으로 생각했는데 이렇게 풀이한다면
N × K = 300,000 × 300,000 이 되어 O(N²)이 되어버려 안된다.

이후 생각

아무리 생각해도 감이 잘 안와서 다른사람들의 풀이 코드를 참고했는데, 모든 사람들이 heapq를 이용해 풀고 있었다.
특히 그때그때 해당 가방의 용량(capacity)을 heappop을 통해 정하고, jewel을 한바퀴 돌면서 capacity보다 작은 무게를 갖고 있는 것을 따로 다른 heapq에 저장하는 방식이 다 똑같았다.
굳이 또 다른 heapq를 선언하지 않고 애초의 jewel을 내림차순 정렬하면 되는거 아닌가?? ㄱ- 생각 하면서 다른 방식으로 풀어보고자 했는데 계속 틀렸다고 나와서... 결국 기존의 정답 방식을 사용했다.

코드

import sys
import heapq

n, k = map(int, sys.stdin.readline().split())
jewel = []
bag = []
answer=0

for _ in range(n):
  m,v = map(int, sys.stdin.readline().split())
  heapq.heappush(jewel, [m,v])

for _ in range(k):
  heapq.heappush(bag, int(sys.stdin.readline().rstrip() ))

tmp = []

for _ in range(k):
  capacity = heapq.heappop(bag)
  
  while jewel and capacity >= jewel[0][0]:
    [weight, price] = heapq.heappop(jewel)
    heapq.heappush(tmp, -price)
  
  if tmp:
    answer -= heapq.heappop(tmp)
  elif not jewel:
    break

print(answer)