밀래의 코딩북

27일차 LeetCode 도전 입니다. Maximal Square. 1. 문제 Maximal Square 라는 문제입니다. 1로 구성된 정사각형의 넓이를 구하는 문제입니다. 위의 예제로 보면 1이 4칸으로 구성된 정사각형이고 2 2 이기 때문에 답은 2*2로 4가 출력됩니다. 해당 문제는 DP 기본 문제로 생각보다 쉽게 구현이 가능합니다. 2. 풀이 class Solution { public int maximalSquare(char[][] matrix) { int n = matrix.length; if(n == 0) return 0; int m = matrix[0].length; int[][] DP = new int[n+1][m+1]; int max = 0; for(int i=1; i

12일차 Last Stone Weight 입니다. -문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3297/ We have a collection of stones, each stone has a positive integer weight. Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x

7일차 Counting Elements 입니다. - 문제 - 풀이 class Solution { public int countElements(int[] arr) { Set set = new HashSet(); for(int i=0; i

6일차 Group Anagrams 입니다. - 문제 - 풀이 class Solution { public List groupAnagrams(String[] strs) { HashMap map = new HashMap(); List items = new ArrayList(); int k = 0; for(int i=0; i

leetCode 5일차 리뷰 입니다. 문제 이름은 Best Time to Buy and Sell Stock II - 문제 - 풀이 문제를 잘 읽어보면 생각보다 쉽게 문제를 풀 수 있는 방법을 찾을 수 있습니다. 배열의 1번째 index부터 시작해서 이전 숫자보다 크면 두개의 차이를 계속 더해나가면 문제에서 의도하는 해를 구 할 수 있죠. 문제에서 몇일에사서 가장 비싼일에 판다고 했지만 그 차이는 하루하루의 차이를 더한것과 같기 때문이죠 그래서 문제는 아래와 같이 풀 수 있습니다. class Solution { public int maxProfit(int[] prices) { int r = 0; for(int i=1; i prices[i-1]) r += prices[i] - prices[i-1]; retu..

LeetCode 30 Day Challenge 4일차 입니다. 문제 이름은 Move Zeroes - 문제 문제는 숫자 배열이 주어지고 in-place로 옮겨야 합니다. 함수를 call by reference 로 해결해야 한다는 의미 입니다. 주어진 변수 nums안의 데이터를 옮겨 해결한다는 의미 입니다. - 풀이 class Solution { public void moveZeroes(int[] nums) { int temp = 0, zeroCount = 0; if(nums[0] == 0) zeroCount++; for(int i=1; i

4월 1일부터 4월 30일까지 진행하는 LeetCode 30 Day Challenge를 하면서 문제 푸는 방법에 대한 정리하는 글입니다. - 문제 연속된 합이 Max가 되는 구간의 합을 구하는 문제입니다. 문제에서 예를 들면 4, -1, 2, 1 의 연속된 구간의 합이 max가 되기 때문에 6이 답이 됩니다. - 풀이 Follow up을 확인하면 시간복잡도가 O(n)으로 해결되는 문제임을 알 수 있습니다. 그래서 어떻게 하면 시간복잡도가 O(n)이 될 수 있을지 고민해봤어요. O(n)이 되려면 주어진 숫자 만큼 for문을 1회 실행 한다고 생각하면 됩니다. class Solution { public int maxSubArray(int[] nums) { int currentSum = nums[0]; int..

LeetCode 30일 챌린지 2일차는 Happy Number가 출제 되었습니다. 문제 난이도는 easy에요. 문제는 주어진 숫자를 자리수마다 제곱하여 더하고 그 수가 만약 1로 수렴한다면 Happy Number 이다. 라는 문제입니다. 생각보다 어렵지 않은 문제라고 생각되어 아래와 같이 작성하여 제출했습니다. class Solution { public boolean isHappy(int n) { boolean result = true; HashSet hs = new HashSet(); hs.add(n); int num; while(true) { if(n == 1) break; num = 0; while(n != 0) { num += (n%10) * (n%10); n = n/10; } n = num; i..

30일 챌린지 9일 차 문제입니다. Backspace String Compare - 문제 : - 풀이 : class Solution { public boolean backspaceCompare(String S, String T) { return convert(S).equals(convert(T)); } public String convert(String text) { int count = 0; StringBuilder new_text = new StringBuilder(); for(int i=text.length()-1; i>=0; i--) { if(text.charAt(i) == '#') { count++; }else { if(count > 0) { count--; }else { new_text.app..

30일 챌린지 Middle of the Linked List 문제 입니다. 문제 난이도는 Easy 입니다. - 문제 - 풀이 class Solution { public ListNode middleNode(ListNode head) { ListNode currentNode = head; int length = 1; while(currentNode.next != null){ length++; currentNode = currentNode.next; } int count = length/2; currentNode = head; while(count!=0){ count--; currentNode = currentNode.next; } return currentNode; } } 이 문제는 최적화 되었는지 조금은 ..