고양이발일기

Problem Solving Process i와 j라는 two pointers를 만든 후, (i는 최소값, j는 최댓값을 구분하기 위함이다) i = 0, j = 1 루프를 돌며 j - i 값의 차이를 구한 후, 해당 값이 max 인지를 검사한다. 또한 i 의 값이 j보다 큰 경우는 ( = 진행 하다 최소값이 나온 경우) i의 포인터를 j로 바꿔준다. j가 prices를 다 돌면 루프를 종료하고 max값을 리턴한다. Solution class Solution: def maxProfit(self, prices: List[int]) -> int: i = 0 j = 1 length = len(prices) max_price = 0 while j < length: diff = prices[j] - prices[i..

Problem Solving Process 우선 array를 sort 한 후, k 만큼의 array를 만든 후에 내부의 max - min 값을 추출하는 일이므로 arr[i+k-1] - arr[i] 값을 계산하며 minimum 값을 추출해냈다! sorting 하면 쉽게 풀리는 알고리즘 이었다. Solution def maxMin(k, arr): arr.sort() minimum = sys.maxsize length = len(arr) for i in range(length - k + 1): minimum = min(minimum, arr[i+k-1] - arr[i]) return minimum

Problem Solving Process 이 문제는 결국 내 힘으로는 못 풀었던 문제이다... ㅠㅡㅠ 약 두시간 동안 고민했으나 에러만 잔뜩 맞이하고 결국 답을 참조했던 문제 푸는 방법은 1. 각 노드의 값을 dict, set 등에 저장 한 후 중복을 검사 2. two pointers를 사용해 돌면서 나아가는 방식 둘의 시간 복잡도는 O(n)으로 같지만 공간복잡도는 1. O(n) 2.O(1)으로 두번째 방법이 제일 효율적이다. Solution class Solution: # O(n) time and O(n) space def detectCycle(self, head: ListNode) -> ListNode: dictionary = collections.defaultdict(ListNode) #or ca..

Problem Solving Process 일단 든 생각은 절반으로 나눈 후, 알파벳 순으로 정렬을 해서 인덱스마다 다르면 카운트를 세주자! 였는데, 그렇게 하면 동일 알파벳 갯수가 여러개인 경우가 있으니, 불가능했다. 그래서 생각해낸 방법은 절반으로 나누어 s1, s2를 만들어서 s1 루프를 돌며 해당 항목이 s2에 있는지 확인하고 s1, s2에 있는 항목을 둘다 제거해주는 방법이다. 하지만,, list로 진행하다보니 time exceeded가 나는 것이어따... 그래서 list 보다 시간 복잡도를 줄일 수 있는 deque를 활용하여 풀어주었다! 확실히 remove 시간이 많이 줄은 것 같다. ( list - O(N) , deque - O(1) ) + 하지만 역시 고수들의 답은 또 달랐다. python..

Problem Solving Process 내가 푼 방법 1. head를 돌며 head 의 전체 length를 구해준다 2. head_length // 2 하여 중간 인덱스 값을 구한다. 3. head를 돌며 중간 인덱스 값 부터 return 한다. 하지만 .... 다른 풀이를 보니 더 천재적인 방법이 있었다. 투 포인터를 사용하여 P2와 P2.next 가 존재하는 동안 루프를 돌며 P1은 한칸씩 나아가고 (P1.next) P2은 두칸씩 나아간다 (P2.next.next) 그렇게 해서 P2 혹은 P2.next가 None이 될 때 까지 나아가면 P1의 값은 middle값이 된다. (전체의 절반이 middle값이므로) 보면서 정말 감탄했다 ㅋㅋㅋㅋㅋㅋ 대단한ㅅ ㅏ람들이야 ... ( •̀ ω •́ )✧ Sol..

Problem Solving Process 우선 문장에 기호가 섞여있기 때문에 1. 알파벳인지 구분을 해준다 2. rotate 되는 숫자(k)가 알파벳의 갯수 26개 이상으로 돌 수 있으니 나머지 값을 계산하여 더해준다. 3. 대소문자를 구분하여 아스키 코드의 min, max 값을 지정한다. 4. max 값을 넘으면 26을 빼준다. 이런식으로 풀었는데 2, 4번을 합쳐서 더한 후, 한 번에 26을 나눠 나머지값을 구하는 형식으로 푸는게 더 깔끔할 것 같다. Solution def caesarCipher(s, k): answer = '' for i in s: if i.isalpha(): k %= 26 rot = ord(i) + k (min, max) = (65, 90) if i.isupper() else ..