(Python) 알고리즘문제 D+5

Kepler·2020년 2월 14일
0

알고리즘

목록 보기
5/8

문제

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

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

예를 들어
strs = ['start', 'stair', 'step']
return은 'st'

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


해답_1 (my solution)

def get_prefix(string):
    if len(string) == 0:
      return ""
    min_len = min(string, key=len)   #제일 짧은 단어찾기
    for index, alphabet in enumerate(min_len):    #제일 짧은단어 길이와 알파벳 찾기 (0,s) (1,t) (2,a), (3,r)
    
        for word in string: #각 단어에 대입해보기
            if word[index] != alphabet: # 각 index의 알파벳과 제일 짧은 단어 알파벳 비교
                return min_len[:index]
                
    return min_len
  • 리스트(string)에서 가장 짧은 단어를 찾고, 그 단어의 철자를 다른 단어들의 철자와 비교하여, 같은 철자의 substring만큼만 return하는 방식으로 접근했다.
  • 가장 짧은 단어(min_len)를 찾기 위해서, min()함수를 사용하였다. key=len을 넘겨주면 각 요소의 길이를 키로 설정하여 iterate 할 수 있다.
  • 다음은 enumerate을 사용하여, 가장 짧은 단어의 철자(alphabet)와 그 인덱스(index)를 구한다.
  • Nested For loop을 사용하여 리스트의 각 단어(word)를 돌아가면서 체크한다. 체크하는 단어의 철자가 가장 짧은 단어의 철자(alphabet)와 같지 않은 시점에 도달하면, 가장 짧은 단어(min_len)의 철자 중 검사한 인덱스에 해당하는 철자 전 까지를 리턴한다. 이 부분은 문자열의 slice를 활용했다.

해답_2 (model solution)

def get_prefix(strs):
    if len(strs) == 0:
        return '' 
    res = ''
    strs = sorted(strs)
    for i in strs[0]:
        if strs[-1].startswith(res+i):
            res += i
        else:
            break
    return res
  • 빈문자열res를 설정했다. 이 빈문자열에 나중에 prefix가 저장된다.

  • sorted()를 사용하여 가장 짧은 길이의 단어가 인덱스 0 에 위치하게 하고, 인덱스 0 자리의 단어를 for문으로 돌렸다.

  • 가장 짧은 단어(strs[0])의 철자(i)와 가장 긴 단어(strs[-1])의 철자를 .startswith를 사용하여 비교하여, 같은 경우에는 인덱스를 하나씩 늘려서 다음 철자를 비교했다. 같지 않은 경우에 도달했을 때, break를 사용하여 for문을 exit하고, res 값을 리턴한다.


새로운개념

<문자열>.startswith(<문자열>) :

문자열이 첫번째 parameter에 적힌 문자로 시작하는지를 검사하며, 리턴값은 boolean이다. 옵션 parameters로 체크를 시작 또는 끝내는 인덱스의 위치를 다음과 같이 입력할 수 있다.

str.startswith(str, beg=0,end=len(string));

str = "this is string example....wow!!!";
print str.startswith( 'this' )
print str.startswith( 'is', 2, 4 )
print str.startswith( 'this', 2, 4 )
>>> True
>>> True
>>> False
profile
🔰

0개의 댓글