본문 바로가기
반응형

Algorithm41

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.
거리두기 확인하기 [프로그래머스] 문제 풀이 문제 풀이 자체가 별로 없다. P의 위치를 좌표 평면에서 x=0, y=0 이라고 했을때 맨하튼 거리가 2 이내 인 곳은 총 12 군데로 west ⇒ [-2,0] , [-1,0] southwest ⇒ [-1,-1] south ⇒ [0, -2] , [0, -1] southeast ⇒ [+1, -1] east ⇒ [+2,0], [+1,0] northeast ⇒ [+1,+1] north ⇒ [0,+2], [0+1] northwest ⇒ [-1,+1] 이렇게 총 12개의 공간을 확인해야 한다. 1, 3, 5, 7 번의 공간의 경우 맨하튼 거리가 1인 경우 P가 존재한다면 무조건 False 맨하튼 거리가 2인 경우 P가 존재한다면 중간 공간의 값이 X가 아니라면 무조건 False 2, 4, 6, 8 번의.. 2021. 11. 29.
땅따먹기 [프로그래머스] 문제 풀이 어... 처음에는 dp처럼 이전 계산 결과를 다 저장한다음에 마지막에 경로값을 쓰는? 문제인줄 알았으나 읽다보다 더 쉬운문제였다. 마지막에 계산 결과중 제일 큰값을 출력하면 되는 문제다. 그렇다면 이전 결과중에 제일 큰값 들만 저장하면서 진행하고, 마지막 결과값중에 제일 큰값을 찾아내면 된다는 얘기다. row의 각 값은 이전 값들과의 계산중 가장 큰값만을 저장하면 된다. [1, 2, 3, 5] [5, 6, 7, 8] → 이 단계에서 계산을 보면 (자신의 index와 같은 index는 피해서) 5 → [5+2, 5+3, 5+5] → max=10 6 → [6+1, 6+3, 6+5] → max=11 7 → [7+1, 7+2, 7+5] → max=12 8 → [8+1, 8+2, 8+3] → max=1.. 2021. 11. 26.
반응형

티스토리툴바