[CLASS 2]백준 11866번, 1654번, 1874번

11866번 : 요세푸스 문제 0

 

요세푸스 순열에 대한 설명이 나와 있고, N과 K 가 주어질 때 이 순열을 출력하면 된다.

 

내 코드:

n,k = map(int,input().split())
arr = [True for _ in range(n)]
li = []
idx = 0
for _ in range(n):
    count = 1
    while True:
        if arr[idx]:
            if count < k:
                count += 1
                idx = (idx + 1) % n
            else:
                arr[idx] = False
                li.append(str(idx+1))
                break
        else:
            idx = (idx + 1) % n

print('<'+', '.join(li)+'>')

 

리스트를 마치 원형처럼 구현하기 위해서는 모듈러(나머지)연산을 이용하면 된다. 리스트의 끝에 도달할 때마다 나머지가 0이 되어서 다시 처음으로 돌아갈 수 있다.

 

이 코드를 작성하고 제출하여 맞았는데, 다른 사람들의 코드의 속도가 내 코드보다 빨라서 코드를 보고 수정하였다.

 

내 코드(개선):

n,k = map(int,input().split())
arr = [i for i in range(1,n+1)]
li = []
idx = 0
while arr:
   idx = (idx + k - 1) % len(arr)
   li.append(str(arr.pop(idx)))

print('<'+', '.join(li)+'>')

 

이 코드는 위 코드와 달리 idx를 증가시킬때, 일일이 count 변수를 통해 세지 않고, 한번에 k - 1 을 더하여 넘어간다. 그리고 pop을 통해 리스트의 길이가 줄어든 것을 반영하기 위해 나누는 수를 리스트의 길이로 바꾸었다. 이렇게 구현하면 쓸데없이 count를 증가시키며 돌지 않기 때문에 성능이 향상된다.

 

1654번 : 랜선 자르기

 

문제의 정답률을 보면 20%밖에 되지 않는다. 이는 문제가 쉬워보여서 단순히 생각한데로 구현한다면 분명이 시간이나 메모리의 초과가 있음을 얘기한다.

 

문제를 처음 보면 가장 긴 랜선에서부터 시작하여 1m씩 높이를 줄여가면서 합을 구하면 될 것 같다. 그러나..

 

내 코드(시간 초과):

k,n = map(int, input().split())
lans = []
for _ in range(k):
    lans.append(int(input()))
lans.sort()
crit = lans[len(lans)-1]
while True:
    count = 0
    for lan in lans:
        count += lan // crit
    
    if count >= n:
        break
    else:
        crit -= 1

print(crit)

 

아니나 다를까. 바로 시간초과 당했다. 문제 조건에 주어질 수 있는 최대 랜선의 길이가 2의 31승-1M(지구에서 달까지의 거리의 5배가 넘는다..)이기 때문에 연산에 엄청난 값이 소모된다. 이럴때 이진탐색을 이용하면 빠르게 찾을 수 있다.

 

내 코드(이진 탐색):

import sys
input = sys.stdin.readline

k,n = map(int, input().split())
lans = []
for _ in range(k):
    lans.append(int(input()))

left = 1
right = max(lans)

while left <= right:
    mid = (left + right) // 2
    count = 0
    for lan in lans:
        count += lan // mid
    
    if count >= n:
        left = mid + 1
    else:
        right = mid - 1

print(right)

 

주어진 랜선중 가장 긴 랜선의 길이를 right에 저장. 그리고 가능한 가장 짧은 랜선의 길이를 left에 저장한 뒤, 이진 탐색을 수행하면 된다. 랜선의 길이를 mid로 자를때 생기는 랜선의 개수를 count에 저장한 뒤, 만약 요구하는 n 보다 많거나 같다면 길이를 늘리면 된다. 같아도 늘리는 이유는, 최대 랜선의 길이를 구해야 하기 때문이다.

 

1874번 : 스택 수열

 

스택에 어떻게 집어넣었다가 빼면 해당 수열을 맞출 수 있을지에 대한 문제이다. 언뜻 보면 하노이의 탑과도 비슷해 보인다.

 

내 코드:

import sys
input = sys.stdin.readline

n = int(input())
stack = []
log = []
count = 1
for _ in range(n):
    request = int(input())
    while count <= request:
        stack.append(count)
        log.append('+')
        count += 1
    
    if stack[-1] == request:
        stack.pop()
        log.append('-')
    else:
        print('NO')
        exit()
    
print('\n'.join(log))

request변수에 입력을 저장하고, count가 해당 request가 될 때까지 stack에 수를 추가한다. 스택에 request와 같은 값을 넣었을 시, 바로 pop을 해준다. 이 로직만 있으면 문제가 풀린다. 수열을 만들 수 없는 경우에는 if문에서 걸러져서 NO를 출력하고 바로 종료된다.