리트코드 239, 76, 77 문제 해설(파이썬 알고리즘 인터뷰)

 사실 내가 지금까지 푼 대부분의 리트코드 문제들은 파이썬 알고리즘 인터뷰라는 책에 소개된 문제들이다. 전에 코딩을 한 적은 있어도 코딩테스트를 준비해본 적은 없기에 당연한 말이지만 많은 나의 풀이가 그 책에서 배운 내용을 토대로 한다. 혹은 거의 똑같다. 그래도 이전에 내가 업로드 한 해설들은 다시 풀어보는 과정에서 책의 도움을 받지 않았던 해설들인데, 이번 문제들은 어렵기도 하고 공부겸 까먹지 않을 겸 올리는 거라 뭔가 양심상 옆에 괄호를 치고 책 이름을 적게 됐다.ㅋㅋㅋㅋ 

 

 문제를 시작하기에 앞서, 나중에 한번정도 따로 글을 파서 얘기할 것 같긴 한데, 정말 잘 나온 책이다. 특히 여기에 소개된 리트코드문제들이 너무 좋아서 리트코드를 조금 신뢰하게됐는데 내가 찾으려고 해보면 뭐랄까 괜찮은 문제가 별로 없다..ㅋㅋㅋㅋㅋㅋㅋ 괜찮은 문제들만 잘 추린 책이랄까. 아무튼, 우연히 괜찮아보여서 샀는데 정말 괜찮고... 코딩 초보자에게 강추한다. 물론 완전 기본적인 내용은 아니라서 파이썬 초보자보단 개발 경험은 있지만 코딩테스트 경험이 없는 사람에게 추천한다.

 

리트코드 239번 해설 링크 (파이썬 알고리즘 인터뷰 75번)

 

 숫자로 구성된 리스트가 잇는데, k만한 크기의 윈도우가 해당 리스트의 처음부터 끝까지 움직일 때 매 윈도우의 최댓값을 리스트로 만들어 반환하면 되는 문제이다. 뭔가 쉬워보인다. 투포인터와 슬라이싱을 적절히 활용하면 되는 문제이긴 하다. 책에서도 그런 풀이가 있긴한데 풀리진 않는다. 효율화를 시켜야 하고 효율화가 된 풀이도 책에 있긴 한데.. 그것도 리트코드에서 풀리지 않는다. 리트코드에 보면 엄청나게 긴 리스트가 예제로 추가된 듯 하고, 그 과정에서 여러차례 max를 계산하는게 시간상 효율적이지 않아서 풀리지 않는다. 그래서 매번 맥스값을 계산하지 않아도 되게끔 값들을 적당히 삭제해주는게 중요하다. 내 풀이는 새로운 값이 들어올 때마다 앞쪽 값보다 크면 앞쪽 값들을 삭제해버리는 방식이다. 그리고 인덱스가 저장된 큐를 만들어서 k윈도우를 벗어날 때마다 값을 제거해주면 된다. 나도 sohyunwriter님이 파이썬 알고리즘 인터뷰 깃허브 이슈에 올려둔 코드(링크)를 참고한건데 깔끔하게 책 내용을 바탕으로 잘 수정된 것 같다.

 

 

리트코드 76번 해설 링크 (파이썬 알고리즘 인터뷰 76번)

 

 s, t 두개의 문자열이 입력될 때 t문자열이 모두 포함돼있는 s의 가장 짧은 문자열을 반환하면 되는 문제이다. 투포인터를 하든, for문을 사용하든 s문자열에서 윈도우를 만들어서 해당 윈도우 안에 t문자열이 다 포함돼있나 계속 확인하는 수 밖에 없다. 주의할 점은 t문자열이 'aabc'라면 s의 부분문자열 안에 'abc'만 있어서는 안되고 'a' 2개와 'bc'가 있어야 한다. 따라서 매 윈도우마다 모든 문자가 있는지 확인하고 또 각 문자가 필요한 갯수만큼 있는지도 확인해야 한다. 사실 예외적인 ..상황을 제외하면 풀이가 정말 쉬운 문제인데 s = 'a', t = 'aa'라거나, s = 'a', t = 'b'같이 조금 예외적인 문제들을 고려하면 점점 깔끔하게 짜기가 어려워지는 문제이다. 나도 처음에 풀때 내 풀이에서 계속 좀씩 수정하다가 코드가 망해버렷던 기억이 있다.....ㅋㅋ  enumerate(s, 1)을 하면 s 문자열을 시작부터 둘러보면서도 예외적인 부분에서 인덱스를 깔끔하게 처리해줘서 코드가 우아해진다.(책의 표현을 빌림.ㅋㅋㅋㅋ)

 

리트코드 424번 해설 링크 (파이썬 알고리즘 인터뷰 77번)

 

 이 문제는 사실 파이썬 알고리즘 인터뷰 책의 영향을 받은 풀이이긴 하지만 이번에는 나 혼자 푼 문제이다. 이 문제의 아이디어는, 문자열에서 지금 내가 보는 윈도우에서 그 안에 가장 많이 존재하는 문자를 제외한 것들을 모두 바꾸면 된다는 것이다. 다시 말해서, (현재 윈도우의 길이 - 그 윈도우 내에서 가장 자주 등장하는 문자의 수 = k)를 만족하는 가장 긴 윈도우를 찾으면 된다. 나는 위 식의 왼쪽 값이 k보다 커진 경우마다(윈도우가 너무 커진 경우) 윈도우의 왼쪽 포인터를 옮겨서 조건을 만족시키게 하고 조건이 만족할 때마다 가장 긴 윈도우를 갱신했다. 책에서는 어차피 가장 긴걸 한번 찾으면 더 짧은건 탐색할 필요가 없기 때문에 (.. 맞긴해) max부분을 삭제해버렸다. 좋은 풀이이고 실제로 내 풀이는 리트코드에서 알려준 실행시간 부분에서 하위권을 기록했기때문에 위와 같은 방식으로 속도를 줄이는건 정말 좋은 방법인 것 같다. 필요한 것만 딱!

 

 

누군가가 만약 내 블로그에 들려서 풀이를 본다면 이게 무슨 풀이야... 라고 생각할 수 있겠지만 아이디어 정도는 그래도 참고할 수 있지 않나 싶다.