backtracking
-
[Algo Rhythm🕺💃] LeetCode 90. SubsetsIIAlgo Rhythm🕺💃/LeetCode 2020. 8. 22. 23:24
📚 Problem description Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] 🎯 Solution class Solution { List ans = new ArrayList(); public List subsetsWithDup(int[] nums) { Arrays.sort(nums); backtrack(nums, ..
-
[Algo Rhythm🕺💃] LeetCode 46. PermutationsAlgo Rhythm🕺💃/LeetCode 2020. 8. 22. 22:35
📚 Problem description Given a collection of distinct integers, return all possible permutations. Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 🎯 Solution class Solution { List ans = new ArrayList(); public List permute(int[] nums) { boolean[] visited = new boolean[nums.length]; backtrack(nums, visited, new ArrayList()); return ans; } public void backtra..
-
[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 도둑질Algo Rhythm🕺💃/Programmers 2020. 8. 8. 22:49
📚 문제 설명 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 🎯 어떻게 풀었나 Backtracking을 이용한 첫번째 시도 (0/ 100) => 정확성은 모두 시간 초과, 효율성은 모두 통과 🙅♂️🙅♀️🙅 class Solution { private..
-
[Algo Rhythm🕺💃] LeetCode 784. Letter Case PermutationAlgo Rhythm🕺💃/LeetCode 2020. 7. 27. 15:12
📚 Problem description Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create. Examples: Input: S = "a1b2" Output: ["a1b2", "a1B2", "A1b2", "A1B2"] Input: S = "3z4" Output: ["3z4", "3Z4"] Input: S = "12345" Output: ["12345"] Note: S will be a string with length between 1 and 12. S wi..
-
[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 여행경로Algo Rhythm🕺💃/Programmers 2020. 7. 25. 15:14
📚 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 🎯 어떻게 풀었나 첫번째 시도 (50점/ 100점)..