Algorithm/LeetCode (24) 썸네일형 리스트형 [Java] LeetCode 34번 Find First and Last Position of Element in Sorted Array 정렬된 배열에서 target이 위치하는 첫번째 위치와 마지막 위치를 구하는 문제이다. 정렬이 되어있으므로 이분 탐색을 사용할 수 있다. 일반적인 이분탐색으로 찾되, 타겟보다 크거나 같은 부분에서 일치하는 것을 찾게 되면 시작점이 되고, 타겟보다 작거나 같은 부분에서 일치하는 부분을 찾게되면 마지막점이 된다. class Solution { public int[] searchRange(int[] nums, int target) { int n = nums.length; int l = 0; int r = n - 1; int[] answer = { -1, -1 }; while (l [Java] LeetCode 33번 Search in Rotated Sorted Array 로테이션이 되어있으면 숫자를 오름차순의 구역 두개의 구역으로 나누어서 생각할 수 있다. 왼쪽의 첫번째가 무조건 첫번째의 숫자가 오른쪽 구역의 첫번째 숫자보다 크게된다. 이 지점을 binary search로 찾는다. 오른쪽 구역의 시작 점을 turnPoint라는 변수에 저장하였다. 이제 왼쪽과 오른쪽 구역에서 각각 일치하는 숫자의 index를 찾고 이것을 return 해주면 된다. class Solution { public int search(int[] nums, int target) { int first = nums[0]; int n = nums.length; int l = 1; int r = n - 1; int turnPoint = 0; int answer = -1; while (l [Java] LeetCode 25번 Reverse Nodes in k-Group 먼저 list를 reverse하는 함수를 만들고, K개의 node를 만나면 reverse를 한다. reverse한 node의 마지막을 저장하여, 다음번 reverse를 하게 되면 이 둘을 이어준다. class Solution { public ListNode reverse(ListNode head) { int n = 0; ListNode cur = head; if (head == null) { return null; } while (cur != null) { n++; cur = cur.next; } if (n == 1) { return head; } cur = head; ListNode prev = null; ListNode next = null; while (cur != null) { next = cur.. [Java] LeetCode 23번 Merge k Sorted Lists k개의 정렬된 링크드 리스트를 1개의 정렬된 링크드 리스트로 합치는 문제이다. 머지소트와 상당히 흡사하다. 그래서 list의 길이가 2라면 두 리스트를 합쳐주고, 3이상이라면 반씩 쪼개어서 다시 merge 과정을 진행해준다. class Solution { public ListNode mergeTwo(ListNode first, ListNode second) { ListNode ret = new ListNode(); ListNode cur = ret; while (first != null && second != null) { if (first.val < second.val) { cur.next = new ListNode(first.val); first = first.next; } else { cur.nex.. [Java] LeetCode 22번 Generate Parentheses 재귀적으로 호출하여서 괄호를 만들었다. 중복으로 괄호가 추가되는 것을 방지하기 위해서 set으로 체크를 하였다. class Solution { public Map dp = new HashMap(); public List generateParenthesis(int n) { if (dp.get(n) != null) { return dp.get(n); } if (n == 1) { List list = new ArrayList(); list.add("()"); dp.put(1, list); return list; } List answer = new ArrayList(); List smallerOne = generateParenthesis(n - 1); Set checked = new HashSet(); for .. [Java] LeetCode 21번 Merge Two Sorted Lists 2개의 singly linked list를 merge하는 문제이다. 처음에는 while문으로 두개의 리스트에서 값을 비교해서 정답에 추가해준후에, 나중에 남아있는 list를 붙여준다. class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode cur = null; ListNode answer = null; while (l1 != null && l2 != null) { ListNode node; if (l1.val < l2.val) { node = new ListNode(l1.val); l1 = l1.next; } else { node = new ListNode(l2.val); l2 = l2.next; } if (c.. [Java] LeetCode 20번 Valid Parentheses Stack을 이용해서 쉽게 해결이 가능하다. 닫는 괄호가 나왔을 때, stack에서 pop한 값이 짝을 이루는 괄호가 아니라면 잘못된 괄호 쌍이 된다. class Solution { public boolean isValid(String s) { Deque stack = new LinkedList(); boolean result = true; for (int i = 0; i < s.length(); i++) { Character c = s.charAt(i); if (c == '(' || c == '{' || c == '[') { stack.push(c); } else { if (stack.size() == 0) { result = false; break; } Character popC = stack.pop.. [Java] LeetCode 19번 Remove Nth Node From End of List 싱글 링크트 리스트에서 뒤에서 n번째의 노드를 삭제하여 return 하는 문제이다. 자바에서 제공하는 List 자료구조를 사용하는 것이 아니라, 주어진 싱글 링크드 리스트인 ListNode를 사용해서 푸는 것이 핵심이라고 생각된다. 싱글 링크드 리스트이기 때문에 앞에서 몇번째인지는 알 수 있지만, 뒤에서 몇번째인지는 알기가 어렵다. 그래서 먼저 리스트의 사이즈를 구하고, 뒤에서 몇번째가아니라 앞에서 몇번째를 지우는 문제로 바꿔준다. 리스트의 사이즈가 1인 경우는 null을 리턴해줘야되고, 첫번째 노드를 지우는 경우에도 head.next를 return 해줘야된다. 이외에는 중간노드.next = 중간노드.next.next 로 값을 변경해주면 된다. class ListNode { int val; ListNod.. 이전 1 2 3 다음