알고리즘 - codekata day5

min00young·2020년 11월 8일
0

문제

strs은 단어가 담긴 배열입니다.

공통된 시작 단어(prefix)를 반환해주세요.

예를 들어

strs = ['start', 'stair', 'step']
return'st'

strs = ['start', 'wework', 'today']
return''

풀이

이번 문제에서 공통된 시작 단어인 prefix(접두어)를 찾는 문제입니다.

일단은 함수로 넘겨주는 인자가 배열로 된 형태로 단어를 전달하게 되는것을 볼 수 있습니다.
단어의 길이는 각각 다양하게 이루어져있고, 일단 단어가 3개 주어진다고 볼때,
3개의 단어에서 공통으로 일치하는 접두어를 찾아야 합니다.

3개를 각각 비교하는 방법보다, 파이썬 기본제공함수인 sorted()함수를 통해서 입력받은 단어를 알파벳순으로 정렬을 합니다.

이제는 정렬된 단어에서 첫번째 단어와 마지막단어인 세번째 단어를 각각 앞에 한글자씩 비교하면서 공통된 시작단어를 고르는 과정을 시작합니다.

첫단어를 선택하기 위해서 string[0]을 통해서 첫번째 단어를 지정했고, 반복문을 통해서 앞에서부터 한글자씩 나오도록 처리를 하였습니다.
그리고 한단어가 나오면, 마지막 단어 string[-1]을 첫번째 단어와 일치하면 true값이 나오도록 startswith()함수를 이용하여서 반복문과 조건문에 대한 로직을 구성하였습니다.

true값일경우, 결과출력변수인 result에 한단어씩 추가를 하고, 만약에 false값이 나오면 공통된 단어가 없는것이기때문에 바로 반복문을 종료하도록 하였습니다.

정답코드

def get_prefix(string):
  if len(string) == 0:
    return ''
  result = ''
  string = sorted(string)
  
  for i in string[0]:
    if string[-1].startswith(result + i):
      result += i
    else:
      break
  return result
	
get_prefix(['start', 'stair', 'step'])
profile
개발공부를 하면서 배우고 경험하고 앞으로 알아가야할것들에 대해서 정리하고 있습니다 🙂

0개의 댓글