2023/7/14

2217번: 로프

import sys

input = sys.stdin.readline
lopes = []

N = int(input())

for _ in range(N):
  lopes.append(int(input()))

lopes.sort()
max = lopes[0] * N

for i in range(N):
  if max < lopes[i] * (N-i):
    max = lopes[i] * (N-i)

print(max)

저번 시간에 sys.stdin.readline을 input에 넣어서 활용하는 방법을 적용해보았다.

++ 정렬을 수행하고 작은 수 * 남은 로프 개수를 for 문으로 돌아가면서 max값을 찾아내어 문제를 해결하였다.

18870번: 좌표 압축

어허.. 이것을 어떻게 NlogN으로 짤 수 있지?

계수정렬을 쓸까했는데 데이터의 범위가 10^9라서 안되고… 고민하다 실패

다름사람 풀이를 보니 딕셔너리를 활용해 풀어내었다.

import sys
N = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
arr2 = []

arr2 = list(set(arr))
arr2.sort()

for i in range(len(arr)):
  arr[i]=arr2.index(arr[i])

print(*arr,sep=" ")

보통의 시간초과가 나는 코드이다.

for i in range를 돌면서

index를 활용해 들어가는데 index메소드가 시간복잡도 N이다 따라서 O(N^2) 이기떄문에 시간초과가 나는 것이다.

import sys
N = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
arr2 = []

arr2 = list(sorted(set(arr)))

dic = {arr2[i]:i for i in range (len(arr2))}

for i in arr:
  print(dic[i],end=' ')