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를 출력해주면 끝

2022.02.08 나이순 정렬

# 10814 나이순 정렬

N = int(input())
arr = []
for i in range(N):
    a, b = input().split()
    a = int(a)
    arr.append([a,b])
arr.sort(key = lambda x : x[0])

for i in arr:
    print(*i)

정렬해주는데 sort에 key값으로 람다를 써주는 게 키 포인트 같다.

람다를 사용해 arr의 숫자만 정렬해주는 것...

2022.02.08

백준 1874 스택수열

# 1874 스택수열
import sys

n = int(input())
stack = []
result = []
s = 0
for i in range(1,n+1):
    a = int(sys.stdin.readline())
    stack.append(a)
    if s - a < 0:
        for j in range(abs(s-a)):
            result.append('+')
        result.append('-')
        s = a
    else:
        if s - a > 1 and (s - 1) not in stack:
            result.append('NO')
            break
        else:
            result.append('-')
            s = max(a,s)
if 'NO' in result:
    print('NO')
else:
    for i in result:
        print(i)

입력받는 값을 저장하는 stack 리스트와 기호를 저장하는 result 리스트를 생성하고

s의 값을 변경해주면서 그 차이를 통해 result에 기호를 저장해줬다.

성공이라고 돼있어서 아 전에 풀어본 문제구나 하고 봤더니

전혀 기억이 안 나고 마치 새로운 문제를 보는 것 같았다.

어찌어찌 풀기는 했지만 시간 초과가 떠서 pypy3로 채점을 했다.

2022.02.07

백준 2164 카드 2

#2164 카드2

N = int(input())
arr = [i for i in range(1,N+1)]

while len(arr) != 1:
    s = arr[1]
    del arr[0]
    arr.append(s)
    del arr[1]

print(arr[0])

#2164 카드2
from collections import deque

N = int(input())
queue = deque()
for i in range(1,N+1):
    queue.append(i)
    
while len(queue) != 1:
    queue.popleft()
    queue.append(queue.popleft())

print(queue[0])

처음에 위 코드로 풀었다가 시간 초과가 떴다.

시간 복잡도는 while문 처음 시작할 때까지는 같은 거 같은데

무엇에서 차이나는 걸까