본문 바로가기
반응형

python61

Linked List Cycle [leetcode] 코드 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: num_list = [] curr = head while True: if curr == None: return False if curr not in num_list: num_list.append(curr) curr = curr.next else: return True 문제 풀이 과정 설명 나는 지나는 모든 노드를 리스트에 저장한 뒤, 사이클이라면 리스트에 중복되는 노드가 분명.. 2022. 3. 9.
Arithmetic Slices [leetcode] 문제 https://leetcode.com/problems/arithmetic-slices/ Arithmetic Slices - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제풀이 아... 풀었는데 소 뒷걸음 치다 벌레 잡은 격이 느낌이다. 부분배열(contiguous subsequence of the array) 이 등차수열을 만족하는지 확인하고 맞다면 개수를 +1 해주는 문제였다. 부분배열을 검증하는 방법은 해당 배열의 모든 숫자와 등차수열 합공식에 넣은.. 2022. 3. 3.
다문서 요약 하기 (multi-document summarization) 요즘 요약에 관심이 있어서 관련 논문을 찾아 보던중 (취미로) ‘아 이건 나도 구현이 가능할 것 같은데?’ 싶은 논문이 있어서 정리해보려고 한다. 문서 하나에 대해 요약하는 건 블로그에 정리한게 있다. (물론 생성요약이 아니라 추출요약이다.) 요약은 크게 추출 요약 (extractive) 과 생성 요약 (abstractive) 으로 나뉜다. 오늘 해볼 건 추출요약 (extractive) 이다. 참고한 논문은 Clustering Sentences with Density Peaks for Multi-document Summarization 으로 비슷하게 주제의 기사들의 ‘문장’ 들 간의 밀집도를 바탕으로 중요한 문장을 ‘추출’ 한다. 이 논문에서는 중요도를 크게 3가지로 나누었는데, representativ.. 2022. 3. 1.
Remove K Digits [leetcode] 문제링크 문제 풀이 Input: num = "1432219", k = 3 Output: "1219" 첫번째 풀이 처음에는 앞 숫자와 뒤 숫자를 비교해서 뒤 숫자가 크면 해당 숫자를 지우는 로직인줄 알았다. 그럼 위 예시로 보면 1 : “4” 32219→ 4가 크므로 4를 지운다 ⇒ 132219 (k =2) 1 : “3” 2219→ 3이 크므로 3을 지운다 ⇒ 12219 (k=1) 1 : “2” 219→ 2가 크므로 2를 지운다 ⇒ 1219 (k=0 이므로 종료) 그럼 정답으로 1219 이므로 쉽게 푼줄 알았다. 하지만 반례로 Input: num = "12345", k = 2 Output: "123" 위 반례가 있다. 1 : 2 → 2가 크므로 2를 지운다 ⇒ 1345 (k=1) 1 : 3 → 3이 크므로.. 2022. 2. 19.
Swap Nodes in Pairs [leetcode] 문제 문제 풀이 정리 의외로 머리속에서 정리가 안되던 문제였다. 그림을 보면 알겠지만 짝수 일때만 자리를 바꿔줘야 한다. 하지만 List(배열) 이 아니고 Linked List 이기 때문에 인덱스로 접근할 수 없다. 그래서 even_flag를 만들어서 마치 짝수일때만 동작할 수 있도록 한다. 현재 위치가 짝수일 때와 홀수일 때 로직이 다른데 적어보자. 홀수일 때 현재 노드는 이전 노드로 지정한다. (prev = curr) 현재 위치를 다음 노드로 옮긴다.(혹은 지정한다.) (curr = curr.next) 짝수 플래그를 true로 변경한다. if even_flag == False: prev = curr curr = curr.next even_flag = True 짝수일 때 이전 노드의 next를 현재 노.. 2022. 2. 16.
쿼드압축 후 개수 세기 [프로그래머스] 문제링크 문제풀이 예전에 한번 문제만 봤던건데 예전과 달라진 점은 이제 그림을 보고 “오! 재귀함수로 풀면 금방 풀리겠다” 가 보이는 단계로 진화했다. 문제풀이 각이 보이니 얼른 풀었다. 입력으로 들어오는 arr 행렬을 4등분해서 갯수를 세면 되겠다 싶었다. 규칙으로는 arr 행렬 4등분 하기 arr 의 길이가 1 이라면 해당 배열의 숫자 그냥 반환하기 4등분 된 각 부분의 모든 숫자가 같다면 그 숫자 하나만 반환하기 (압축) 그렇게 제일 작은 부분부터 사분면 합치면서 재귀함수 빠져나오기 하나씩 구현해보자 arr 행렬 4등분하기 def slice_arr(arr, upDown, direction): temp_arr = [] slice_num = len(arr)//2 if upDown == "up": # 가.. 2022. 2. 14.
Subsets [leetcode] 문제 Subsets - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제풀이 문제 예시로 나온 답을 보고 풀게 되었다. Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 규칙이 보이는가? output 에 처음에는 [] (빈 리스트) 공집합 하나만 추가해준다. num = 1 일때, output 을 순회하면서 이전 집합에 1을 추가한다. (temp_list = [] + 1 = [1]).. 2022. 2. 13.
K-diff Pairs in an Array [leetcode] 문제 풀이 리스트 안 숫자들 중 차이의 절대값이 k를 만족하는 숫자 쌍 의 개수를 찾는 문제다. 한국말로 한문장 정리하니 “의” 로 연결된게 많아 국어지문 푸는것 같다. 다시 정리하자. 리스트 안 숫자들 중 ⇒ ex. [3,1,4,1,5] 차이의 절대 값 ⇒ ex. |3 - 1| = 2 k를 만족하는 숫자 쌍 count! ⇒ ex. |3-1| == 2 ? (count +1) : nothing! 문제를 보면 리스트의 중복된 숫자가 있어도 1개로 친다고 한다. 그럼 로직상 중복체크도 필요하다는 얘기다. 나는 이렇게 풀었다. 현재 비교할 숫자 = nums[i] 비교 당해야 할 숫자들 = nums[i+1:] (중복을 피하기 위해 i 번째 이후 숫자들만 사용) 중복을 피하기 위해 num_set 생성 ⇒ num_s.. 2022. 2. 9.
Find All Anagrams in a String [leetcode] 문제 https://leetcode.com/problems/find-all-anagrams-in-a-string/ Find All Anagrams in a String - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 풀이 설명 긴 문자열 (이하 s) 에서 짧은 문자열(이하 p)의 anagram(알파벳 순서를 바꾼 문자열) 을 찾는 문제이다. 해당 문자열이 s에서 발견될 경우, 발견된 위치를 전부 리턴하면 되는 문제이다. anagram은 문자의 순서를 바꿔.. 2022. 2. 2.
반응형

티스토리툴바