[CLASS 2]백준 1966번, 2805번, 1929번

1966번 : 프린터 큐

 

상근이라는 친구가 프린터 소프트웨어를 만들었는데, 큐를 적용한듯 하다. 해당 문서가 몇 번째에 출력될 지 맞추면 된다.

 

처음에는 큐로 해야할듯 해서 collections의 deque를 사용했다. 그런데 나중에 그냥 list로 바꿔봤는데 오히려 속도가 약간 더 빨라졌다..

 

내 코드(덱):

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, m = map(int,input().split())
    queue = deque(list(map(int,input().split())))

    count = 0
    while True:
        if max(queue) > queue[0]:
            queue.append(queue.popleft())
            if m == 0:
                m = len(queue) - 1
            else:
                m -= 1
        else:
            queue.popleft()
            count += 1
            if m == 0:
                print(count)
                break
            else:
                m -= 1

 

내 코드(리스트):

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, m = map(int,input().split())
    queue = list(map(int,input().split()))

    count = 0
    while True:
        if max(queue) > queue[0]:
            queue.append(queue.pop(0))
            if m == 0:
                m = len(queue) - 1
            else:
                m -= 1
        else:
            queue.pop(0)
            count += 1
            if m == 0:
                print(count)
                break
            else:
                m -= 1

 

코드는 덱이랑 리스트인것만 다르고 나머지는 완전히 같다. 큐에서 가장 큰 값과 0번 인덱스를 비교하여 pop할지 아니면 뒤로 넘길지 고르면 된다. 주의할 점은 m변수가 출력되지 못하고 큐의 뒤로 넘어갈 때 음수가 되지 않도록 해줘야 한다.

 

2805번 : 나무 자르기

 

상근이가 이번에는 나무를 자르는데, 신기한 절단기를 가져와서 나무를 한번에 자른다. 이 문제는 저번 글에 있던 랜선 문제와 매우 유사하다. 이번에도 높이가 20억미터같은 터무니없는 값이 가능하기 때문에 이진 탐색을 이용하여 자를 높이를 정해야 한다.

 

내 코드(시간 초과):

# 이진 탐색
n, m = map(int,input().split())
heights = list(map(int,input().split()))

left = 0
right = max(heights)

while left <= right:
    mid = (left + right) // 2
    myTree = 0
    # 이 부분 개선 필요
    for tree in heights:
        if tree > mid:
            myTree += tree - mid
    
    if myTree >= m:
        left = mid + 1
    else:
        right = mid - 1

print(right)

 

그래도 이번엔 이진 탐색을 이용하여 자신있게 제출했는데 시간 초과 당했다... pypy3로 하면 통과한다. 어디서 미묘하게 시간이 느려졌나 다른 분들의 코드를 보니 나무의 높이와 자를 높이를 비교하는 과정에서 Counter 를 사용해서 시간을 줄였다. 나는 for 문을 사용해서 일일이 계산하느라 느려진 것 같아 Counter를 사용해봤다.

 

내 코드(이진 탐색,Counter):

# 이진 탐색(Counter 이용)
from collections import Counter
n, m = map(int,input().split())
heights = Counter(map(int,input().split()))

left = 0
right = max(heights)

while left <= right:
    mid = (left + right) // 2
    myTree = 0
    for tree,count in heights.items():
        if tree > mid:
            myTree += (tree - mid) * count
    
    if myTree >= m:
        left = mid + 1
    else:
        right = mid - 1

print(right)

 

Counter를 이용하여 높이가 같은 나무들을 한번에 곱하기로 처리해 줬더니 통과했다. 아마 테스트 케이스에서 길이가 같은 나무를 엄청 많이 주는 케이스가 있었던 것 같다.

 

1929번 : 소수 구하기

 

소수를 구하는 문제이다. 저번에도 이런 문제를 풀었었는데, 이번엔 M 이상이라는 조건이 붙었다. 저번과 같은 원리를 적용하면 이런 코드를 작성할 수 있다.

 

내 코드:

# 그냥 나눠보는 방법(느림)
m, n = map(int,input().split())

def isPrime(number,primes):
    sqrt = int(number**0.5)
    for prime in primes:
        if prime <= sqrt:
            if i % prime == 0:
                return False
        else:
            return True

primes = [2]
for i in range(3,n+1):
    if isPrime(i,primes):
        primes.append(i)

print('\n'.join([str(i) for i in primes if m <= i]))

 

단점이 있다면 좀 느리다. 매번 제곱근을 구하고 비교하기 때문이다. 이번에는 문제 분류에도 쓰여있는 에라토스테네스의 체를 써봤다.

 

내 코드(에라토스테네스의 체):

# 에라토스테네스의 체
m, n = map(int,input().split())

def isprime(m, n):
    primes = [False,False] + [True] * (n - 1)
    for i in range(2, int(n**0.5)+1):
        if primes[i]:
            for j in range(i*2, n+1, i):
                primes[j] = False

    for i in range(m,n+1):
        if primes[i]:
            print(i)

isprime(m,n)

 

에라토스테네스의 체는 간단히 말해 어떤 수의 배수는 모두 없애는 방식이다. 2의 배수는 2를 제외 모두 없어지고(False가 되고) 3의 배수도 3을 제외하고 없어지고... 를 반복하여 n의 제곱근까지 해주면 된다. 여기서 더 나아가 n의 제곱근 이하의 소수의 배수만 없앨수도 있겠지만.. 이정도도 충분히 빠르다!