Sguri
2024.04-3
4월 3주차 기록
2024년 4월 15일
1. 10773번 제로
단순하게 0일때 리스트에 있는 마지막을 제거하면 될 것 같아 바로 구현했다. 근데 int(input())으로 입력을 받으니 너무 느렸다. input=sys.stdin.readline()으로 받으니 시간이 600배 빨라졌다..!
알게 된 점
- sys.stdin.readline() 이 input()보다 빠르다.
코드 비교
input=sys.stdin.readline()으로 대체
구현 코드
import sys
k = int(input())
answer = []
for i in range(k):
number = int(input())
if number ==0:
answer.pop()
else:
answer.append(number)
print(sum(answer))
-- 변경 후 코드 --
import sys
input= sys.stdin.readline
k = int(input())
answer = []
for i in range(k):
number = int(input())
if number ==0:
answer.pop()
else:
answer.append(number)
print(sum(answer))
1. 18110번 solved.ac
그냥 단순하게 리스트에 넣고 반올림 하면 되겠구나 했다. round()함수를 썼더니 잘 안돼서 질문게시판을 보았는데 몰랐던 round함수의 규칙이 있었다! 또한, 시간초과가 돼서 for문으로 기존에 하나하나 지우던걸 slicing으로 해결했다. 그리고 문제를 찬찬히 보자! 0일때도 미리미리 예외처리 하기!
알게 된 점
- 반올림은 5이상에서 5미만 (1,2,3,4)에서 버린다. 이걸 사사오입이라고 하는데 round는 오사오입이다. 5초과에서 올올리며, 5인경우 앞자리가 짝수인 경우 버리고 홀수인 경우 올린다!!
- ex) round(2.5)=2, round(3.5)=
코드 비교
생각해보면 차례로 빼기 때문에 굳이 2차원 리스트로 만들 필요가 없다. 또한 index=0에 있는 것이 최댓값이면 빼면 된다. 이때 순서를 알기를 원하는 m이 0이면 멈춘다. 하나를 뺏기 때문에 index값을 하나를 줄인다. 만약 순서를 옮겨야 하는 상황이고 index가 0이면 index를 맨 끝값으로 옮긴다.(0에서 -1해서 앞으로 갈 수 없기 때문에) 그게 아니면 list에서 1를 빼주며 앞으로 옮기는 느낌을 준다.
즉 실제로 옮기는게 아니라 우리가 알고 싶은 값만 옮기면 되기에 그 수만 조작해준다.
while True:
if files[0] == max(files):
count += 1
if index == 0:
break
index -= 1
files.pop(0)
else:
if index == 0:
index = len(files)-1
else:
index -= 1
a = files.pop(0)
files.append(a)
구현 코드
import sys
input= sys.stdin.readline
n = int(input())
answer =[]
def rounds(n):
if n-int(n)>= 0.5:
return int(n)+1
else:
return int(n)
if n ==0:
print(0)
else:
for i in range(n):
number = int(input())
answer.append(number)
count = rounds(n*0.15)
answer.sort()
answer = answer[count:n-count]
print((rounds(sum(answer)/len(answer))))
2024년 4월 17일
목표
- 4문제 풀기
1. 1966번 프린터 큐
구현에서 계속 오류 나서 고치느라 힘들었다. 체계적인 구조부터 생각하고 구현하는 게 시간을 단축하지 않을까?
알게 된 점
- 반올림은 5이상에서 5미만 (1,2,3,4)에서 버린다. 이걸 사사오입이라고 하는데 round는 오사오입이다. 5초과에서 올올리며, 5인경우 앞자리가 짝수인 경우 버리고 홀수인 경우 올린다!!
- ex) round(2.5)=2, round(3.5)=3
구현 코드
import sys
input= sys.stdin.readline
a= int(input())
answer = []
files = []
for _ in range(a):
idx = 0
n,m= map(int,input().split())
for i in map(int,input().strip().split()):
files.append([i,idx])
idx+=1
count = 0
while files:
priority,idx = files.pop(0)
if files:
if priority<max(files,key = lambda x:x[0])[0]:
#인쇄하지 않고 뒤에 재배치
files.append([priority,idx])
else:
#인쇄
count +=1
if idx ==m:
answer.append(count)
else:
if idx == m:
#인쇄하고 출력
count +=1
answer.append(count)
break
else:
#인쇄만 하는 경우
count +=1
break
for i in answer:
print(i)
2. 2108번 통계학
그냥 통계를 출력하는 것. 여기에서 Counter로 빈도를 판별했다. 만약 빈도가 같으면 두번 째로 작은 값을 출력하는게 어려웠었는데, 가장 큰 값을 아니까, 그 빈도를 가진 숫자들은 전부 list에 넣고, sort()해서 맨 앞 값을 제거해줘서 해결했다.
코드 비교
절댓값이 4000이 넘지 않으므로 정수 전체는 8001개이기에 이 값을 지닌 list를 선언한다. 이후, 그 값이 있으면 그자리에 1을 더해준다. (이전에도 봤던 구현이다!) -1인경우 -1인 index는 없기에, 4000을 기준으로 앞뒤 배치를 해준다. 그리고 그렇게 완성된 코드를 전부 돌면서 max count값으로 비교하거나(이건 만든 리스트의 max, 갯수로 +=1을 해줬기에), 값이 있는 경우 더하거나 max값이나 min값을 찾는다.
numbers= [0]*8001
#리스트 만들기
for i in stdin:
num = int(i)
counts[num+4000] += 1 #있으면 추가 1
for i in range(8001):
num = i-4000 #처음에 4000에서 더해줬으니
s += num*counts[i] #총 합은 갯수*number
if cnt == maxc and mcnt < 2: 최대빈도수, 최초거나
#그 다음작은값, 왜냐 작은것부터 보기 때문에 가능
mode = num
mcnt += 1 #최대 빈도 값 세기
구현 코드
import sys
from collections import Counter
input= sys.stdin.readline
n = int(input()) #수의 개수
numbers= []
for i in range(n):
numbers.append(int(input()))
print(round(sum(numbers)/n)) #산술평균
numbers.sort()
print(numbers[n//2])
commons = Counter(numbers).most_common()
max_count = commons[0][1]
mins = []
count = 0
for i in commons:
if i[1] == max_count:ㅇㄷ
mins.append(i[0])
else:
break
if len(mins)>1:
mins.sort()
del mins[0]
print(mins[0])
print(max(numbers)-min(numbers))
2024년 4월 18일
1. 1929번 소수 구하기
에라토스테네스의 체를 떠올렸다! 문제는 어떻게 구현했는지 매번 까먹는다. 이번엔 잘 기억해보자.
코드 비교
- m~n사이에 있는 소수만 알면 된다. 따라서 range를 (m,n+1)로 설정하자
- 2부터 알아야 할 숫자 제곱근까지, 나눠지면 멈춤. (약수 존재므로 소수가 아님_)
구현 코드
import sys
input= sys.stdin.readline().strip
start,end = map(int,input().split())
primes = []
a = [False,False] + [True]*(end-1)
for i in range(2,end+1):
if a[i]:#왜 a[i]냐하면, a에서 2부터 True가 뜨기 때문에 이 배수를 다 제거!
primes.append(i)
for j in range(2*i, end+1, i):#소수의 배수를 다 제거
a[j] = False
for i in primes:
if i>=start:
print(i)
2. 1654번 랜선 자르기
일단 혹시 해서 이진 탐색으로 하지 않고 떠오르는 걸 했는데 역시나.. 시간초과 뜨고 바로 코드를 수정했다. 아직 이진 탐색 중 최댓값을 찾는 게 미숙해서 좀 오래 걸렸다.
알게 된 점
- arr = [int(input()) for i in range(k)] ← k번 동안 input 받아서 넣는 코드.
- 이 코드에서 처음 설정할 r값을 cables의 평균으로 놓는 것이 빠르다.
구현 코드
import sys
cables = []
k,n = map(int,sys.stdin.readline().strip().split())
for _ in range(k):
cable = int(sys.stdin.readline())
cables.append(cable)
allCable = 0
r = max(cables)
l = 1
while l<=r:
cut = (l+r)//2
allCable = sum([x//cut for x in cables])
if allCable>=n: #최댓값을 구해야 하기에 같아도 start를 올려 범위를 압축.
l = cut+1
else:
r = cut -1 #cut의 범위를 낮춰야 함.
print(r)
2024년 4월 19일
1. 1874번 스택 수열
!https://d2gd6pc034wcta.cloudfront.net/tier/9.svg
💡문제 분석 요약
| 2 초 | 128 MB | | — | — |
입력 값을 보면서 숫자 순서대로 보면서 +와 -를 출력하는 문제
현재 위치부터 숫자 순서대로 +(push)를 출력하고, pop을 할 때는 list로 pop여부를 파악하여 뺀다.
💡알고리즘 설계
실제로 pop과 push로 list의 값을 변경하면 시간이 오래 걸릴 것 같아, list[number]=bool 로 pop여부를 확인한다. → 그러나 그렇게 오래걸리진 않는 듯 하다.
입력 값을 받은 list를 돌면서, 얼마나 push해야하고 pop해야하는 지 알고 그만큼 answer에 추가한다.
이때, push를 해야하는 상황이면, 현재까지 push한 숫자~넣어야 하는 숫자 범위만큼 돈다. 현재 위치도 저장해 놓는다. (pop때 사용)
pop을 해야하는 상황이면, 뺏는지 확인하고 현재 위치~ 넣어야 하는 숫자 만큼 돌면서 빼준다. 현재 위치도 저장 한다.
만약, 이미 뺀 숫자를 요구해오면 No를 출력하라는 bool을 킨다!
💡코드
import sys
input= sys.stdin.readline
n = int(input())
numbers = [int(input()) for _ in range(n)]
stack = [True]*(n+1)
answer = []
now =0
countPush = 0
No = False
for i in numbers:
if stack[i]:
if now<=i:
for j in range(countPush,i):
answer.append('+')
countPush +=1
now = i
answer.append('-')
stack[i] = False
else:
for z in range(i,now):
if stack[z]:
answer.append('-')
stack[z]=False
now = i
else:
No =True
if No:
print('NO')
else:
for i in answer:
print(i)
💡시간복잡도
for문 1개→ N
2중 for문에서 append는 N
print할때 N
총 3N
💡 틀린 이유
처음 코드도 비슷하게 구현했으나, pop을 했는지 안했는지를 체크할 방법이 없어서 이상한 값을 쓰다가 틀렸다.
💡 틀린 부분 수정 or 다른 풀이
현재 값과 찾아야할 숫자를 비교하면서 그 숫자에 다다를때까지 push 해준다. 만약 맨 끝값을 빼봤는데(실제로 pop() 실행 )찾는 숫자가 아니면 NO를 뱉는다.
위 구문에서 뺏으므로 append(’-’)를 해준다.
위 코드는 list를 하나 적게 사용했다. pop()을 사용해 O(1)로 실제 리스트를 지워 추가 list구현을 하지 않았다. 또한 append 와 pop자체는 그리 오래걸리지 않으므로 구현 가능하다.
312인경우, 123을 넣고, 3을 뺀다. 이후 1이 들어오면 pop을 할때 2부터 나오므로 NO!
1432인 경우, 1넣고 제거, 234넣고 4제거, 이후 3, 2가 자연스럽게 빠지므로 통과!
💡 느낀점 or 기억할정보
No의 조건을 이해하지 못해서 틀렸다. 처음에 ‘-’값이 그냥 단순히 길이보다 큰가? 하였는데 그게 아니었다! → 제대로 문제를 이해하고 풀자
2. 1811번 마인크래프트
!https://d2gd6pc034wcta.cloudfront.net/tier/9.svg
💡문제 분석 요약
| 2 초 | 128 MB | | — | — |
입력 값을 보면서 숫자 순서대로 보면서 +와 -를 출력하는 문제
현재 위치부터 숫자 순서대로 +(push)를 출력하고, pop을 할 때는 list로 pop여부를 파악하여 뺀다.
💡알고리즘 설계
초안:
00 01 02
10 11 12
20 21 22
ㅂ. 위 블록 제거 후 인벤 2
- 이벤 꺼내서 놓기 1
최소 시간.
즉 비교해야한다.
2초 걸리는 제거 vs 2 1초 걸리는 쌓기 ( 그러나 인벤이 차있어야 함)
2차원 배열 돌면서
평균값을 출력하고 그만큼 채우거나 버려야 함.
이때 채우려면 인벤을 보고, 인벤이 없으면 무조건 2초로 카운트.
💡코드
import sys
input= sys.stdin.readline
n, m ,stock= map(int,input().split())
block =dict()
for _ in range(n):
for a in list(map(int,input().split())):
block[a] = block.get(a,0)+1 #값이 없으면 0, 값이 있으면 +=1
ans = [float('inf'), 0]
for h in range(min(block.keys()), max(block.keys())+1):
count = 0
inven =0
for b in block.keys():
if h < b:
count += (b-h)*block[b]*2
if h > b:
count += (h-b)*block[b]*1
inven += (h-b)*block[b]
if inven<=stock and count<=ans[0]:
ans = [count, h]
print(*ans)
💡시간복잡도
💡 틀린 이유
이분 탐색으로 풀려다가 안돼서 답을 보게 되었다. 찾다가 이분 탐색으로 풀지 못하는 이유를 알았다. 프로그래머스의 입국심사 문제와 비슷하다고 생각해서 풀려고 했는데 아니었다.
이분 탐색 문제: 비교할 기준값, 탐색할 값, 구하고자 하는 값이 존재한다.
탐색할 값과 구하고자 하는 값은 같은 domain을 가진다. 입국 심사 문제의 경우 탐색할 값과 구하고자 하는 값이 time domain으로 같았지만,
이 문제의 경우 탐색할 값(돌아서 볼 값)은 height, 구하고자 하는 값은 time이기에 이분 탐색이 불가하다.
💡 틀린 부분 수정 or 다른 풀이
최대 높이가 267이므로 257칸의 리스트를 미리 선언한다.그리고 각 index=블록의 높이가 되며, 그 블록의 갯수를 value 값에 담는다. 즉 list[높이]=높이에 따른 블록 갯수 .
모든 블록의 높이를 다 더하고, 인벤토리에 있는 값에 그 값을 더한다.
그 값을 2배 한것(왜냐하면 모든것을 뺄 때 최대 2초가 걸리며, 그때 인벤토리에는 모든 1크기의 블럭이 죄다 담기기 때문이다.)
답은 (최소 시간, 최대 높이) 높이 최댓값을 2배*모든 블럭 설정하고, time의 최소값은 0으로 설정한다.
list를 돌때마다 b가 0보다 작아지면 멈추고 min함수를 활용하여 answer가 최대인지 본다. 이때 높이는 최댓값이어야 하므로 index값은 -index로 비교해줘야 한다. 그리고 값을 재 설정해준다.
돌아보는 높이에 있는 블록을 i라하면, 이 갯수를 need에 넣는다.
모든 블럭 갯수를 have에 넣으면, 각 range를 돌때마다 0층 최대 갯수- 이미 존재하는 블럭을 뺀다. (즉, 그 층에서 마지막으로 끝나는 블럭만 뺀다. ) t에는 현재까지 센 블럭의 갯수를 넣는다.
import sys
input=sys.stdin.readline
def sol():
n,m,b=map(int,input().split())
data=[0]*257
for _ in range(n):
for i in map(int,input().split()):
data[i]+=1
have=sum(i*data[i] for i in range(257))
ans=(have*2,0)
need=0
t=data[0]
nm=n*m
for i in range(1,257):
need+=t
have-=nm-t
t+=data[i]
if have+b-need<0:
break
else:
ans=min((have*2+need,-i),ans)
print(ans[0],-ans[1])
sol()
💡 느낀점 or 기억할정보
이분 탐색을 쓸 수 있는 지 파악하고 쓰자.
비교할 기준값, 탐색할 값,=(같은 영역 값)=구하고자 하는 값
2024년 4월 21일
1. 11723번 집합
연산 수행 프로그램.
💡문제 분석 요약
string과 number를 받고, 각 조건처럼 연산을 수행하여 출력하는 문제.
💡알고리즘 설계
input을 받고, split으로 나눈 것을 각각 대입하면서 연산을 수행한다.
💡코드
import sys
input= sys.stdin.readline
n = int(input())
number = set()
for i in range(n):
sentence =list(input().split())
if len(sentence)>1:
do,n = sentence
n = int(n)
else:
do = sentence[0]
if do=='add':
if n not in number:
number.add(n)
elif do=='remove': number.discard(n)
elif do=='check':
if n in number: print(1)
else:
print(0)
elif do=='toggle':
if n in number:
number.discard(n)
else:
number.add(n)
elif do=='all':
number = {x for x in range(1,21)}#시간 복잡도를 위해선 [1,2,3..20]을 직접 대입하기
elif do=='empty':
number=set()
💡시간 복잡도
💡 틀린 이유
중간중간 코드를 잘못 짰다. 없으면 출력하는 것을 제대로 체크하지 못했다.
또한 값을 받을 때 list형태로 받았으면서 all과 같이 len이 1일때 do=sentence[0]를 빼먹었다.
💡 틀린 부분 수정 or 다른 풀이
range를 쓰지 않고 {1,2,3,4,…20}으로 된 리스트를 바로 넣는 것이 시간 입장에선 빠르다.
또한 굳이 set으로 풀 필요가 없다. list로 풀어도 좋다. 어차피 set형식으로 풀라하지도 않았으니!
💡 느낀점 or 기억할정보
set이라고 해서 곧이곧대로 set이라고 풀지 않아도 된다!
set에서 지울때, remove와 discard 두 개가 있는데, discard의 경우 없는 값을 지우라고 해도 에러가 나지 않는다. 이는 string의 find()와 index()도 비슷하다. find에서 없으면 -1을 return하지만 index는 Error. list에서도 index()도 없으면 Error
list에서 pop, remove, del 같이 지우는 기능에 없는 값을 지우면 전부 Error.
1. 1620번 나는야 포켓몬 마스터 이다솜
💡문제 분석 요약
키와 값으로 연결된 값을 출력한다. list보다 dict가 빠르므로 dictionary를 활용한다.
💡알고리즘 설계
알파벳을 key로 가지는 dictionary와 번호를 key로 가지는 dictionary로 입력값을 출력한다.
💡코드
#83440KB 288ms
import sys
from collections import defaultdict
input= sys.stdin.readline
n,m= map(int,input().strip().split())
name= defaultdict()
number=defaultdict()
a= sys.stdin.readlines()
lines = list(map(lambda s:s.strip(), a))
book = lines[:n]
question = lines[n:]
for i in range(n):
name[book[i]]=i+1
number[i+1] = book[i]
for q in question:
if q.isalpha():
print(name[q])
else:
print(number[int(q)])
#메모리와 시간 줄인 버전
#74264KB 228ms
import sys
input= sys.stdin.readline
n,m= map(int,input().strip().split())
a= sys.stdin.readlines()
lines = list(map(lambda s:s.strip(), a))
book = lines[:n]
question = lines[n:]
name_dict = {name:idx+1 for idx,name in enumerate(book)}
for q in question:
if q.isalpha():
print(name_dict[q])
else:
print(book[int(q)-1])
💡시간복잡도
💡 틀린 이유
좀 더 오래걸린 이유! dict를 하나 더 만들어서
💡 틀린 부분 수정 or 다른 풀이
굳이 dict를 두 개 만들어서 할 필요 없이, input이 애초부터 순서에 맞게 들어오므로 그것을 그대로 쓰면 된다!
또한, 읽을때 readlines()에 개행문자까지 전부 다 읽혀서 애매하다면, sys.stdin.read().splitlines()로 각 데이터를 읽어오면 된다. 이러면 한줄씩 문자열을 전부 읽을 수 있다. (대신 입력이 다 들어오므로, n과m값은 lins[0]으로 따로 처리해주고 나머지 값들도 lines[1,n+1]로 처리해야한다. . )
💡 느낀점 or 기억할정보
- sys.stdin.read().splitlines()로 각 데이터를 읽어오면 된다.
- 순서대로 값이 들어올 때, 아예 값을 읽어서 생성되는 list를 활용하자!
- name_dict = {name:idx+1 for idx,name in enumerate(book)} 형식처럼 dict값을 설정하는 게 가능하다.
3. 1764번 듣보잡
💡문제 분석 요약
2초 256MB
💡알고리즘 설계
set으로 설정하고 교집합을 구한다.
💡코드
import sys
lines= sys.stdin.read().splitlines()
n,m = map(int,lines[0].split())
nListen = set(lines[1:n+1])
nSee = set(lines[n+1:])
answer = nListen.intersection(nSee)
print(len(answer))
for i in sorted(list(answer)):
print(i)
💡시간복잡도
2N정도
💡 느낀점 or 기억할정보
교집합은 intersection으로 구하면 된다.