본문 바로가기

Algorithm

 (51)
[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] 위클리 챌린지 8주차 - 최소직사각형 sizes에 이차원 배열로 가로 세로의 값이 주어진다. 가로세로중 긴 길이를 가로로, 짧은 길이를 세로로 바꾸어서 각각 가로의 최대값과 세로의 최대값을 구한 후 이를 곱해주어 반환한다. class Solution { public int solution(int[][] sizes) { int answer = 0; int n = sizes.length; int maxWidth = 0; int maxHeight = 0; for(int i = 0; i < n; i ++){ maxWidth = Math.max(maxWidth, Math.max(sizes[i][0], sizes[i][1])); maxHeight = Math.max(maxHeight, Math.min(sizes[i][0], sizes[i][1])); ..
[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..
[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",..

티스토리툴바