codekata3. 유일한 알파벳과 제일 긴 단어의 길이

wonseok2877·2021년 6월 23일
2

algorithm

목록 보기
3/9

문제 파악

String 형인 str 인자에서 중복되지 않은 알파벳으로 이루어진 제일 긴 단어의 길이를 반환해주세요.

요구사항 : 각각의 알파벳이 string안에서 유일한, 제일 긴 단어를 찾아라.

제한사항 : 없음

인풋 : string값

아웃풋 : 단어의 길이

생각 과정

  1. 리스트 내 각각의 요소들끼리 비교한다. 중복되는 요소들을 다른 리스트 혹은 딕셔너리에 넣는다. set에다 넣을까??

  2. 대상 string에 대해서, 중복되는 요소가 발견되면 그 앞까지 슬라이싱해서 변형시킨다.

  3. 그렇게 만들어진 리스트중에서, 가장 길이가 긴 요소의 길이를 반환한다.

첫번째 방법

결론부터 말하면 실패다. 가장 긴 단어가 아니라, 그저 알파벳을 중복되지 않게 차곡차곡 넣기만 하는 이상한 로직이 되어버렸다. 이렇게 되면 abcdefaaaaaaa같이 단순한 경우, 혹은 abcabcabcd경우밖에 안 된다.

def get_len_of_str(s):
    my_list = []
    my_str = ""
    for c in s:
        if my_str.count(c) > 0:
            continue
        my_str += c
        s = s[1:]
        print(c)
        my_list.append(my_str)
    return len(max(my_list))

두번째 방법

짝꿍님이 생각하신 방법. 최대길이를 할당할 변수와 가장 긴 단어를 할당할 변수를 선언해놓고, 반복문을 시작한다. 만약 단어 변수 안에 해당 글자가 이미 있다면, 단어 변수를 초기화한다. 아직 없다면, 단어에 그 글자를 추가한다. 그리고 그 단어의 길이가 최대길이 변수보다 길 경우, 변수에다 그 단어의 길이를 할당한다.

def get_len_of_str(s):
    max_len = 0
    is_in_list = ""
    for c in s:
        if c in is_in_list:
            is_in_list = ""
        is_in_list += c
        if len(is_in_list) > max_len:
            max_len = len(is_in_list)
    return max_len

세번째 방법

충격적이게도 이것도 실패였다.
abcaf라는 string에서 반복되는 알파벳 없이 가장 긴 단어는? 당연히 bcaf다. 그러나 앞에서 나온 방법들은 알파벳이 반복될 경우 바로 string을 자르니까, abc를 가장 긴 단어로 만들게 된다.

그래서 각 글자들의 index를 어딘가에 저장해야만 한다. 그래야만 중복되는 글자가 나왔을 때, 이전 글자의 바로 뒤 index에서부터 단어를 만들 수 있기 때문이다.

동명(선생)님이 생각하신 방법.

def get_len_of_str(s):
    s_dict = {}
    start_index = 0
    result = 0
    for i, c in enumerate(s):
        if c in s_dict and s_dict[c] >= start_index:
            start_index = s_dict[c] + 1
        print(i - start_index)
        result = max(result, i - start_index + 1)
        s_dict[c] = i
	return result

생각

  1. 문제를 파악하고 스스로 생각하는 과정을 지켜보는 게 확실히 도움이 된다.
  2. 아직 문제를 제대로 파악하고, 생각을 정리하고, 전달하는 실력이 많이 부족하다.
  3. enumerate는 아무리 봐도 편하다.
  4. 딕셔너리를 이용하는게 코드를 훨씬 간단하게 만들어줬다.
  5. max함수 좋다.
profile
백엔드 지망생 (벨로그 탈주각 재는중)

0개의 댓글