onlybooks/python-algorithm-interview

<파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트

python-algorithm-interview's Issues

P529 예제 1 출력

두 배열의 교집합을 구하는 부분인데요.
p529에서 예제 1의 출력이 [2]로 나와있던데 답이 [2, 2]로 나와야하는거 아닌가요??
굳이 set()에 넣어서 중복 요소를 없애는 이유가 있나요?? 오히려 교집합에대해서 혼란을 주는 것 같습니다.

typo report (p.282 && p.331)

// p.282
아래서 3 번째줄, "10개의 공간중" -> "9개의 공간중" 으로 바뀌어야 될거같습니다.

// p.331
두번째 예제 출력, "1" -> "3"

typo report(p.177)

소스코드 안에 # 두부분이 뒤바뀐것 같습니다~

typo p.161

p.161 슬라이딩 윈도우가 우측으로 이동하는 코드에서 expand(s, i , i + 1)로 표기되어 있습니다.
반면에 전체코드에서는 expand(i, i + 1)로 표기되어 있습니다.

expand가 정의된 것을 보면 expand(i, i + 1)이 맞는 것으로 보입니다. 감사합니다.

참고문헌 링크

매번 참고문헌의 글을 읽기 위해서 주소를 따라쳐야하는 번거로움이 있습니다.

약간의 편의를 위해서 참고문헌을 이 레포를 통해서 제공해주시면 (아니면 다른 방법이라도) 좋을 것 같습니다 ㅎㅎ

책은 너무 잘 읽고 있습니다. 감사합니다.

책에 대한 문의는 이곳에 공개 질문으로 등록해주시기 바랍니다.

책에 대한 문의는 많은 분에게 도움이 될 수 있도록 이곳에 공개 질문으로 등록해주시기 바랍니다.

담지 못하신 주제 관련

안녕하세요.
우선 이런 책을 내 주신 것에 대해 감사 말씀을 드립니다.
현업에 계신 분이 경험을 녹여 내에 많은 시간과 노력을 들이셨다는 것을 조금만 읽어도 느낄 수 있었습니다.

다름이 아니라 혹시 책에서 분량 문제 등의 제약 조건으로 인해 다루지 못했 던 주제가 있으셨다면, 어떤 것이 있으셨는지 궁금합니다.
다루는 주제가 알고리즘기법 자체로만 볼 때는 초급과 중급에 걸쳐있는 것 같습니다.
하지만 이번 K사 시험에서 구간트리가 나왔다는 등 중급 이상의 알고리즘이 실제 시험에서 사용되고 있는 상황인데,
혹시 담지 못하신 주제가 있다면 어떤 것들이 있을지, 또는 추후에 2편 계획이 있으신지 궁금합니다.

좋은 하루 되세요.

05. Group Anagram 결과 값 반환형

네, 그렇네요.
리트코드에서는 List[List[str]]를 요구하고 있는 만큼 제안해 주신 대로,

return list(anagrams.values())

로 처리하는게 맞겠습니다.
상세한 분석과 함께, 알려주셔서 감사합니다.
정오표 및 증쇄 시 반영하도록 하겠습니다.

감사합니다.

Originally posted by @likejazz in #16 (comment)

원래 코드가 맞습니다.

https://docs.python.org/3.8/library/collections.html#collections.defaultdict

defaultdict Examples
"When each key is encountered for the first time, it is not already in the mapping; so an entry is automatically created using the default_factory function which returns an empty list."

key와 매핑되는 value 자체가 리스트입니다.

Q 11. 자신을 제외한 배열의 곱 풀이 질문입니다.

오른쪽 곱셈을 할 때, range의 파라미터 중에서 0 - 1이 있는데, 왜 이렇게 작성하셨는지 궁금합니다!

-1로 작성해도 정상적으로 동작하던데, 의도를 파악하지 못해 질문남깁니다.

p = 1
for i in range(len(nums) -1, 0 - 1, -1): # 이 부분입니다.
    out[i] = out[i] * p
    p = p * nums[i]

p520 오타를 발견했습니다.

p520 풀이 4의 첫 번째 문장의
이진 검색을 사용하는 풀었지만,
->
이진 검색을 사용하여 풀었지만,
으로 수정해야 된다 생각합니다.

typo report(p.350)

위에서 6번째 줄

[책 내용] 이 경우 앞서 순열의 결과인 60에서 6을 나눈 6/60 = 10이 된다.

[수정] 이 경우 앞서 순열의 결과인 60에서 6을 나눈 60/6 = 10이 된다.

분모와 분자를 바꾸어야 합니다.

설명도 쉽게 되어있고 다양한 각도에서 접근한 코드를 보며 책 재미있게 보고 있습니다. 감사합니다!

AI 분야 책을 쓰실 예정은 없으신가요?? 기대됩니다!

101쪽 비문 수정

리스트에서 최댓값 또는최솟값 경우가
-> 리스트에서 최댓값 또는 최솟값을 찾는 경우가
로 수정해야 더 자연스러울 것 같네요

28번문제. 해시맵 디자인

깃허브에 올라와 있는 28번 해시맵 디자인의 풀이코드에 ListNode정의하는 부분이 잘못 올라 온 것같습니다.
class ListNode:
def init(self, x):
self.val = x
self.next = None

책내용>>
class ListNode:
def init(self, key=None, value=None):
self.key = key
self.value = value
self.next = None

P450

_percolate_up 구현하는 코드 중

while parent >= 0: 이 맞나요??

items[0]이 None인데... 실행해봐도 안되요

제가 잘못 이해한건가요?

219쪽 reverse(head) 오류나는데 확인해주실수있나요?

219쪽 reverse(head) 오류나는데 확인해주실수있나요?
reverse 함수는 인자 2개 받는 함수로 구성했는데 왜 head 하나만 들어가는지도 모르겠습니다.

p.593 시간복잡도 관련 질문입니다.

우선 책의 코드인 while heap 부분을 보면 heap에서 하나씩 뺀걸 insert 함수를 이용하는데 제가 알기로 insert함수는 O(N)의 시간복잡도를 가지고 있으므로 결국 O(N^2)인데

아래는 제가 짠 코드입니다. 저 같은 경우는 정렬 후에 최소값부터 미리 만들어진 리스트에 넣는 식으로 구현하였습니다.
책에서는 heap을 빈 리스트로 선언하고 채워 나가는 식이고 저는 people의 length만큼 -1로 초기화 한 후에 집어 넣는식으로 구현하였습니다.
제가 짠 코드도 결국 O(N^2)이지만 책의 코드 같은 경우는 빈 리스트부터 채워나가니 중간중간 리스트의 적재율이 넘어가면 더 큰 리스트로 바뀌는 오버헤드도 있을거라 제가 짠게 더 빠를거라 생각하였는데
채점을 해보면 제가 짠 코드가 훨씬 느리게 나오는데 이유를 모르겠어서 질문드립니다..
혹시 insert함수도 내부적으로 최적화 같은게 되어있는건가요??

제 코드에 대해 추가 설명을 하자면 최소값부터 정렬이 되있으니 [-1,-1,-1,-1,-1 ..] 이 있을 때 최소값이 (4,4)면 그 앞에 4칸을 비우고 5번째 칸에 (4,4)를 넣고 그 다음 값이 (5,5)면 5칸을 비워놓고 (5,5)를 채우는.. 그런 알고리즘입니다.

    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        answer = [-1] * len(people)
        people.sort()
        
        for j in range(len(people)):
            h, k = people[j]
            for i in range(len(answer)):
                if j == len(answer)-1 and answer[i] == -1:
                    answer[i] = people[j]
                    break
                if k == 0 and answer[i] == -1:
                    answer[i] = people[j]
                    break
                    
                if answer[i] == -1 or answer[i][0] == h:   # answer[i][0] == h 는 앞에 숫자들이 같은경우 대비
                    k -= 1
                else:
                    continue
        
        return answer

Group Anagram 문제의 잘못된 반환형

안녕하세요. 초판 1쇄 기준으로 153페이지의 그룹 애너그램 문제에 대한 반환형이 잘못되어 이슈 등록합니다.

TL;DR

그룹 애너그램 문제에서는 반환형에 대한 타입 힌팅을 List[List[str]] 로 명시하고 있습니다. 하지만 책의 풀이에서는 view 객체를 반환하고 있습니다. view 객체와 list 객체는 서로 다른 객체이기 때문에

return anagrams.values()

대신

return list(anagrams.values())

리스트 타입으로 변환한 뒤 리턴하는 것이 올바르다 생각합니다.

이유

1. view 객체와 list 객체는 ==연산자에 의한 비교가 성립하지 않습니다.

>>> a = [1, 2, 3]
>>> b = {1: 1, 2: 2, 3: 3}
>>> a == b.values()
False
>>> b.values() == a
False
>>> list(b.values()) == a
True

2. view 객체는 원본 딕셔너리에 대한 연결이 유지됩니다.

# view
>>> a = {1: 1, 2: 2}
>>> view = a.values()
>>> view
dict_values([1, 2])
>>> a[1] = 2
>>> view
dict_values([2, 2])

# list
>>> a = {1: 1, 2: 2}
>>> no_view = list(a.values())
no_view
[1, 2]
>>> a[1] = 2
>>> no_view
[1, 2]

결론

현재는 leetcode에서 view 객체를 반환해도 문제가 없습니다. 다만, 추후 오답으로 바뀐다거나 타 플랫폼에서는 오답으로 채점할 가능성을 배제할 수 없기 때문에 올바른 타입으로 반환해야한다고 생각합니다. 감사합니다.

알고리즘 공부 방법에 대한 문의

안녕하세요.
책에 설명된 알고리즘 문제들을 차근차근 이해하려고 노력하며 공부하고 있습니다.
책에 소개된 문제의 코드를 직접 실행해보고 디버깅해가며 공부하고 있는데, 바보 같은 질문일 수도 있지만, 문득 드는 생각이.. 이렇게 다른 사람이 고안해낸 풀이법을 이해하며 습득하면 저도 그분들 처럼 알고리즘에 대한 풀이법을 생각해낼 수 있는 문제해결능력이 향상될 수 있는지 궁금해서 이렇게 질문드립니다. (단순히 풀이법을 따라하게 되는 것이 아닌) 알고리즘 쪽은 어떤식으로 공부해나아가야 좋을지 잘 모르겠네요.. 그냥 이렇게 책의 설명과 코드를 이해하면서 공부하는게 잘하고 있는 것일까요?

감사합니다.

객체의 메소드에 관한 질문드립니다!

안녕하세요! 1번 2번 문제를 풀면서 궁금한 점이 생겨 질문드립니다.

1번 문제를 풀다가 str 타입의 객체는 .lower() 같은 메소드를 사용했을 때 원본이 변하지 않는 것을 확인했고
2번 문제를 풀다가 list 타입의 객체에서는 .reverse()를 사용했을 때 원본이 변하는 것을 확인했습니다.

이렇게 객체의 메소드를 호출했을 때 원본이 변하냐 변하지 않느냐는 mutable / immutable 차이 때문에 발생하는 건가요?

56page 에 오타가 있어요

사소한 거긴 하지만..
루프문 java 예시에 닫힘 중괄호(})가 빠져있습니다.

p.222, 223 타입 힌트 질문 드립니다.

안녕하세요 선생님의 책으로 열심히 공부하고 있는 학생입니다.
공부를 하다보니 p.222, 223 함수의 타입 힌트에 의문이 생겨 질문 드립니다.

    # 연결 리스트를 파이썬 리스트로 변환
    def toList(self, node: ListNode) -> ListNode:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list


    # 파이썬 리스트를 연결 리스트로 변환
    def toReversedLinkedList(self, result: ListNode) -> ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node

        return node

위 toList 함수는 타입 힌트에서 반환형이 ListNode로 명시되어 있는데 내부 list의 선언과 설명을 보니 List인 것 같고,
아래 toReversedLinkedList 함수의 인자인 result는 str로 타입 힌트를 하는 게 맞지 않나라는 의문이 들었습니다.
그래서 파이썬의 타입 힌트에 대해 찾아보니 타입힌트는 IDE나 정적 검사기에서 오류를 탐지하는데 도울 뿐 런타임에는 영향을 미치지 못한다는 것을 보았습니다. 실제로 리트코드에서 제가 생각한 것과 원래 코드 모두 정상적으로 정답으로 인정되어 제가 생각한 것이 틀린 것인지 그렇다면 왜 그런 것인지 궁금하여 질문 남깁니다. 감사합니다.

재귀에 관한 질문입니다.

책에 재귀로 푼 코드를 보면 설명란 종종 재귀가 간단하고 우아한 코드라고 나옵니다.
그런데 인터넷에 보면 실무에서는 재귀는 코드를 작성한 사람만 편해서 잘 안쓰인다고 그러던데
사실인가요? 물론 이진트리 같은 경우야 당연히 재귀가 쓰이지만 그외에 고급?알고리즘 등을 짤 때 실무에서도 재귀가 빈번하게 사용되는지 학생입장에서 궁금합니다.

640쪽 그림23-9에 오류가 있는것 같습니다.

계단 오르기 문제 브루트포스 그림 23-9 루트 밑 노드가
n계단->n-1계단, n-1계단이 아니라 n계단-> n-1계단, n-2계단으로 나누어져야 될것 같습니다.

좋은 책 써주셔서 감사합니다.

p502 오타가 있는 것 같습니다.

p502 풀이 2의 3번째 문단 2번째 줄에 '만약 다음번 head도 cur보다 작은 상태라면 굳이 되돌아가지 않아도 되지 않을까?' 와 해당 문단의 마지막 2번째 줄에는 '되돌아가는 경우는 cur가 head보다 클 때만 하면 될 것 같다.' 이 두 문장은 if head.val < cur.val 의 조건에서 되돌아가지 않는다 와 되돌아간다 두 가지를 모두 지칭하고 있어 오타라고 생각합니다.

p.307 문제 확인바랍니다.

교재에는 "k번 이상 등장하는 요소를 추출하라." 라고 되어있습니다.
하지만 leet코드 347번의 문제의 번역과 교재의 예제코드를 보면 "많이 등장하는 순서대로 k개 추출하라."가 맞지 않을까요?

7번 문제 두 수의 합 3번 풀이 질문

해답코드중 마지막 두줄
if target - num in nums_map and i != nums_map[target - num]:
return nums.index(num), nums_map[target_num] 에서

저는 코드를 이렇게 작성한 이유는 값이 같은 두 수의 합이 정답이어서 딕셔너리에서 첫번째 숫자의 인덱스가 두번째 숫자의 인덱스로 덮어씌일을 때를 고려해서 짠 코드라고 이해했는데요,
볼드처리한 nums.index(num)은 굳이 index함수를 사용한 이유를 잘 모르겠습니다.

index값이 왼쪽부터 값을 찾아주기 때문에 첫번째 값의 인덱스를 리턴해서 index함수를 사용한 건가요??
그렇다면 그냥 nums.index(num) 대신 i를 사용하면 되지 않나요?
코드를 return i, nums_map[target_num] 로 바꿨을 때도 문제없이 동작해서 index 함수를 사용한 의도가 궁금해서 질문 드립니다.

코딩테스트 문의

안녕하세요.
일단 좋은 책 써주셔서 감사하게 읽고있습니다.
읽다보니 조금 잘못된 정보가 있는것 같아 여기에 문의 남김니다.

p44 경우, 삼성전자는 자체 플랫폼을 이용하지만, 상시테스트, 역량테스트(공채) 의 경우 python으로 풀이가 가능합니다.
또한 SWEA에서도 python으로 풀이가 가능한 문제들이 있으며, 상시테스트 같은경우 A형 B형 C형 등급이 나뉘게 되는데 A형의 경우 python이 가능하고 B형 C형 같은 경우가 python 이 불가능합니다. 혹시나 오해할 경우가 생길것 같아 이렇게 글 남김니다.

16장 트라이 473쪽 질문있습니다.

단업 삽입 부분 코드에서 node.val = char 라는 부분이 있습니다. 그런데 트라이를 저장할 노드 부분에서는 val을 정의하고 있지 않아 의문이 들었습니다. 그래서 제가 직접 node.val = char 부분을 제거하고 실행한 결과 오류없이 잘 실행되는 것도 확인했습니다.
혹시나 제가 놓친 부분이 있는지 있다면 어떤 부분인지 설명을 듣고 싶어서 글을 남겼습니다.

88번 집 도둑 코드에 대해 문의드립니다.

타뷸레이션을 활용한 두 번째 풀이가 leetcode에서 KeyError :0 에러를 발생시키고 동작이 되지 않습니다.

leetcode 동영상과 "파이썬 알고리즘 인터뷰" 에 사용된 코드의 관계 목록

leetcode 동영상에서 설명되는 코드(문제)가 책의 어디에서 사용되었는가를 보여주는 "찾아보기"(index)는 혹시 제공되지 않나요?

p.175 오타는 아니지만..

for i, num in enumerate(nums):
if target-num in nums_map and i != nums_m-nuap[target-num]:
return nums.index(num), nums_map[target-num]

여기서 마지막 부분인 nums.index(num)는 그냥 i로 해도 되지않나요? 이게 좀 더 가독성이 좋지않나 싶어서.. ㅎㅎ

가장 긴 펠린드롬 문제 질문입니다.

expand 함수를 보면 while 조건문에서 right <= len(s) and s[left] == s[right-1] 이렇게 되어있는데
right < len(s) and s[left] == s[right]이 맞지 않나요?

제가 곰곰히 생각해본 결과 right <= len(s)에서 = 이 붙은 이유는 for i in range(len(s)-1) 구문에서 마지막 i에서 i+2를 하면 인덱스 에러 문제 때문에 그런거같긴한데 저건 그렇다쳐도 s[left] == s[right-1]은 이해가 되지 않습니다.
저렇게하면 2칸짜리 포인터 기준으로 i랑 i+1이 같은지를 비교하는게 아니고 그냥 i랑 i가 같은지 비교하게 되는거 아닌가요?

또 return s[left+1:right-1] 부분도 그냥 제가 생각하기에는 return s[left+1:right]이 맞는거같은데
책에 있는 코드로 leetcoe로 제출했을때 잘되는걸보면 제가 이해하지 못한 부분이 있는 것 같은데 전체적으로 설명좀 해주시면 감사하겠습니다.

그리고 이건 여담이지만 책을보면 중간중간 go로 작성된 코드가 보여서 go에 관심있고 열심히 배우고 있는 대학생으로써 질문하나만 여쭙자면 현재 한국에서 경력말고 신입개발자로써도 golang을 잘 다루게되면 경쟁력이 있을까요? golang에 대해 어떻게 생각하시는지 궁금합니다!

코딩 테스트에 대한 질문

안녕하세요,

유익하고 알찬 책을 이렇게 접할 수 있게 애써 주셔서 감사드립니다. <파이썬 알고리즘 인터뷰>를 열심히

소화 중입니다. 책에 나오는 주 대상 언어는 아니어도 코딩 테스트 관련 대비 내용이 있으므로 SQL 코딩 테스트에

대해서도 질문 드려도 될까요? 실시하는 회사마다 난이도가 천차만별일 수 있지만, 그래도 어느 정도 보편적인 범위의

난이도라는 건 존재한다고 생각합니다. 어떤 테이블이 주어졌을 때

1시간 안에 5~6개 문제 정도의 쿼리를 제출해야 하는 SQL 테스트 진행 방식이라면,

난이도를 어느 정도로 생각하고 준비하면 통과 확률을 최대한 높일 수 있을까요? (제출 후 제출 코드에 대한 리뷰 인터뷰도 진행)

SQL 전문 개발자 포지션은 아니고 데이터 사이언스나 데이터 분석 포지션인 경우입니다.

좀 고리타분한 시각인지 몰라도 사실 "SQL이 코딩 테스트를 할 만한 언어인가?"라는

(더 근본적으로는 SQL도 'L'이 있다고 해도 (프로그래밍) 언어는 언어이긴 한가 하는) 느낌도 있습니다만 요즘

SQL만으로 코딩 테스트를 진행하는 비중도 꽤 늘어나고 있는 추세 같습니다. 떠올려 보실 수 있는 팁 다양하게

공유될 수 있으면 정말 도움이 되고 감사하겠습니다. 실무에서 꽤 써 본 경험은 있지만(개발자나 관리자는 아니라 DML 위주로)

막상 테스팅 환경을 접해야 한다고 하니 상당히 부담이 가중됩니다.

다소 막연한 질문 같기도 한데, 그래도 압박감이 커지고 답답해서 올리니 도움 말씀 미리 진심으로 감사드립니다.

오타 확인 부탁드립니다.

p152

line 7
return max(counts , key=count.get)

->
return max(counts, key=counts.get)

딕셔너리 객체의 변수명이 오타난것 같습니다.

코딩 테스트에 대한 문의

안녕하세요,

유익하고 알찬 책을 이렇게 접할 수 있게 애써 주셔서 감사드립니다. <파이썬 알고리즘 인터뷰>를 열심히

소화 중입니다. 책에 나오는 주 대상 언어는 아니어도 코딩 테스트 관련 대비 내용이 있으므로 SQL 코딩 테스트에

대해서도 질문 드려도 될까요? 실시하는 회사마다 난이도가 천차만별일 수 있지만, 그래도 어느 정도 보편적인 범위의

난이도라는 건 존재한다고 생각합니다. 어떤 테이블이 주어졌을 때

1시간 안에 5~6개 문제 정도의 쿼리를 제출해야 하는 SQL 테스트 진행 방식이라면,

난이도를 어느 정도로 생각하고 준비하면 통과 확률을 최대한 높일 수 있을까요? (제출 후 제출 코드에 대한 리뷰 인터뷰도 진행)

SQL 전문 개발자 포지션은 아니고 데이터 사이언스나 데이터 분석 포지션인 경우입니다.

좀 고리타분한 시각인지 몰라도 사실 "SQL이 코딩 테스트를 할 만한 언어인가?"라는

(더 근본적으로는 SQL도 'L'이 있다고 해도 (프로그래밍) 언어는 언어이긴 한가 하는) 느낌도 있습니다만 요즘

SQL만으로 코딩 테스트를 진행하는 비중도 꽤 늘어나고 있는 추세 같습니다. 떠올려 보실 수 있는 팁 다양하게

공유될 수 있으면 정말 도움이 되고 감사하겠습니다. 실무에서 꽤 써 본 경험은 있지만(개발자나 관리자는 아니라 DML 위주로)

막상 테스팅 환경을 접해야 한다고 하니 상당히 부담이 가중됩니다.

다소 막연한 질문 같기도 한데, 그래도 압박감이 커지고 답답해서 올리니 도움 말씀 미리 진심으로 감사드립니다.

문제 14번 "두 정렬 리스트의 병합" 질문 있습니다.

안녕하세요, 파이썬 알고리즘 인터뷰 책으로 공부하고 있는 학생입니다.

풀이 1의 해설을 보면 "풀이가 명확하고 코드도 길지 않다." 라고 써있는데, 조건문의 조건들이 왜 저렇게 구성이 되었는지 전혀 감이 오지 않아서요...

구글링을 통해서 아래 코드를 활용하여 이해하기는 했지만, 책 저자님의 소스코드도 이해하고 싶어서 글 남깁니다.

감사합니다.

*구글링한 코드: https://rottk.tistory.com/entry/21-Merge-Two-Sorted-Lists

class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None :
return l2

    if l2 is None :
        return l1

    if (l1.val > l2.val) :
        head = ListNode(l2.val)
        head.next = self.mergeTwoLists(l1, l2.next)
    else :
        head = ListNode(l1.val)
        head.next = self.mergeTwoLists(l1.next, l2)

    return head

3sum 문제 최적화 관련 질문입니다.

우선 이 질문은 책의 오류나 오타 등에 관한 질문이 아니라서 해도되는건지 잘 모르겠습니다.
만약 안되는거라면 확인 후에 삭제하겠습니다.

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []

    nums.sort()
    res = []
    for i in range(len(nums)-2):
    if i > 0 and nums[i] == nums[i-1]:
            continue
        left, right = i+1, len(nums)-1
        while left < right:
            tot = nums[i]+nums[left]+nums[right]
            if tot == 0 and sorted([nums[i], nums[left], nums[right]]) not in res:
                res.append(sorted([nums[i], nums[left], nums[right]]))
                left += 1
                right -= 1
            elif tot < 0:
                left += 1
            elif tot > 0:
                right -= 1
            else: # tot이 0이고 res에 이미 중복된 배열이 있을 때 무한루프를 방지하기위함
                left += 1
                right -= 1
    return res

이건 제가 구현한 풀이이고 릿코드에 제출하면 time limit이 나오는데 제가 봤을 때 시간복잡도가 책이랑 차이가 왜 많이 나는지
잘 모르겠는데 이유를 알 수 있을까요? 파이참에서 오류 케이스를 돌려본 결과 답이 나오긴하는걸보면 알고리즘은 맞는거같은데 어떤거때매 시간복잡도 차이가 많이 나는건지 잘 모르겠습니다.

P613

p613의 그림 22-4에서 1,2 1,3 1,4 1,5 라고 되어있는데요.
지문에서는 [1,2,1,3,1,4,1,1]이라고 되어있습니다.
그렇다면 1,5가 1,1 이 되어야되는거 아닌가요??

p232 그림 8-6 재귀로 스왑하는 구조

안녕하세요. 수고 많으십니다.
페어의 노드 스왑문제에서 제가 그림을 그려봤을 때는 두 번째 재귀에서 반환할 때 return p로 4를 반환하게 되어서 그림의 1) 쪽에 1이 4를 가리켜야 되는 거 같은데 맞을까요??

Typo report (p.185)

p.185
큰 문제는 아니지만 전체코드 함수 정의 def에서 d가 빠져있습니다.

좋은 책 잘 읽고 있습니다.

P549 오타있습니다.

p549에 마지막 OR연산 결과를 보여주는 곳에
5 & -4
->
5 | -4
로 바꿔야 할 것 같습니다.

typo report (p. 292)

// p.292
두번째 paragraph, "삭제 emove()" -> "삭제 remove()"

혹시 p163 오타가 맞을까요??

163p 밑에서 3번째 줄 128 이하가 아닌 127 이하라고 생각하는데 맞나요??

오탈자 제보입니다. p.211입니다.

파이썬에서는 원시 타입(Primitive Types)이 존재하지 않는다.

않다.를 않는다로 고치는 것이 좋을 것 같습니다.

책 잘 읽고 있습니다. 감사합니다!

75번 문제 : 최대슬라이딩 윈도우 - 큐를 통한 최적화에 대한 반례

안녕하세요, 책을 통해 공부하던 중 20장의 75번 큐를 위한 최적화에 대해 질문이 있어 메시지 드립니다.

최댓값이 윈도우에서 빠지면 current_max 를 -inf 로 초기화하고 current_max 가 -inf 인 경우에는 window 에서 max 값을 구해 current_max 를 구하게 되는데요, 이렇게 되면 입력배열이 [1억, 99999999, 99999998...1] 이 주어지는 경우에 매번 새로 max 값을 구해야해서 비효율적이지 않나 하는 의문이 들어 메시지 드립니다. 코드가 이 경우를 어떻게 커버하는 것일까요?

유명한 문제이고, 많은 사람들의 감수를 거친 책의 풀이가 틀렸을 리가 없겠다는 생각이 들지만 질문하면서 저한테 깨달음이 있지 않을까 하는 마음에 메시지 드립니다!

다시 한 번 좋은 책 집필해주셔서 감사합니다~

입력값 처리

안녕하세요 책을 재미있게 공부하고 있는 학생입니다. 책의 코드를 공부하다보니 입력과 출력에서 input()을 이용하지 않고 함수를 통한 풀이에 의문을 갖게 되었습니다. 리트코드에 들어가서 다른 분들의 풀이를 보니 거의 다 함수를 이용해서 풀이하셨더군요 코딩 테스트 때도 입력이라는 단어에 크게 의미를 두지 않고 함수로 풀이해도 되는 건가요?

Originally posted by @chanmin01 in #2 (comment)

P.146 에서 질문 드립니다.

안녕하세요.

P.146에서
s[:] = s[::-1] 코드는 파이참에서 아래와 같은 error가 발생하는데,
리트코드에서는 사용 가능하다고 말씀하신 것으로 이해하였습니다.

이건 리트코드의 문제인지,
아니면 python 관련하여 제가 모르는 부분에 의해 발생하는 차이인지 문의 드립니다.

Traceback (most recent call last):
File "C:/Users/User/PycharmProjects/pythonProject/main.py", line 21, in
s[:] = s[::-1]
TypeError: 'str' object does not support item assignment

감사합니다.

문제를 풀었는데, 책과 달라요

그런데, 본질적으로 책과 같은데, 방식만 다른건지, 문제가 있는 코드인지도 여기 올리면 봐주시나요..?
( 리트코드에 잘 제출됩니다. )

빗물 트래핑 문제입니다.

다음 코드는 제가 작성한 코드입니다.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: 
            return 0 

        volume = 0 # 빗물의 양
        max_height_index = height.index(max(height)) # 가장 높은 블럭의 위치
        left_height = height[:max_height_index+1]  # 가장 높은 블럭 좌측 구간
        right_height = list(reversed(height[max_height_index:])) # 가장 높은 블럭 우측 구간 반전

        left, right = 0, 1
        while right < len(left_height): 
            if left_height[left] > left_height[right]: 
                volume += left_height[left] - left_height[right] 
                right += 1 
            else: 
                left, right = right, right + 1  


        left, right = 0, 1
        while right < len(right_height):
            if right_height[left] > right_height[right]: 
                volume += right_height[left] - right_height[right] 
                right += 1 
            else:
                left, right = right, right + 1 
            
        return volume 

35번 "조합" 문제에 관해 질문드립니다.

안녕하세요, 좋은 서적 출판해주셔서 정말 감사드립니다.

35번 풀이 1에 대한 질문이 있습니다.
아래 코드에서 k == 0 이 될 때, return 으로 백트래킹을 해야,
search space가 줄어들어 연산량이 조금이라도 줄지 않을까 해서 질문드립니다.
(return 하지 않을시 순열과 동일한 연산량..?)
혹시, 제가 생각하지 못한 오류 부분이 있는지 궁금합니다.
물론 35번 풀이 2 의 itertools 모듈을 활용하는 것보다는 느리지만
기존의 풀이 1 보다는 빠른 것 같아서요.

읽어주셔서 감사합니다.

from typing import List


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        results = []

        def dfs(elements, start: int, k: int):
            if k == 0:
                results.append(elements[:])
                # k개 찾은 후 백트래킹 (아래 for문 실행 막음)
                return

            # 자신 이전의 모든 값을 고정하여 재귀 호출
            for i in range(start, n + 1):
                elements.append(i)
                dfs(elements, i + 1, k - 1)
                elements.pop()

        dfs([], 1, k)
        return results

P174. 풀이 2 반환형

P173의 "두 수의 합" 문제의 리트코드에서 제시하는 함수의 반환형은 List[int] 입니다.

하지만 해당 문제의 풀이2, 풀이3, 풀이 5들은 다음과 같이 Tuple[int] 를 반환하고 있습니다.

# 풀이 2
return nums.index(n), nums[i+1:].index(complement) + (i+1)
# 풀이 3
return nums.index(num), nums_map[target - num]
# 풀이 5
return left, right

풀이 1, 풀이4의 경우는 리트코드에서 제시하는 바와 같이 List[int] 을 반환하고 있습니다.

# 풀이1
return [i, j]
# 풀이 4
return [nums_map[target - num], i]

이전에 올라왔던 이슈 중 그룹 애너그램 문제과 동일한 이슈인 것 같습니다.

이 문제 말고도 일부 문제에서 List를 요구하는데 Tuple을 반환하는 경우가 빈번한 것 같습니다.

큰 문제는 아니지만, 리트코드가 제시하는 타입에 맞추는 것이 책의 전체 일관성이나,

제출에도 좋은 것 같아서 이슈를 작성하여 봅니다.