⭕️ 맞힌 문제
🔥 수학
피로도 / 22864 / 브론즈 3
코드
A, B, C, M = map(int, input().split())
cnt = 0 # 시간
hp = 0 # 누적 피로도
wrk = 0 # 누적 일
# 24시간이 될 때까지 반복
while cnt < 24:
cnt += 1
# 피로도가 음수로 내려가면 0으로 바뀜
if hp < 0:
hp = 0
# (누적 피로도 + 다음에 일했을 때의 피로도) > M일 경우 휴식
if hp + A > M:
hp -= C
# (누적 피로도 + 다음에 일했을 때의 피로도) <= M일 경우 일
else:
hp += A
wrk += B
print(wrk)진법 변환 / 2745 / 브론즈 2
코드
res = 0
arr, x = input().split()
arr = list(arr)
x = int(x)
# 입력받은 문자를 숫자로 변환
def input2int(a):
if a == '0' or a == '1' or a == '2' or a == '3' or a == '4' or a == '5' or a == '6' or a == '7' or a == '8' or a == '9':
return int(a)
else:
return ord(a) - 55
# 앞자리 부터 계산 실행
for i in range(len(arr)):
# res += 해당 자리의 값 * (... 진법에 의한 계산 ...)
res += input2int(arr[i]) * (x ** (len(arr) - i - 1))
print(res)정리
변환하는 함수가 아닌 0~35까지의 문자열을 만든 후 index를 이용하는 것도 괜찮은 풀이!
🔥 자료구조
괄호 / 9012 / 실버 4
코드
# 9012
N = int(input())
for i in range(N):
a = input()
b = []
for i in a:
if i == '(':
b.append(i)
elif i == ')':
if len(b) == 0:
print("NO")
break
else:
x = b.pop()
if x == ')':
print("NO")
break
# 여기!
else:
if len(b) != 0:
print("NO")
else:
print("YES")정리
for문에서 중간에 break가 나지 않았다면 else문을 실행한다.
아래 코드 내 에서 중간에 break가 나지 않았다면 '여기!' 아래 코드를 실행
break가 나왔다면 '여기!' 코드를 실행하지 않음.
카드2 / 2164 / 실버 4
코드
from collections import deque
N = int(input())
a = deque([])
for i in range(1, N+1):
a.append(i)
while len(a) != 1:
a.popleft()
if len(a) == 1:
print(a[0])
exit()
else:
a.append(a[0])
a.popleft()
print(a[0])스택 / 10828 / 실버 4
코드
# 10828
import sys
N = int(input())
a = []
for i in range(N):
S = sys.stdin.readline().split()
if S[0] == "push":
a.append(int(S[1]))
elif S[0] == "pop":
if len(a) != 0:
print(a[len(a)-1])
a.pop(len(a)-1)
else:
print(-1)
elif S[0] == "size":
print(len(a))
elif S[0] == "empty":
if len(a) == 0:
print(1)
else:
print(0)
elif S[0] == "top":
if len(a) != 0:
print(a[len(a)-1])
else:
print(-1)큐2 / 18258 / 실버 4
코드
import sys
from collections import deque
N = int(input())
a = deque([])
for i in range(N):
S = sys.stdin.readline().split()
if S[0] == "push":
a.append(int(S[1]))
elif S[0] == "pop":
if len(a) != 0:
print(a[0])
a.popleft()
else:
print(-1)
elif S[0] == "size":
print(len(a))
elif S[0] == "empty":
if len(a) == 0:
print(1)
else:
print(0)
elif S[0] == "front":
if len(a) != 0:
print(a[0])
else:
print(-1)
elif S[0] == "back":
if len(a) != 0:
print(a[len(a)-1])
else:
print(-1)🔥 자료구조 2
절댓값 힙 / 11286 / 실버 1
코드
import heapq
import sys
maxHeap = []
N = int(sys.stdin.readline())
for _ in range(N):
x = int(sys.stdin.readline())
if x == 0:
if len(maxHeap) == 0: # 만약 배열 길이가 0이라면 0 출력
print(0)
else: # 가장 큰 값 pop
print(heapq.heappop(maxHeap)[1])
else: # 배열에 추가
heapq.heappush(maxHeap, (abs(x), x)) # heapq는 작은 순으로 정렬되기 때문에 abs로 정렬시킴정리
직접 프린트해가면서 확인해보니
python의 heapq 모듈에서는, tuple을 heap으로 정렬할 때
첫번째 아이템의 크기 순으로 정렬한 뒤
같으면 두번째 아이템의 크기 순으로 정렬한다.
❌ 다시 풀어볼 문제
🔥 수학
공약수 / 5618 / 브론즈 3
코드
import sys
def gcd(a, b):
if a == 0:
return b
return gcd(b % a, a)
n = int(input())
S = sys.stdin.readline().split()
x = gcd(int(S[0]), int(S[1]))
if n == 3:
x = gcd(x, int(S[2]))
for i in range(1, x+1):
if x % i == 0:
print(i)
정리
유클리드 호제법을 알아야만 시간 초과가 나지 않는 문제
또한 어째서인지 python3로는 시간 초과가 나고 pypy3로 해야 성공한다.
🔥 자료구조
덱 / 10866 / 실버 4
import sys
from collections import deque
N = int(input())
a = deque([])
for i in range(N):
S = sys.stdin.readline().split()
if S[0] == "push_front":
a.appendleft(int(S[1]))
elif S[0] == "push_back":
a.append(int(S[1]))
elif S[0] == "pop_front":
if len(a) != 0:
print(a[0])
a.popleft()
else:
print(-1)
elif S[0] == "pop_back":
if len(a) != 0:
print(a[len(a)-1])
a.pop()
else:
print(-1)
elif S[0] == "size":
print(len(a))
elif S[0] == "empty":
if len(a) == 0:
print(1)
else:
print(0)
elif S[0] == "front":
if len(a) != 0:
print(a[0])
else:
print(-1)
elif S[0] == "back":
if len(a) != 0:
print(a[len(a)-1])
else:
print(-1)
정리
sys.stdin.readline()
- 한 두 줄이 아닌 여러줄을 입력 받을때 input()으로 받으면 시간 초과가 나기 때문에 사용
- .split()을 사용한다면 배열 형식으로, 공백을 기준으로 나눠서 입력받음
ㅤ
List Onotation 이유 index 접근 O(1) ddd pop(0) O(N) 접근하는 건 O(1)이지만 삭제 후 나머지 원소들 복사해줘야 함 ㅤ
deque : double-ended queue
Deque Onotation 이유 index 접근 O(N) ?? pop(0) O(1) Double Linked List로 구현되었음
스택 수열 / 1874 / 실버 3
코드
n = int(input())
ans = []
S = []
num = 0
cnt = 1
# 누적 plus를 한 횟수
# 더 큰 값이 나왔을 때 필요한 + 횟수를 계산할 때 사용
for i in range(n):
num = int(input())
# 더 큰 값이 나왔을 때 push
while cnt <= num:
S.append(cnt)
cnt += 1
ans.append('+')
# 더 작은 값이 나왔을 때 pop
# 혹은 push를 한 이후 pop 한 번 시행
if S[-1] == num:
S.pop()
ans.append('-')
# 불가능
else:
print("NO")
exit()
for i in ans:
print(i)정리
논리적인 생각, pseudo 코드 완성하고 코딩하기.
1. 전부 다 입력받고 출력해야한다고 착각함
2. +의 개수로 풀면 쉽다는 것은 캐치함 -> cnt를 스택에 넣을 생각은 못함
후위 표기식 2 / 1935 / 실버3
코드
N = int(input())
S = list(input())
num = []
sta = []
cnt = 0
for i in range(N):
num.append(int(input()))
# 문자열이 끝날 때까지 반복
while cnt != len(S):
# operator를 입력받으면 pop 2번, 연산
if S[cnt] == '*':
sta.append(sta.pop() * sta.pop())
elif S[cnt] == '/':
sta.append(1 / sta.pop() * sta.pop())
elif S[cnt] == '+':
sta.append(sta.pop() + sta.pop())
elif S[cnt] == '-':
sta.append(-sta.pop() + sta.pop())
# operand를 입력 받으면 해당 숫자로 변환
else:
sta.append(num[ord(S[cnt]) - ord('A')])
cnt += 1
print(f'{sta[0] :.2f}')정리
알파벳을 숫자로 변환하는 과정에서, 처음부터 다 변환하는 것으로 판단했다.
(push할 때 변환하면 됨)
역시 손으로 먼저 푸는게 맞는듯하다.
🔥 자료구조 2
최대 힙 / 11279 / 실버 2
코드
import heapq
import sys
maxHeap = []
N = int(sys.stdin.readline())
for _ in range(N):
x = int(sys.stdin.readline())
if x == 0:
if len(maxHeap) == 0: # 만약 배열 길이가 0이라면 0 출력
print(0)
else: # 가장 큰 값 pop
print(heapq.heappop(maxHeap)[1])
else: # 배열에 추가
heapq.heappush(maxHeap, (-x, x)) # heapq는 작은 순으로 정렬되기 때문에 -x로 정렬시킴정리
- 시간 초과가 나므로 input() 대신 sys.stdin.readline() 사용
import heapq heapq.heappush(heap, item) # item을 heap에 추가 heapq.heappop(heap) # heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출 heapq.heapify(x) # 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) ) #최대힙으로 만들기 #힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다. heapq.heappop(max_heap)[1]
N번째 큰 수 / 2075 / 골드 5
코드
import heapq
import sys
N = int(sys.stdin.readline())
heap = []
for _ in range(N):
data = list(map(int, sys.stdin.readline().split()))
if not heap: # heap이 비어있을 경우
for item in data:
heapq.heappush(heap, item)
else: # heap에 N개의 아이템이 있을 경우
for item in data:
# 힙의 최솟값보다 작은 경우 집어넣지 않음
if heap[0] < item:
heapq.heappush(heap, item)
heapq.heappop(heap) # heap의 크기 N으로 유지
print(heapq.heappop(heap)) # N번째로 큰 값 출력나는야 포켓몬 마스터 이다솜 / 1620 / 실버 3
코드
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = {}
for i in range(1, N+1):
x = input().strip()
a[i] = x
a[x] = i
for _ in range(M):
x = input().strip()
if x.isdigit():
print(a[int(x)])
else:
print(a[x])정리
- 개행문자를 제거하려면 strip함수를 사용하면 됨.
- 딕셔너리를 이용하면 더 빠른 시간 내에 검색 가능.
허쓸하는 좀비