본문 바로가기

Algorithm/LeetCode

 (24)
[Java] LeetCode 17번 Letter Combinations of a Phone Number 옛날 피처폰에 숫자위치에 있는 알파벳들의 가능한 조합을 모두 출력하는 문제이다. 이런 조합의 문제에서는 재귀호출을 통해서 쉽게 해결할 수 있다. 재귀 함수를 작성할 때 중요한 포인트는 언제 함수가 종료되는지 잘 명시하는 것이다. digits의 길이가 0이 되면 비어있는 리스트를 리턴하고, 1이라면 map에서 조회하여 리턴한다. 이외의 경우에는 첫번째 숫자와 나머지 문자를 이어서 정답에 추가하여 리턴한다. class Solution { Map map = new HashMap(); { map.put("2", List.of("a", "b", "c")); map.put("3", List.of("d", "e", "f")); map.put("4", List.of("g", "h", "i")); map.put("5",..
[Java] LeetCode 15번 3Sum 배열에서 3개의 수의 합이 0이되도록하는 수의 집합을 찾는 문제이다. 먼저 배열을 정렬한 뒤에 2개의 수를 고정하고, 나머지 하나를 binary search로 찾는 방식을 택했다. 시간복잡도는 O(n^2 log(2))이다. 중복되는 집합을 피하기 위해서 전과 같은 수의 값이면 다음 값으로 넘어갈 수 있도록 continue 구문을 작성해주었다. class Solution { public List threeSum(int[] nums) { List answer = new ArrayList(); Arrays.sort(nums); int n = nums.length; for (int i = 0; i 0 && nums[i] == nums[i - 1]) continue; for (..
[Java] LeetCode 11번 Container With Most Water 막대기 2개로 둘러쌓인 부분의 넓이를 구하는 것이 문제이다. 작은 길이의 막대기가 기준이 되어 넓이가 구해지는 것이 문제의 포인트이다. 왼쪽 막대기의 위치를 l 오른쪽 막대기의 위치를 r로 두고, 왼쪽과 오른쪽 중 작은 길이의 막대기를 한칸씩 옮겨서 넓이의 최대값을 찾는다. 작은 것은 옮기는 이유는 더 큰 넓이가 되기 위해서는 작은 길이의 막대기가 길어져야되기 때문이다. class Solution { public int maxArea(int[] height) { int l = 0; int r = height.length - 1; int max = (r - l) * Math.min(height[l], height[r]); while (l < r) { if (height[l]
[Java] LeetCode 10번 Regular Expression Matching 1. dp를 사용하지 않는 풀이 isMatch 함수를 재귀적으로 호출하여 문제를 해결해보았다. 각각의 경우의 수는 주석으로 남겨두었다. 생각보다 복잡하고, 코드가 길어졌다. dp를 사용하지 않기 때문에 중복으로 같은 케이스를 확인하게 되므로 느리다. class Solution { public boolean isMatch(String s, String p) { boolean isPossible = false; // s가 남았는데 p가 없는 경우 if (s.length() > 0 && p.length() == 0) { return false; } // s와 p가 모두 소진된 경우 else if (s.length() == 0 && p.length() == 0) { return true; } if (p.leng..
[Java] LeetCode 5번 Longest Palindromic Substring dp[start][end]에 start부터 end까지의 부분 문자열이 팔린드롬인지 여부를 저장하였다. 1이면 팔린드롬이고 0이면 아직 체크되지 않은 값이며, -1이면 팔린드롬이 아니다. 이중 포문을 돌면서 i와 j를 시작과 끝으로 하는 문자열이 팔린드롬인지 아닌지를 체크하였다. 이미 체크한 문자열들을 다시 검사하지 않기 위해서 dp를 사용하였으며 O(n^2) 보다는 조금 더 느린 풀이이지만 통과되었다. class Solution { public int checkPalindrome(int[][] dp, int start, int end, String s) { if (dp[start][end] != 0) { return dp[start][end]; } int len = end - start + 1; if (..
[Java] LeetCode 4번 Median of Two Sorted Arrays 문제의 조건에서는 O(log(m+n))으로 풀라고 주어졌다. 차근차근 접근하기위해서 느린방법으로 먼저 풀어보았다. 1. O(m+n) 시간복잡도 풀이 중간값을 찾기 위해서 두개의 배열을 합쳐준다. 병합정렬(merge sort)에서 두개의 배열을 합쳐주는 작업과 흡사하다. 두개의 배열의 값들을 비교해서 작은 값을 추가하고 인덱스를 증가시킨다. 인덱스가 전부 증가된 이후에는 남은 배열들을 추가해주는 작업을 해주면 된다. 합친 후에는 홀수개인지 짝수개인지에 따라서 값을 계산해주었다. class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n1 = nums1.length; int n2 = nums2.length; i..
[Java] LeetCode 3번 Longest Substring Without Repeating Characters 반복되는 문자가 없는 가장긴 부분문자열(substring)의 길이를 구하는 문제이다. for문으로 순차적으로 문자를 탐색하면서 map 언제 마지막으로 해당 문자를 마주쳤는지 저장한다. 만약 마주친 문자가 나온다면 마주친 문자의 개수가 부분문자열의 길이가 된다. 그리고 마주친 문자가 이전에 등장한 위치 + 1 부터 현재위치까지 map을 이용해 마주친 문자들을 넣어준다. class Solution { public int lengthOfLongestSubstring(String s) { int ans = 0; Map visitedPos = new HashMap(); for (int i = 0; i < s.length(); i++) { Integer lastPos = visitedPos.get(Character..
[Java] LeetCode 2번 Add Two Numbers 총 3단계로 풀이가 진행되었다. l1과 l2의 길이가 다르고, 최대 100개까지 이어질 수 있다. 1. l1과 l2의 공통 조상을 먼저 더하여 노드로 만들어준다. 2. 공통조상을 제외하고 남은 l1또는 l2를 더해준다. 3. 마지막에 올림이 남았으면 노드를 추가해준다. 컴퓨터 구조에서 가산기를 구현하는 것과 비슷한다. carry라는 변수에 올림이 발생했는지를 저장하고 이것을 더할 때마다 계속 사용했다. 그리고 마지막에도 올림이 발생하였으면 최고 자리수가 1이 되도록 만드는 것이 포인트이다. class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode ..

티스토리툴바