그대로 출력하기 2/문자열 반복/랜선 자르기

 

01 [백준] 11719번 그대로 출력하기 2

입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 주어질 수도 있고, 각 줄의 앞 뒤에 공백이 있을 수도 있다. 입력받은 그대로 출력한다.

while True:
  try:
    print(input())
  except:
    break

 

그냥 입력받은 그대로 출력하는 거라서 간단한 줄 알았는데, 정답을 찾아보기 전까지는 못 풀었을 문제였다. 사용자가 종료하기 전까지는 계속 동작하기 위해서 while과 try-except를 사용하는 것 같다.

 

02 [백준] 2675번 문자열 반복

T = int(input())

for _ in range(T):
    answer = ''
    n, word = input().split()
    for i in word:
        answer += i*int(n)
    print(answer)

 

이 문제는 주어진 숫자만큼 알파벳을 반복하는 문제였다. 1년 전에도 두 번이나 풀었던 흔적이 있었고, 그래서 더 익숙하게 풀었다. 

 

03 [백준] 1654번 랜선 자르기

이 문제는 이진탐색 문제이다. 그래서 문제를 풀기 전, 나동빈씨의 이진탐색 강의를 가볍게 들어보았다.

 

이진탐색은 주로 "정렬"되어 있는 리스트에서 탐색할 때 활용한다. 시작점과, 끝점, 그리고 중간점을 이용하여 탐색을 진행한다.

이 알고리즘의 시간 복잡도는 O(logN)이다. 

 

이진탐색을 위한 라이브러리도 존재한다. bisect_left(), bisect_right()가 있는데, 일단 나는 전체적인 동작 원리를 이해하는 것이 우선이니, 요 라이브러리들은 보류했다.

 

K, N = map(int, input().split())
K_lst = [int(input()) for _ in range(K)]
start, end = 1, max(K_lst) # 이분 탐색 처음과 끝 위치 

while start <= end:
    median = (start + end) // 2
    N_cnt = 0 

    for i in K_lst:
        N_cnt += i // median
    if N_cnt >= N:
        start = median + 1 # 더 긴 길이도 가능한지 확인
    else:
        end = median - 1 # 너무 긴 경우, 더 짧게 잘라야 함
print(end)

 

시작점은 start고, 끝점은 end, 중간점은 median 변수를 사용하였다. while문에서 start가 end보다 작거나 같으면 계속 반복한다. N_cnt는 필요한 랜선의 개수에 부합하는지 확인하기 위한 카운트 변수이다. 

 

for문에서는 모든 가지고 있는 K개의 랜선에 대해 median으로 나누어진다면 몇 번이나 나누어지는지에 대해 N_cnt에 누적한다. 

 

if문에서는 N_cnt가 N보다 많다는 것은 즉, 랜선의 길이를 더 길게 해도 된다는 의미이기에, start를 median 오른쪽으로 옮긴다. 

만약 그렇지 않다면, 랜선의 길이를 너무 길게 잡은 것이기에 end를 median 왼쪽으로 옮긴다.

 

그렇게 while문 계속 반복하다보면, end가 랜선의 최대길이가 된다. 

 

---

 

사실 이번주 문제가 실버 하나, 골드 두 개, 보너스까지 총 네 문제나 남았는데 못 풀었다 .. 안 푼 게 아니라 어려워서 못풀었다 ㅜ