하이 나윤

문제 특정 인덱스의 이웃값이 비어있는지 체크한 후 비어있으면꽃을 심고 그렇지 않을 경우 넘어가며 주어진 n만큼 꽃을 심을 수 있는지 판단하는 문제  풀이 -> 크기가 2 * 10^4 정도의 작은 배열이었기 때문에 주어진 flowerbed보다 크기가 2 큰 새로운 배열 custom을 선언해서맨 앞과 맨 끝에 0을 각각 넣고 인덱스 1부터 flowerbed_size + 1에 배열 flowerbed를 복사했다.그 후 1부터 flowerbed_size까지 체크하며 꽃을 심을 땅을 셌다. class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { int count = 0; int size = flowerbed...

Trie트라이라고 하는 자료구조가 존재하는데 문자열을 저장하고 탐색하기 위해 사용된다고 한다. 특히 단어 검색 알고리즘에 사용된다고 한다.문자열 저장을 위한 메모리를 어느정도 차지하고는 있지만 O(n)으로 굉장히 빠르다. 이 링크를 보고..공부하며 아래 코드 구현하였다. (설명 완벽..) Node는 문자 Character 키와 연결되는 Node를 가지는 HashMap과 해당 노드가 문자열의 마지막 문자인지를 알려주는 endOfWord로 이루어져 있다. 하나의 노드가 다양한 노드로 뻗어나가기 위해 HashMap을 사용한 것 같다.class Trie { public Node root; public Trie() { root = new Node(); } public vo..

문제 최초 풀이 -> 정렬 후 맨 마지막이 정답이라 가정한 후 for문으로 인덱스 2씩 이동하면서 두 개의 수를 비교최종 풀이 -> 비트연산자 ^를 사용함 ^는 XOR 연산자로 이진수에서 대응되는 수가 같으면 0, 다르면 1을 반환한다. 최종 풀이(1ms)class Solution { public int singleNumber(int[] nums) { int r = 0; for(int i = 0; i  최초 풀이(7ms)class Solution { public int singleNumber(int[] nums) { Arrays.sort(nums); int answer = nums[nums.length - 1]; ..

문제 최초 풀이 -> 이진수로 바꿔서 문자열 형태로 가져온 후 반복문으로 문자 요소 중 1의 개수를 세었다.중간 풀이 -> 이진수로 바꾸는 과정에서 1이 있으면 세었다.최종 풀이 -> 비트 연산자를 사용하였다. 최종 풀이(3ms)n & 1 -> 이진수의 1의 자리에 1이 있는지 체크n >> 1 -> 나누기 2, 이진수에서는 오른쪽으로 한칸씩 미는 것class Solution { public int[] countBits(int n) { int[] result = new int[n + 1]; for(int i = 0; i > 1; } return result; }}  중간 풀이(8ms)class Solution { public int[] co..

문제 맨 아래 칸부터 하나 혹은 두 칸씩 올라가면서 최소 칸 수를 메모하며 올라간다. class Solution { public int minCostClimbingStairs(int[] cost) { int start = 0; int top = cost.length + 2; int[] m_cost = new int[top]; for(int i = 0; i m_cost[start + 1] + minimum[start]) { minimum[start + 1] = m_cost[start + 1] + minimum[start]; } if (start + 2 m_cost[start + 2]..

링크 DP(Dynamic Programming)하나의 큰 문제를 작은 문제로 나누어 해결하는 기법 동적프로그래밍을 사용하는 대표적인 문제가 피보나치 수열이다.f(n) = f(n - 1) + f(n - 2) (n > 2), f(0) = 0, f(1) = 1 위의 수열을 해결하기 위해 재귀적으로 문제를 해결할 수도 있지만 중복 실행이 발생하게 되고 n이 커지면 커질수록 비효율적이다.따라서 f(0), f(1)을 배열에 저장해서 한번 구한 값을 또 구하지 않도록 아래와 같이 f(n)을 구할 때까지 반복적으로 연산을 진행한다.  DP를 사용해서 문제를 풀기 위해서는 문제를 작은 문제로 나누고 이 결과를 이용해서 동일한 작은 문제를 해결하도록 해서 소문제를 재사용해야한다.즉, 비슷한 여러 개의 소문제로 나눌 수 있..

링크 이진탐색이란 정렬된 배열에서 가운데 숫자를 고른 후, 찾으려던 숫자보다 작으면 가운데를 기준으로 앞의 절반 배열을 버리고 크면 가운데를 기준으로 뒤의 절반 배열을 버린 후 다시 가운데 숫자를 뽑아서 찾고자 하는 숫자를 찾아가는 탐색이다. 가운데 숫자를 고를 때는 배열 내 가장 작은 인덱스 + (가장 큰 인덱스 - 가장 작은 인덱스) / 2 로 찾는다./** * Forward declaration of guess API. * @param num your guess * @return -1 if num is higher than the picked number * 1 if num is lower than the picked number * othe..

링크class Solution { public static Map map; public static List result; public static String[] temp; public static int len; public List letterCombinations(String digits) { len = digits.length(); temp = new String[len]; result = new ArrayList(); map = new HashMap(); map.put("2", new String[]{"a", "b", "c"}); map.put("3", new String[]{"d", "e",..

링크/** sort가 없는 상황에서는 heap, priority queue를 쓰면.. 이러한 상황을 극복할 수 있다.. */import java.util.PriorityQueue;import java.util.Collections;class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); for(int n: nums) { pq.add(n); } for(int i = 0; i

링크import java.util.*;class Solution { public int nearestExit(char[][] maze, int[] entrance) { int result = -1; Queue queue = new LinkedList(); int m = maze.length; int n = maze[0].length; int[][] visited = new int[m][n]; for(int i = 0; i r.route + 1) { visited[r.x + 1][r.y] = r.route + 1; queue.add(new Route(r.route + 1,..