인생은 효율성

https://leetcode.com/problems/island-perimeter/ Island Perimeter - 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 grid = [[0,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0]] 그림처럼 1은 땅을 0은 물을 뜻한다. 이때 땅의 둘레를 구하는 문제 ==풀이== 1. 땅 두 칸이 붙어 있으면 겹치는 선이 한 개일 것이다. 2. 겹치는 것 생각하지 않고 각 네모의 둘레를 모두 구했을 때..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 처음부터 하나씩 더하고 빼는 경우의 수를 다 구하는 건 비효율적이란 생각이 들어서 반대로 생각해보았다. 숫자들을 전부 더한 다음 거기서 타겟이 되도록 빼는 것이다. 숫자들의 총합은 (타겟이 되기 위한 숫자들 + 잉여 숫자들)이기 때문에 잉여 숫자들의 조합 경우의 수를 구하는 게 답을 구하는 거나 마찬가지이다...

https://leetcode.com/problems/freedom-trail/ Freedom Trail - 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 리스트 ring은 [0]번 요소가 12시 방향에 위치하고 뒤따르는 요소들이 시계방향으로 위치한 다이얼 모양 원이다. 선택해야 하는 알파벳인 key가 주어진다. ring을 시계방향 혹은 반시계 방향으로 돌리면서 key에 해당하는 알파벳을 순서대로 고를 건데 이때 다이얼을 가장 적게 돌리는 경우의 횟수를 구하라...

https://leetcode.com/problems/frog-jump/ Frog Jump - 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 개구리가 강을 건너는데 그 강은 몇 개의 유닛으로 쪼개져 있다. 각 유닛엔 돌이 있을 수도 있고 없을 수도 있다. 오름차순 리스트인 stones가 주어질 때 개구리가 맨 끝까지 갈 수 있다면 true를 반환한다. 맨 처음에는 1칸을 뛸 수 있으며 개구리가 마지막에 k유닛을 점프했다면 다음에 점프할 수 있는 유닛의 간격은 k..

https://leetcode.com/problems/jump-game/ Jump Game - 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 ==문제== nums배열에서 각 요소들은 오른쪽으로 최대 점프할 수 있는 칸 수이다. 첫 번째 인덱스에서 출발할 때 마지막 인덱스까지 도달할 수 있다면 True를 그렇지 않으면 False를 반환하는 문제이다. ==방법== 최대로 갈 수 있는 maxIdx를 저장하고 반복문을 돌면서 maxIdx를 갱신해준다. i와 [i] 값을..

https://leetcode.com/problems/remove-k-digits/submissions/ Remove K Digits - 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 num에서 주어진 k횟수만큼 숫자를 하나씩 삭제해서 가장 작은 숫자가 나오도록 하는 문제이다. 만약 num=1726, k=2라면 숫자 두 개를 지워서 나올 수 있는 가장 작은 숫자 12를 반환하면 된다. 만약 숫자를 단 하나만 지워서 가장 작은 숫자를 만들고 싶다면 숫자를 왼쪽부터..

https://leetcode.com/problems/bulb-switcher-iv/ Bulb Switcher IV - 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 방 안에 전구들이 모두 꺼진 상태이다. 이 전구들을 target상태와 똑같이 만드는 데에 몇 번 스위치를 눌러야 하는지 구하는 문제이다. i번째 전구를 선택하면 i~len(arr)까지의 전구의 상태가 반전된다. 만약 전구가 00111인 상태에서 두 번째 두 번째 전구를 선택했다면 두 번째~다섯 번째..

https://leetcode.com/problems/jump-game-v/ Jump Game V - 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 ==문제== 막대기의 높이가 담긴 배열 arr과 한 번에 점프할 수 있는 막대기의 최대 숫자 d가 주어질 때, 가장 많이 건너뛸 수 있는 횟수를 구하는 문제이다. ==접근방법== arr요소의 인덱스를 차례로 dp함수로 보내서 각 막대기 별로 이동할 수 있는 최대 횟수를 구한다. dp함수에서는 제일 먼저 idx가 딕셔..

https://leetcode.com/problems/subarray-sum-equals-k/ Subarray Sum Equals K - 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 ==문제== nums배열에서 더해서 k가 되는 부분 배열의 가짓수를 구하는 문제이다. ==풀이== 누적합계인 sums를 선언해서 합계에 어떤 숫자가 더해질 때마다 sums-k 값을 구한다. 이 값이 이 전에 구했던 sums의 이력 중 어떤 것이라도 일치하는 게 있다면 부분 배열 개..

https://leetcode.com/problems/longest-string-chain/ Longest String Chain - 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 ==문제== 소문자로 구성된 words 배열을 받는다. 알파벳이 하나씩 추가되어 'a' 'ab' 'dab' 같은 식으로 이어질 때 이것을 word chain이라고 부른다. words배열 안에서 가장 길게 연결할 수 있는 word chain 개수를 구하라. ==처음 코드== 각 단어의 ..