2022.03.08

백준 1966 프린터 큐

#1966 프린터 큐
from collections import deque
# 테스트 케이스  T
T = int(input())

for i in range(T):
  N,M = map(int, input().split())
  
  # 인덱스의 변화를 보여줄 큐, idx를 하나 만든후 인덱스를 저장한다.
  idx = deque()
  for j in range(N):
    idx.append(j)
    
  # arr에 우선순위로 주어진 입력값을 저장한다.
  arr = deque()
  array = list(map(int, input().split()))
  for j in array:
    arr.append(j)
  
  # num은 queue에서 값이 pop될 때마다 +1 해줘 M번째 값이 몇 번째로 출력되는지 계산한다.
  num = 1
  while True:
    if M == idx[0] and arr[0] == max(arr):
      print(num)
      break
    else:
      if max(arr) == arr[0]:
        arr.popleft()
        idx.popleft()
        num += 1
      else:
        arr.append(arr.popleft())
        idx.append(idx.popleft())

그동안 고민하면서 못 풀었던 문제를 드디어 풀었다.

처음에는 큐 하나만 이용해서 풀려고 하다가 인덱스도 큐로 만들어서 변화를 주어야겠구나 생각을 하게 되었고

또 거기서 한동안 못풀다가 while문에서 멈추는 조건을 잘 못주고 있었다는 걸 깨닫고 풀 수 있었다.

2022.02.26

백준 14501 퇴사

# 14501 퇴사

N = int(input())
T = []
P = []

# 날짜와 금액을 나눠 사용하기 위해 두 리스트에 나눠 저장한다.
for i in range(N):
    a,b = map(int, input().split())
    T.append(a)
    P.append(b)

# result에는 각 날짜로 얻을 수 있는 가장 큰 금액을 저장한다.
result = []
for i in range(N):
    # 현재 날짜와 수행해야 하는 일수를 더해 퇴사날보다 늦으면 0 아니면 P의 값을 저장
    if i + T[i] <= N:
        result.append(P[i])
    else:
        result.append(0)

# 현재 날짜의 수행에 필요한 일수 이후의 날짜이면서 result의 값이 0이 아닌경우
# 얻을 수 있는 최대의 값을 구해준다.
for i in range(N):
    num = i+T[i]
    for j in range(num,N):
        if result[j] != 0:
            result[j] = max(result[j], result[i] + P[j] )

        
print(max(result))        

2022.02.25 알고리즘 스터디

백준 13458 시험감독

# 13458 시험감독
import sys
N = int(input())
A = list(map(int, sys.stdin.readline().split()))
B,C = map(int, input().split())

# cnt = 총 감독관을 제외한 부 감독관의 수
cnt = 0
for i in A:
    j = i - B
    if j > 0:
        if j/C > j//C:
            cnt += j//C + 1
        else:
            cnt += j//C
print(cnt + N)

스터디의 마지막 날... 마지막 날이라고 그냥 쉬운 문제 풀자고 했다 ㅋㅋ

브론즈 2문제인데 이제는 실버 아랫단계 문제나 브론즈 1,2랑 무슨 차이인지는 잘 모르겠다 둘 다 어려운데??

처음에 문제를 잘못 이해해서 총감독관의 수가 0 아니면 1이라고 생각을 하고 코드를 짰는데

알고 보니 총감독관은 각각의 시험장에 무조건 1명이 존재하는 문제였다.

2022.02.23

백준 1654 랜선 자르기

# 1654 랜선 자르기

# K,N 입력받는 값
K, N = map(int, input().split())

# K 줄에 걸쳐 입력받는 값을 arr에 저장
arr = []
for i in range(K):
    arr.append(int(input()))

#이분탐색을 시작할 start와 end값을 지정해준다
start = 0
end = max(arr)

while start <= end:
# end가 1일 경우 mid가 0이 되어 ZeroDivisionError가 발생하는걸 막는다.
    if end == 1:
        break
    mid = (start+end)//2
# arr 값을 하나씩 받아와 mid로 나눠진 몫으로 랜선의 갯수를 파악한다. 
    M = 0
    for i in arr:
        M += i//mid
    
    if N > M:
        end = mid - 1
    else:
        start = mid + 1
print(end)

처음 ZeroDivisionError가 발생했을 때는 try, except 구문을 사용하여 단순히 넘기는 시도를 했다.

그런데 그럴 경우에는 N과 K의 숫자가 같으면서 가장 긴 랜선의 길이가 1일 때

올바른 답을 출력시키지 못했기 때문에 다른 방법을 찾아봐야 했다.

여러 방법을 사용해봐도 틀렸습니다만 뜨길래 어떻게 풀어야 할까 생각하던중에

문제가 되는 것은 end가 1일 때만이라는 걸 생각하고 그냥 end가 1이면 반복문을 끝내는 조건을 써넣었다.

2022.02.22

백준 10816 숫자 카드 2

# 10816
import sys
N = int(input())
arr = list(map(int, sys.stdin.readline().split()))
M = int(input())
fin = list(map(int, sys.stdin.readline().split()))

num = {}
for i in arr:
    num[i] = 0

for i in arr:
    num[i] += 1

for i in fin:
    try:
        print(num[i], end = ' ')
    except:
        print(0, end = ' ')

count 함수를 사용하면 되지 않을까? 생각했는데 입력 숫자가 커서 그런가 역시나 시간 초과가 나왔다.

그래서 이분탐색 알고리즘을 써야 하나 했는데 라이브러리를 사용하지 않고는 어떻게 풀이할지 생각이 나질 않아서

그냥 딕셔너리로 풀었다.

N개의 주어진 숫자들을 키값으로 하여 같은 값이 나오면 +1씩 해줬다.

그래서 M개의 주어진 숫자들의 키값에 저장된 값을 출력하는데 try, except 구문을 사용하여

키값이 없을 경우 0을 출력하게 했다.

2022.02.15

백준 10773 제로

# 10773 제로
import sys
K = int(input())
num =[0]

for i in range(K):
    r = int(sys.stdin.readline())
    if r == 0:
        num.pop()
    else:
        num.append(r)
print(sum(num))

반복적으로 입력받아야 하는 K의 숫자 범위가 커서 sys를 사용했다.

스택으로 쉽게 풀 수 있는 문제로 입력받은 숫자를 리스트에 하나씩 넣어주다가

0을 입력받으면 최근에 입력받은 숫자를 pop으로 추출하면 된다.

백준 9012 괄호

# 9012 괄호

N = int(input())
for i in range(N):
    R = list(input())
    if R[0] == ')' or R[-1] == '(':
        print('NO')
    else:
        num = 0
        for j in R:
            if j == '(' and num >= 0:
                num += 1
            else:
                num -= 1
        if num == 0:
            print('YES')
        else:
            print('NO')

먼저 입력으로 받아오는 괄호의 맨 앞과 맨 뒤가 틀리면 바로 'NO'를 반환해준다.

양끝 값이 정상으로 되어있다면 그 안의 괄호 순서의 값을 구해서 답을 출력한다.

num이라는 변수에 0을 할당해 생성해주고

'(' 괄호는 먼저 나와야 하는 괄호이므로 num이 0 이상일 때만 카운트한다.

'(' 괄호가 나오기 전에 ')' 괄호가 나왔다면

num이 마이너스 숫자가 되어서 'NO'를 출력하게 된다.

2022.02.15

백준 1904 타일 01

#1904

N = int(input())
dp = [0]*(N+1)

if N == 1:
    print(1)
elif N == 2:
    print(2)
else:
    dp[1] = 1
    dp[2] = 2
    for i in range(3,N+1):
        dp[i] = (dp[i-2] + dp[i-1])%15746
    print(dp[N])

점화식 자체는 피보나치수열과 같다.

거기에 문제에서 주어진 메모리 초과를 해결해주기 위해서

문제풀이 과정에서 나머지를 구해주면 된다

2022.02.09

#10989 수 정렬하기 3
import sys

N = int(input())
num = [0] * 10001
for i in range(N):
    num[int(sys.stdin.readline())] += 1

for i in range(10001):
    for j in range(num[i]):
        print(i)

주어진 수의 범위가 10,000까지니까 10,001개가 0으로 담긴 리스트를 만든다.

그리고 입력받는 숫자를 인덱스로 삼아서 그 숫자가 등장할 때마다 + 1을 해준다.

다음으로 누적된 숫자만큼 인덱스를 출력해주면 된다.

정렬하기라 간단한 문제인줄 알았는데 메모리 초과를 해결하는데 한참 걸렸다...

그다음은 시간 초과를 해결해야 했네...

2022.02.08 요세푸스 문제

#11866 요세푸스 문제
from collections import deque

N, K = map(int, input().split())
arr = deque()
for i in range(1,N+1):
    arr.append(i)
result = []

for i in range(N):
    for j in range(K-1):
        arr.append(arr.popleft())
    result.append(arr.popleft())

print('<', end = '')
print(*result,sep=', ',end='')
print('>')

수학적으로 풀어 보려다가 큐로 풀면 될 것 같아서 큐로 풀었다.

입력받은 K-1개만큼 리스트의 뒤로 보내주고 K번째 것만 새로운 리스트인 result에 담아준다.

그리고 result를 출력해주면 끝