[Algorithm] 문자열 합치기 (Algospot – STRJOIN)

By | 2018-09-15

출처

  • https://algospot.com/judge/problem/read/STRJOIN
  • 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 (구종만)

난이도

  • 하 – (중) – 상 – 최상 – 풀지 못함

문제

  • 100개 이하의 String의 길이가 Input으로 주어진다. 주어진 String을 모두 합치고 싶다. String을 합치기 위해서는 두 개의 String 길이 만큼 For Loop을 돌아야 한다. 예를 들어 “st”, “ri”, “ng”가 Input으로 주어지면, 먼저 “stri”를 만들기 위해 총 4번의 For Loop을 돌아야 한다. “string”이라는 단어를 만들기 위해서는 총 10((2+2) + (4+2))번 For Loop을 돌아야 한다. 주어진 String을 모두 합치기 위해 For Loop을 돌아야 하는 최소 횟수를 찾는 문제이다.

후기

  • 역시나 책을 읽고 있어서 탐욕법을 사용해서 문제를 해결해야 한다는 생각은 했다.
  • 문제를 읽고 바로 Priority Queue를 사용해서 문제를 풀면 쉽게 풀릴 것 같았다. 그래서 Priority Queue를 만들어서 가장 짧은 문장을 먼저 합치고, 새롭게 만들어진 문자열을 Priority Queue에 추가하는 방법으로 문제를 해결하였다. Priority Queue를 너무 오랜만에 구현해서 실수를 몇 번 하였다. 지난번에도 비슷한 실수를 했는데 Priority Queue에 Pop을 할 때 Left Tree Node와 Right Tree Node가 Parent Node보다 값이 작을 경우 바꾸는 부분에서 항상 실수한다. Left와 Right Tree Node 모두가 Parent Node보다 작을 경우 Left와 Right Tree Node중 더 작은 수를 Parent로 만들어야 하는데 항상 이부분에서 실수한다.
  • 문제를 풀고 책에 작성된 답안을 보니 동일한 답안이였다.

코드

  • 탐욕법을 사용한 코드
  • Github 주소: https://github.com/mkblog-cokr/algorithmCode
  • 실행 시간: 1ms (제일 빠른 코드와 동일한 성능)

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *