본문 바로가기

릿코드

264. Ugly Number II 1) Original Idea 1부터 하나씩 ugly number인지 확인 후, n번째 ugly number를 return 한다. : 시간이 너무 많이 걸림 & 중복연산이 너무 많음 -> 시간 초과 2) ugly number list를 저장해두고, 2, 3, 혹은 5로 나눠지는 경우(나머지가 0), 나눠진 몫이 ugly number 리스트에 있으면, 해당 number를 ugly number 리스트에 새로 추가해준다. 아니면 pass : 해야하는 나머지 연산, 나누기 연산이 너무 많음 -> 시간 초과 3) num을 1부터 확인하지 않고, sorted map을 이용해서, map 안에 있는 것 중 ct 번째로 큰 숫자를 가져온다. 그 숫자에 2, 3, 5를 곱한 결과를 map에 넣는다. 이를 n번 반복한다. .. 더보기
409. Longest Palindrome 1) Original 문자는 ascii 번호로 되어 있기 때문에 이를 저장할 해시맵 map[256] 을 준비한다. 그리고 각 문자가 몇개 나오는지 카운트한다. 또한 256 사이즈를 다 스캔하기에는 번거로울 수 있으니, key를 unordered set(동일한 키 추가 방지) 으로 저장해준다. (이건 이 문제의 경우, 알맞지 않은 방법이었다) 이제 카운트 숫자가 짝수인지 홀수인지 판단한다. 만약 짝수라면 그대로 더해주면 된다. 하지만 홀수라면, 그대로 더해주면 안된다. Palindrome은 단 한번의 홀수만 허용이 가능하다. 따라서 나는 이를 위해 sig라는 bool 을 만들었고, 한번만 허용가능한 홀수가 나왔을 때, sig를 false로 업데이트해준다. sig가 true일 경우 length에 홀수를 그대.. 더보기
121. Best Time to Buy and Sell Stock 1) Original : 기본 아이디어는 아래의 코드에서부터 시작된다. (이 코드를 돌리면 시간 초과가 뜬다) 1, 2, 3, 4 가 있다면, 1 vs max(2,3,4) = 4 - 1 2 vs max(3,4) = 4 - 2 3 vs max(4) = 4 - 3 결과 값들의 max를 MaxProfit으로 반환한다. 하지만 이 코드는 max를 구하는 과정(j loop)에서 겹치는 연산을 불필요하게 반복한다는 것을 볼 수 있다. 2) Optimization 1 : Max를 maxlist에 넣고, 새로운 원소가 추가될 때, maxlist[i+1] = max(maxlist[i] , prices[i+1]) 을 해준다. 여기서 max연산을 역순으로 해주어야해서, 실제로는 maxlist[i] = max(maxlist[.. 더보기
142. Linked List Cycle II 1) 오리지날 노드를 순환하면서, 포인터를 저장해준다. 방문한적 있는 pointer가 있다면 그 리스트를 반환. 아니면, nullptr 을 반환한다. 2) Floyed's Cycle detection Algorithm : 설명과 증명은 아래 티스토리 참고. https://fierycoding.tistory.com/45 플로이드의 토끼와 거북이 알고리즘(Floyd's Tortoise & Hare Algorithm) / 증명 / leetcode 287번 / 파이썬 발단 어느날 나의 유튜브 알고리즘에 뜬 JOMA... 사실 예전에도 한 번 본 적 있는 영상인데 그때는 킬킬킬 웃고 넘어갔지만 이제와서 다시 보니 알고리즘의 내용이 궁금해졌습니다. 결국엔 알아보 fierycoding.tistory.com 알고리즘 .. 더보기
876. Middle of the Linked List Solution 몇개인지 갯수를 세고, 그 갯수/2 만큼 head를 이동시켜서 return. 더보기
206. Reverse Linked List 주어진 LinkedList 를 Reverse 하는 문제. 복잡한 문제 같지만 천천히 생각해보면 그렇지 않다. 1) 첫번째 직관적인 솔루션 Prev라는 이전 노드를 저장하는 노드를 정의. 1 -> 2 -> 3 이라는 리스트가 있다면, Prev = nullptr 일때, head = 1 Prev = 1 일때, head = 2 Prev = 2 일때, head = 3 Prev = 3 일때, head = nullptr이 된다. 즉 새로운 Prev = head가 되고, 새로운 Prev의 next 는 Prev가 된다. 여기서 나는 tp라는 새로운 노드를 만들었고, tp 는 새로운 Prev 노드인데 이는, head->val의 값을 갖고 현재 prev를 next에 저장한다. 그리고 head 를 이동시켜준다. 이는 새로운 .. 더보기
21. Merge Two Sorted Lists Merged List를 만들고, 두 리스트의 첫 노드 값을 비교해가면서, 작은 것을 Merged linked list에 연결해준다. 만약 하나의 리스트가 비워졌다면 그대로 다른 리스트을 연결해준다. 더보기
392. Is Subsequence 이건 정말 설명할게 없어서, t 문자열을 스캔할 때, s 문자열에 대한 포인터를 유지하면서, 일치하는게 있으면 p ++ 아니면 t 문자열 인덱스로 넘어간다. 총 p의 갯수가 s 문자열의 길이와 같으면 subsequence 가 true 아니면 false 더보기

티스토리툴바