🌈 중복되지 않은 알파벳 중 가장 긴 단어의 길이
🤔 나의 Solution
String 형인 str 인자에서 중복되지 않은 알파벳으로 이루어진 제일 긴 단어의 길이를 반환해주세요.
str: 텍스트
return: 중복되지 않은 알파벳 길이 (숫자 반환)
✔️ 예를 들어, str = "abcabcabc"가 주어진다면 3을 반환한다. abc가 가장 긴 문자열이기 때문이다.
✔️ str = "aaaaa"이 주어진다면 1을 반환한다. 모두 반복되기 떄문에 a가 가장 긴 문자열이기 때문이다.
✔️ str = "sttrg"이 주어진다면 3을 반환한다. "trg"가 제일 길기 때문이다.
def get_len_of_str(s): res_len = 0 for i in range(len(s)): current_s = "" current_len = 0 for i in s[i:]: if i not in current_s: current_s += i current_len += 1 else: current_s = i current_len = 1 if res_len < current_len: res_len = current_len return res_len s = "sttrg" print(get_len_of_str(s)) # 3
✔️ 최종적으로 가장 긴 단어의 길이를 저장하는 res_len을 만들어두고, 이를 계속 업데이트 시켜 최종적으로 반환해주기로 했다.
✔️ for문을 통해 문자열의 길이만큼 index를 순회하고, 내부에서 현재의 가장 긴 문자열과 현재 가장 긴 문자열의 길이를 받아둘 변수를 지정했다.
✔️ 이후 문자열을 idex 기준으로 str[0:], str[1:], str[2:], str[3:]... 이런식으로 반복시켜 i값이 current_str에 있는지 없는지를 제어하였다.
✔️ 만일 current_str에 없는 문자열이라면 current_s에 이어붙이고, current_len을 1씩 증가시켜 길이를 체크했다.
✔️ 반면 current_str에 이미 있는 문자열이라면, current_s와 current_len를 초기화시켰다.
✔️ 이 제어문이 이후 if문에서는 최종적으로 반환할 res_len에 담긴 길이와 현재 current_len에 담긴 길이를 비교해서 더 큰 값으로 res_len을 업데이트했다.
✔️ 이 방법에도 TEST 통과에는 문제가 없다.
🤔 찾은 Solution
def get_len_of_str(s): res = {} start = 0 end = 0 for index, value in enumerate(s): # print(f"index : {index} / value : {value}") if value in res and start <= res[value]: # 👈 이미 res안에 key가 존재하고, 그 key의 value가 start보다 크거나 같을 때,, start = res[value] + 1 # 👈 해당 key값의 value를 1 상승시킨다. else: # 👈 그렇지 않을 때, end = max(end, index-start+1) # 👈 현재 end값과 index-start+1한 값 중 큰 값을 end로 업데이트시킨다. res[value] = index # print(f"res : {res}") # print('#') return end s = "sttrg" print(get_len_of_str(s)) # 3
✔️ Dict 자료구조를 활용하여 해결하는 방법이다. start 변수는 이미 존재하는 문자를 만났을 때, 그 index를 기억해서 end값을 처리하는데 사용된다.
✔️ 중복되지 않는 문자가 연속된다면 start는 0을 유지하기 때문에 end값은 "index + 1"이 된다. 1을 증감시켜주는 이유는 index가 0부터 시작하기 때문이다.
✔️ end에는 최근 중복이 되기 전까지 문자열의 갯수를 기억하기 때문에 그 값과 중복이 존재해서 새로 문자 갯수를 카운트하기 시작한 값(index-start+1) 중 큰 값을 업데이트 시키는 방법으로 가장 긴 문자열을 기억시킨다.
index : 0 / value : s # 👈 for문의 n번째 index, value값 res : {'s': 0} # 👈 res가 비어있기 때문에 else 구문이 작동하여 's'가 key값으로 index가 value값으로 추가 start : 0 / end : 1 # 👈 start = 0, end = max(end:0, index-start+1:1) # index : 1 / value : t # 👈 for문의 n번째 index, value값 res : {'s': 0, 't': 1} # 👈 res에 't'가 key로 존재하지 않기 때문에 else구문이 작동되어 현재 index값을 value값으로 res에 추가 start : 0 / end : 2 # 👈 start = 0, end = max(end:1, index-start+1:2) # index : 2 / value : t # 👈 for문의 n번째 index, value값 res : {'s': 0, 't': 2} # 👈 res에 't'가 이미 존재하고, start값보다 res[value]값이 크기 때문에 res[value] 값을 1을 증가 start : 2 / end : 2 # 👈 start = res[value] + 1, end = max(end:1, index-start+1:2) # index : 3 / value : r # 👈 for문의 n번째 index, value값 res : {'s': 0, 't': 2, 'r': 3} # 👈 res에 'r'가 key로 존재하지 않기 때문에 else구문이 작동되어 현재 index값을 value값으로 res에 추가 start : 2 / end : 2 # 👈 start = 2, end = max(end:2, index-start+1:2) # index : 4 / value : g # 👈 for문의 n번째 index, value값 res : {'s': 0, 't': 2, 'r': 3, 'g': 4} # 👈 res에 'g'가 key로 존재하지 않기 때문에 else구문이 작동되어 현재 index값을 value값으로 res에 추가 start : 2 / end : 3 # 👈 start = 2, end = max(end:2, index-start+1:3) # 3 # 👈 답
🤔 느낀점.
1. 문자열을 순회한다는 점에 사로잡혀 dict형을 생각지도 못했다. 그 결과로 for문을 2번 반복하는 참사를 발생시켰다.
2. 이미 존재하는지 아닌지의 체크 포인트가 들어간 문제를 마주할 때 dict형태를 고려해야겠다.
3. dict형은 일반적인 상황일 때 언제나 배열 보다 빠르기 때문이다.
4. enumerate를 문제상황에서 떠올리지 못햇다. 문법을 아는것과 문제해결에 활용하는 것에 큰 차이를 느꼈다. 사용하지 못하면 모르는 것과 같다.
