알고리즘 문제를 하나씩 풀어보고 있는데, 쉽게 생각했던 처음과 달리 접근하기 쉽지 않았다.
문제는 다음과 같다.
주어진 문자열에서, 중복되지 않은 알파벳으로 이루어진 제일 긴 단어의 길이를 반환하라.
ex)
str = "abcabcabc" => 3 ("abc")
str = "aaaaa" => 1 ("a")
str = "sttrg" => 3 ("trg")
문제만 봐서는 조금 헷갈렸는데, 예시를 보고 제대로 이해했다.
중복되지 않은 알파벳으로 이루어진 가장 긴 단어의 길이
= 중복되는 글자가 나오기 전까지의 단어 갯수를 리턴하라
이런 뜻인 거지.
고민하면서 작성했던 접근방법 세가지를 아래에 가져왔다.
if 만약 0번이 다음 1번과 다른가?:
yes>0+1이라는 temp변수에 저장
no>현재 temp변수의 길이를 리스트2에 저장
중복되는 글자가 몇개 있는지?
있는지 여부로 0번째 글자가 몇개 들어있는지
1.전체문자열리스트의 0번을 검증후리스트(아직빈)와 검증 같은게 있으면 stop
2.검증후리스트를 리셋하고 그 문자 or 그 다음문자부터 다시 시작여러 방법들을 고민하면서 어려웠던 것은, 먼저 한가지 for문을 구상해 봐도 그 다음에 for문이 와야 하는지, if문이 와야 하는지 등 어떻게 로직을 짜야 할지 첫걸음부터 헷갈렸기 때문이다.
그래서 먼저 리스트들을 정의했다.
a = [] # 빈 리스트 중복되지 않은 문자들을 저장
b = list(s) # 원본 문자열 리스트
c = [] # 리셋할 때 len을 저장하는 리스트음, 이렇게 작명하면 안 되겠지만 그렇게 했다.
-
a에는 중복되지 않은 문자들을 저장한다. 중복을 검사한 후 a에 삽입해 다음 문자를 검증하기 위한 것이다. 중복되는 문자가 나타난다면 이 a의 length를 가지고 가장 긴 문자열의 길이를 출력한다.
-
b는 변형하지 않을, 원본 문자열 리스트다. 사실 정의만 해두고 사용하지는 않았다. 그래도 리스트가 세개 필요하다는 사실을 주지한 채 접근하는 것이 도움이 될 것 같아 내버려 두었다.
-
c는 글자가 중복될 때 a의 length를 저장하기 위한 리스트다. 여기서 가장 큰 값을 리턴한다.
여기까지 작성한 후에는 조금 감이 잡혔다.
먼저 원본 문자열 리스트인 b를 가지고 검증을 시작해야 하니 for문을 작성했다. 그리고 a에 문자가 들어 있는지 검증하는 if문까지 작성할 수 있었다.
def get_len_of_str(s):
a = [] # 빈 리스트 중복되지 않은 문자들을 저장
b = list(s) # 원본 문자열 리스트
c = [] # 리셋할 때 len을 저장하는 리스트
for i in list(s):
if i in a:
elif i not in a:
a.append(i)예시를 가지고 돌려 보았다. "xyzzg"라는 문자열을 입력받는다고 가정해 보자.
-
먼저 for문의 i에 "x"가 들어오면, "x"가 리스트 a(=[ ])에 있는지 확인한다. a는 빈 리스트를 할당받았으므로 자연스럽게 elif로 넘어갈 것이다.
-
"x"가 들어있지 않으면 중복되지 않으니 리스트 a에 "x"를 저장한다.
-
다시 for문으로 돌아가서 2번째(인덱스 기준으로 1번째) 문자인 "y"가 i에 들어온다. "y"가 리스트 a(=["x"])에 있는지 검증한다. 없으니 elif로 넘어가 리스트 a에 "y"를 저장한다.
-
"z"가 for문의 i에 들어오면, 리스트 a(=["x", "y"])에 없으니 리스트 a에 "z"를 저장한다.
여기까지 하면 리스트는 아래와 같아진다.
a = ["x", "y", "z"] # 빈 리스트 중복되지 않은 문자들을 저장
b = ["x", "y", "z", "z", "g"] # 원본 문자열 리스트
c = [] # 리셋할 때 len을 저장하는 리스트이제 중복되는 값이 등장한다. "z"다. 고민하다가 이렇게 작성했다.
def get_len_of_str(s):
a = [] # 빈 리스트 중복되지 않은 문자들을 저장
b = list(s) # 원본 문자열 리스트
c = [] # 리셋할 때 len을 저장하는 리스트
for i in list(s):
if i in a:
c.append(len(a))
a = []
elif i not in a:
a.append(i)
return max(c)-
"z"가 들어오면 리스트 a에 "z"가 있는지 검증한다. 있다.
-
그러면 "z" 전까지의 문자열. 즉 현재 리스트 a에 들어있는 문자들. 즉 리스트 a의 length가 중복이 나오기 전까지의 가장 긴 문자열이 된다. 이 값을 리스트 c에 저장한다.
-
다시 중복이 나올 때까지 세어야 하므로 리스트 a를 빈 리스트로 리셋한다.
-
다음 값 "g"를 검증한다. "g"는 리스트 a에 들어있지 않으므로 elif에서 리스트 a에 "g"를 더한다.
-
끝까지 돌렸으니 리스트 c에서 가장 긴 값을 반환한다.
완성한 후 return값을 확인해 보니, 테스트의 절반을 겨우 통과했다.
문제들은 다음과 같았다.
- 중복되는 문자가 없는 경우 아무것도 c에 append하지 않아 0이 반환된다.
- 여러번 검증할 경우 마지막 문자열의 길이가 c에 append되지 않아 틀린 값이 반환된다.
- 전부 같은 문자일 경우(ex. "aaaaa") 0이 반환된다.
- 중복되는 값이 연속될 경우(ex."qweerty") 답이 "erty"니 4가 되어야 하는데 중복되는 값인 "e"가 검증 후 다음 for문으로 넘어가 "rty"만 계산되어 3이 반환된다.
이렇게 해결했다:
- 중복되는 문자가 없는 경우 아무것도 c에 append하지 않아 0이 반환된다.
- 여러번 검증할 경우 마지막 문자열의 길이가 c에 append되지 않아 틀린 값이 반환된다.
같은 결의 문제였기 때문에 for문을 다 돌린 후에 마지막 결과물인 리스트 a의 length를 리스트 c에 추가한다.
- 전부 같은 문자일 경우(ex. "aaaaa") 0이 반환된다.
리스트 a에 아무것도 저장되지 않고 끝나기 때문에 리스트 c에도 아무 데이터가 저장되지 않았다. c가 빈 리스트일 경우 1을 반환한다.
- 중복되는 값이 연속될 경우(ex."qweerty") 답이 "erty"니 4가 되어야 하는데 중복되는 값인 "e"가 검증 후 다음 for문으로 넘어가 "rty"만 계산되어 3이 반환된다.
이게 조금 어려웠는데, 검증한 후에 해당 문자를 리스트 a에 바로 할당함으로써 값을 유지할 수 있었다. 3번 문제도 이것으로 같이 해결된다.
결과물이다:
def get_len_of_str(s):
a = [] # 빈 리스트 중복되지 않은 문자들을 저장
b = list(s) # 원본 문자열 리스트
c = [] # 리셋할 때 len을 저장하는 리스트
for i in list(s):
if i in a:
c.append(len(a))
a = [i]
elif i not in a:
a.append(i)
c.append(len(a))
if c == []: # 3번 문제. 없어져도 되는 부분!
return 1
return max(c)
