본문 바로가기
반응형

알고리즘81

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.
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.
배달 [프로그래머스] 문제 풀이 설명 그래프 보자마자 음 이건 dfs 문제군 이라고 감이 왔다. 확실히 예전보다는 문제를 많이 풀어봐서 감을 익힌듯 하다. 그래프 그림을 보면 주의 할 점이 보이는데, cycle 이 존재한다는 점이다. 연결된 node를 따라갈때, recursive 하게 함수를 짜게 되는데, 끝이 없다면 stack overflow로 에러가 날수 있다. 그래서 visited 라는 배열을 만들어 이전에 방문한 node에 대해 체크할 수 있도록 구현했다. 우선 road 매트릭스를 만들어 준다. 매트릭스 mat[i][j] 는 i번째 마을과 j 번째 마을의 road 길이로 세팅해준다. 각 마을 별로 방문했는지 여부를 알 수 있게 visited 리스트 역시 만들어준다. mat = [] for i in range(N): #.. 2022. 1. 29.
Linked List Random Node [leetcode] 문제 Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen. Implement the Solution class: Solution(ListNode head) Initializes the object with the integer array nums. int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen. Example 1.. 2022. 1. 7.
반응형

티스토리툴바