코드.kr

BOJ 29363 - Пишущая машинка

8 min read

문제 링크

문제 요약

주어진 n개의 단어를 각 줄에 하나씩 타이핑하는 데 필요한 최소 키 입력 횟수를 계산하는 문제입니다.

이 타자기는 일반적인 문자 입력과 개행(새 줄) 기능 외에 두 가지 특별한 기능을 가지고 있습니다.

  1. 마지막 문자 삭제: 현재 줄의 마지막 문자를 지웁니다. (1회 입력)
  2. 이전 줄의 마지막 단어 복사: 새로운 줄의 시작에서, 아직 아무것도 입력되지 않은 상태일 때만 작동합니다.

문제에서 각 줄에 단어 하나만 입력되므로, “이전 줄의 마지막 단어”는 곧 “이전 줄 전체 단어”를 의미합니다. 첫 번째 줄을 제외한 각 줄에서는 새로운 단어를 입력하는 두 가지 방법(전부 새로 타이핑 vs 이전 줄 복사 후 수정) 중 더 효율적인 방법을 선택해야 합니다.

풀이

이 문제는 각 줄을 타이핑하는 데 드는 최소 비용을 계산하여 전체 합을 구하는 Greedy (그리디, 탐욕법) 방식으로 해결할 수 있습니다.

각 줄을 완성하는 시점에서 이전 줄을 바탕으로 현재 줄을 만드는 두 가지 주요 방법 중 더 효율적인 것을 선택합니다.

  1. 첫 번째 줄 (l[0]):

    • 첫 번째 줄은 이전에 완성된 줄이 없으므로, 모든 문자를 직접 입력하는 수밖에 없습니다.
    • 따라서 비용은 l[0]의 길이, 즉 len(l[0])이 됩니다.

  2. 두 번째 줄부터 (l[i], i > 0):

    • 각 줄로 이동할 때마다 개행 문자 1회가 필요합니다. 이 비용은 항상 발생하므로, 최종 결과에 미리 더해두거나 각 줄의 계산 비용에 포함시킵니다. (코드에서는 ans += 1로 처리)

    • 현재 줄 l[i]를 만들기 위한 두 가지 방법 중 더 적은 비용이 드는 방법을 선택합니다.

      • 방법 1: l[i] 전체를 새로 입력하는 경우
        • 비용: len(l[i]) (문자 수)
      • 방법 2: 이전 줄 l[i-1]을 복사한 후 수정하는 경우
        • 이 방법은 새로운 줄 시작에서 1회 복사하는 키 입력이 필요합니다.
        • 이후 l[i-1]을 l[i]로 변형해야 합니다.
        • l[i-1]과 l[i]의 가장 긴 공통 접두사(Longest Common Prefix, LCP)를 찾습니다. LCP의 길이를 common_len이라고 하겠습니다.
        • 삭제 횟수: l[i-1]에서 common_len 이후의 문자들은 삭제해야 합니다. 이 횟수는 len(l[i-1]) - common_len입니다.
        • 입력 횟수: l[i]에서 common_len 이후의 문자들은 새로 입력해야 합니다. 이 횟수는 len(l[i]) - common_len입니다.
        • 총 비용: 1 (복사) + (len(l[i-1]) - common_len) (삭제) + (len(l[i]) - common_len) (입력)

    • common_len 계산:

      • 코드는 differnt_idx 변수를 사용하여 l[i-1]과 l[i]가 처음으로 달라지는 인덱스를 찾습니다. 이것이 common_len의 역할을 합니다.
      • l[i-1]과 l[i]를 앞에서부터 비교하여 일치하는 문자가 어디까지인지 확인합니다.
      • 만약 l[i-1]과 l[i]가 한쪽이 다른 쪽의 접두사인 경우 (예: “apple”과 “apples”), differnt_idx는 -1이 됩니다. 이 때는 짧은 문자열의 길이가 common_len이 됩니다.
        • l[i-1]이 l[i]의 접두사이면 (len(l[i]) > len(l[i-1])): l[i-1]을 복사한 후 len(l[i]) - len(l[i-1])개의 문자를 추가합니다. (삭제는 0회)
        • l[i]가 l[i-1]의 접두사이면 (len(l[i]) <= len(l[i-1])): l[i-1]을 복사한 후 len(l[i-1]) - len(l[i])개의 문자를 삭제합니다. (추가는 0회)
      • l[i-1]과 l[i]가 중간에 달라지는 경우 (예: “apple”과 “apricot”):
        • differnt_idx 이후의 l[i-1] 부분을 모두 삭제하고 (len(l[i-1]) - differnt_idx 횟수),
        • differnt_idx 이후의 l[i] 부분을 새로 입력합니다 (len(l[i]) - differnt_idx 횟수).

    • 각 줄 i에 대해 min(방법 1 비용, 방법 2 비용)을 계산하여 총 ans에 더합니다.

정답 코드

def solve():
  n = int(input())
 
  l = [input() for _ in range(n)]
 
  ans = len(l[0]) # 첫 번째 줄은 무조건 길이만큼 입력
 
  for i in range(1, n):
    ans += 1  # 다음 줄로 넘어가는 개행(newline) 1회
 
    # 방법 1: 현재 문장을 처음부터 그냥 다 쓰기
    cost_option1 = len(l[i])
 
    # 방법 2: 이전 문장을 복사한 후, 뒤에서부터 다른 문자를 다 지우고 다시 작성
    differnt_idx = -1 # 이전 문장과 현재 문장이 처음으로 달라지는 인덱스
 
    # 두 문자열의 길이 중 작은 값만큼 비교
    for j in range(0, min(len(l[i]), len(l[i-1]))):
      if l[i][j] != l[i-1][j]:
        differnt_idx = j
        break
 
    delete_count = 0
    add_count = 0
 
    if differnt_idx == -1: # 이전 문장이 현재 문장의 접두사이거나, 현재 문장이 이전 문장의 접두사이거나, 두 문장이 완전히 동일한 경우
      if len(l[i]) > len(l[i-1]):
        # 이전 문장이 현재 문장의 접두사: 복사 후 나머지 추가
        add_count = len(l[i]) - len(l[i-1])
      else:
        # 현재 문장이 이전 문장의 접두사 또는 동일: 복사 후 나머지 삭제
        delete_count = len(l[i-1]) - len(l[i])
    else: # 이전 문장과 현재 문장이 중간에 달라지는 경우
      # differnt_idx부터 이전 문장의 끝까지 삭제
      delete_count = len(l[i - 1]) - differnt_idx
      # differnt_idx부터 현재 문장의 끝까지 추가
      add_count = len(l[i]) - differnt_idx
 
    # 복사 1회 + 삭제 횟수 + 추가 횟수
    cost_option2 = 1 + delete_count + add_count
    
    # 두 방법 중 최소 비용을 선택하여 총합에 더함
    ans += min(cost_option1, cost_option2)
  
  print(ans)
 
 
if __name__ == "__main__":
  tc = 1
  for t in range(1, tc+1):
    ret = solve()

연관 페이지

참고 문헌 / 사이트

그래프 뷰