Algorithm (51) 썸네일형 리스트형 [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 .. [Java] 2021 위클리 챌린지 7주차 - 입실 퇴실 모기업 코딩테스트의 기출문제로 당시 너무 어려워서 이것을 빼고 제출했던 기억이 있다. 프로그래머스의 정답자 수가 다른 주차수에 비해서 적은 것을 보면 풀기 어려운 문제임을 직감할 수 있다. 나는 그림을 그려서 문제의 규칙을 찾아보고자 했다. 먼저 입실을 1, 4, 2, 3 순으로 하고, 퇴실을 2, 1, 4, 3으로 하는 경우를 살펴보자. 입실과 퇴실을 일렬로 쓰고, 같은 번호를 선으로 이었다. 선으로 둘러쌓아진 부분이 각 번호가 존재한 시간을 나타내게 된다. 1번과 다른 번호들의 관계를 보면서 어떤 경우일 때 확정적으로 만나게 되는지 알아보자. - 1번과 2번의 관계 1번의 파란선이 2번의 노란선을 감싸고 있는 구조가 보이게 되는데, 이 경우에는 1번과 2번이 무조건 만났다는 것을 알 수 있다. 그래서.. 이전 1 2 3 4 5 6 7 다음
