본문 바로가기
반응형

algorithm82

Score of Parentheses [leetcode] 문제 문제풀이 설명 하...또 쉬워보여서 도전했다가 오지게 오래걸려서 풀었다. (그래도 풀었다는게 대견쓰) 규칙에 따라서 괄호를 숫자로 변경한 뒤, 모든 숫자의 합을 구하는 문제다. (규칙은 위에 써져 있다.) 분명 말하지만 이미 밸런스한 상태라 스택이 필요없다. 괄호를 어떻게 치환하는지가 관건이다. 처음에는 “()”를 “|” 로 치환했었다. 그렇게 변경할 경우 | 양옆에 괄호를 보고 값을 구할 수 있을거라 생각했었지만, (()()) 의 경우에는 ( | | ) 로 변하고, (()(()())) 인 경우에는 ( | ( | | ) ) 등 로직을 구성하는데 있어서 언제 더하고, 언제 기다릴지 에 대한 로직이 뚜렷하게 보이지 않았다. 몇번의 불통 끝에 하나 발견한 사실은 처음 등장하는 “)(” 을 기준으로 양옆으.. 2022. 3. 17.
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.
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.
Permutation in String [leetcode] 문제 문제 풀이 문자열의 퍼뮤테이션 이 존재하는지 여부 판단 문제이다. 문자열의 퍼뮤테이션은 문자열의 길이가 길어질수록 연산량이 급격히 증가하기 때문에 다른 식으로 풀었는데 바로 dictionary (다른말로 Map) 이다. 순서만 바뀐 문자열의 경우, 사용된 문자와 해당 문자 개수가 같다는 점을 이용해 { “a” : n개, “b” : m개, ...} 등으로 나타내 같은 키 값을 가지고 있는지, 서로 다른 키가 존재하지 않는지 여부 같은 키 값에 대해 동일한 수량을 가지고 있는지 여부 를 검사하면 퍼뮤테이션 연산을 피할 수 있다. 코드상으로는 dictionary를 만드는 함수 dictionary 2개를 서로 비교하는 함수 를 구성했다. #dictionary를 만드는 함수 def dictCreate(sel.. 2022. 2. 11.
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.
반응형

티스토리툴바