알고리즘31 Alternating Characters 풀이 Java Alternating Characters | HackerRank Calculate the minimum number of deletions required to convert a string into a string in which consecutive characters are different. www.hackerrank.com 문제 5 AAAA BBBBB ABABABAB BABABA AAABBB 인접한 모든 문자가 같지 않으려면 몇 글자를 삭제해야 하는가? 아주 기본문제구만 허허.. class Result { public static int alternatingCharacters(String s) { char[] arr = s.toCharArray(); int res = 0; for(int i = .. 2022. 7. 11. Recursion: Davis' Staircase 풀이 Java Recursion: Davis' Staircase | HackerRank Recursion: Davis' Staircase | HackerRank We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies. www.hackerrank.com Recursion and Backtracking에 DP를 살짝 얹은 문제 피보나치와 비슷하게 공식을 만들면 되지만, n이 커지는 경우를 생각해서 DP를 사용해야 한다. return stepPerms(n - 1) + stepPerms(n - 2) + st.. 2022. 7. 10. Strings: Making Anagrams java 풀이 Strings: Making Anagrams | HackerRank How many characters should one delete to make two given strings anagrams of each other? www.hackerrank.com 시간복잡도 참고 https://hbase.tistory.com/185 [Java] 컬렉션들의 시간복잡도 (Collection Big-O) 자바를 이용해서 알고리즘 문제를 풀거나 큰 사이즈의 데이터를 다룰 때, 컬렉션들의 정확한 시간복잡도(Big-O)를 알고 사용하는 것이 중요하다. 자칫 불필요하게 느린 컬렉션이나 메소드를 사용 hbase.tistory.com list.contains의 시간복잡도는 O(n) 이기 때문에 내 풀이의 시간복잡도는 O(n^.. 2022. 7. 9. Hash Tables: Ice Cream Parlor 풀이 java Hash Tables: Ice Cream Parlor | HackerRank Help Sunny and Johnny spend all their money during each trip to the Ice Cream Parlor. www.hackerrank.com 포인트는 카테고리에 있는 것처럼 HashTable (HashMap)! 1. cost 값들을 HashMap에 저장하고 2. for : cost 값을 하나씩 가지고 오며 money-cost 값을 구함 3. money-cost 값이 hashmap에 있는지 확인하고, 있으면 return 이렇게 하면 O(n)의 시간복잡도를 가져서 시간초과가 안남 import java.io.*; import java.math.*; import java.security.*.. 2022. 7. 9. Max Array Sum 풀이 Java Max Array Sum | HackerRank Find the maximum sum of elements in an array. www.hackerrank.com DP문제 subset of non-adjacent elements : 인접하지 않은 요소들의 집합 arr = {-2, 1, 3, -4, 5} dp = new int[5] 시작하기 전에, dp[0] = -2 (제일 첫번째 수만 초기화) dp[1] = max(n,d(n-1)) = max(-2,1) = 1 case 1 : N번째 수를 포함하는 경우 n : n 번째 값, d(n) : n 까지의 합 max(n,d(n-2)+n) * d(n-2)인 이유는 인접하면 안되기 때문 case 2 : N번째 수를 포함하지 않는 경우 d(n-1) ---- d[n] .. 2022. 7. 9. Binary Search Tree : Lowest Common Ancestor 풀이 Java LCA : LCA알고리즘은 트리에서 두 개의 노드를 선택했을 때 최소 공통 조상을 구해주는 알고리즘이다. LCA는 두 노드가 처음으로 갈라지는 지점이다. * 본인 포함 * 자기 자신도 자신의 조상이 될 수 있음 이 문제는 LCA에 대한 개념과 재귀에 대해서 알면 쉽게 풀 수 있지만 개념을 이해하지 못하면 산으로 갈 수 있다. DFS 재귀로 풀기 import java.util.*; import java.io.*; class Node { Node left; Node right; int data; Node(int data) { this.data = data; left = null; right = null; } } class LCA_BST { /* * class Node int data; Node left; N.. 2022. 7. 9. 이전 1 2 3 4 5 6 다음 반응형
