이재윤 블로그

문제 이해 - 배열에서 Target과 일치하는 두 수의 합을 구하라 해결 전략 (1) O(n2)으로 문제를 풀이하면, 2중 for문을 순회하면서 목표하는 target을 구할 수 있습니다. (2) O(n)으로 문제를 풀이하면, HashMap을 사용해서 목표하는 target을 구할 수 있습니다. 구현 (1) O(n2) class Solution { public int[] twoSum(int[] nums, int target) { int[] answer = new int[2]; for(int i=0; i

문제 이해 - 두 링크드 리스트의 덧셈을 구하라 해결 전략 - 두 개의 링크드 리스트를 각각 순회하면서, 값을 추출하고, 각각의 값을 더해줍니다. 구현 class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int carry = 0; ListNode p, dummy = new ListNode(0); p = dummy; while(l1 != null || l2 != null || carry != 0){ if(l1 != null){ carry += l1.val; l1 = l1.next; } if(l2 != null){ carry += l2.val; l2 = l2.next; } ListNode tmp = new ListNode(ca..

문제 이해 - 두 정렬된 링크드 리스트를 합쳐라 해결 전략 - 링크드 리스트의 기본 문제입니다. - ListNode dummy와 head를 선언한 후, head에 조건에 맞게 값들을 추가합니다. - 마지막으로 dummy.next를 반환합니다. 구현 class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(0); ListNode head = dummy; while(list1 != null && list2 != null){ if(list1.val < list2.val){ head.next = new ListNode(list1.val); head = head.next; ..

문제 이해 - 링크드 리스트가 팰린드롬인지 아닌지 판별하라 해결 전략 - 이 문제를 푸는데는 여러 가지 전략이 있습니다. -> 그 중에서 '뒤집어서 비교하는' 전략을 선택했습니다. - reverseAndClone 메소드를 통해서 뒤집은 ListNode를 만들고, isEqual 메소드를 통해서 비교해줍니다. 구현 class Solution { public ListNode reverseAndClone(ListNode node){ ListNode head = null; while(node != null){ ListNode n = new ListNode(node.val); n.next = head; head = n; node = node.next; } return head; } public boolean isP..

문제 이해 - 링크드 리스트에서 특정 값을 삭제하라 해결 전략 - dummy라는 임의의 노드를 생성합니다. - dummy.next에 head를 대입합니다. - curr에 dummy를 대입합니다. - curr를 순회하면서 val에 해당되는 값을 제거합니다. 구현 class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode curr = dummy; while(curr.next != null){ if(curr.next.val == val){ curr.next = curr.next.next; }else{ curr = curr.nex..

문제 이해 - 링크드 리스트의 중간부부터 반환하라. 해결 전략 - 두 개의 링크드 리스트(slow, fast)를 선언하고, 각각에 head를 대입한다. - while문을 통해 slow=slow.next, fast=fast.next.next로 이동하면서, fast와 fast.next중 하나가 null일때까지 이동한다. - slow를 리턴한다. 구현 class Solution { public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } return slow; ..

문제 이해 - 문자열에 하나의 문자를 추가함으로 인해서, subsequence를 최대화하라. 해결 전략 - 문자열을 순회하면서 첫번째 문자를 만날때마다, cnt1++을 한다. - 문자열을 순회하면서 두번째 문자를 만날때마다, res에 cnt1을 더하고, cnt2++을 한다. - 최종적으로 res에 cnt1과 cnt2중에 큰 값을 더해준다. 구현 class Solution { public long maximumSubsequenceCount(String s, String pattern) { long res = 0, cnt1 = 0, cnt2 = 0; for (int i = 0; i < s.length(); ++i) { if (s.charAt(i) == pattern.charAt(1)) { res += cnt..

문제 이해 - 배열에 있는 값들을 +1씩 K번 증가할 때, 최종적으로 배열에 있는 값들의 곱을 최대화할 수 있도록 하라 해결 전략 - 우선순위 큐를 사용해서, 배열의 값들을 저장한다. - 우선순위 큐를 통해, 가장 작은 값을 추출하고, 그 값에 1을 더한 후, 다시 우선순위 큐에 넣는다. - 우선순위 큐에서 값을 하나씩 빼면서 곱해준다. 구현 class Solution { public int maximumProduct(int[] nums, int k) { long answer = 1; PriorityQueue pq = new PriorityQueue(); for(int i=0; i

문제 이해 - directions 문자열에 나타난 문자에 따라 충돌 횟수를 구하라 해결 전략 - int i = 0 을 선언하고, directions 문자열을 순회하면서 L이 아닌 지점까지 이동합니다. - 해당 지점부터 'R'이 발견되면, carsFromRight에 값을 하나씩 추가하고, 'S'가 발견되면 answer에 carsFromRight를, 'L'이 발견되면 answer에 carsFromRight+1을 더해줍니다. - carsFromRight를 0으로 초기화한 후, 계속 순회합니다. 구현 class Solution { public int countCollisions(String directions) { int answer = 0; int i = 0; int carsFromRight = 0; for(..

문제 이해 - 정렬된 Linked List에서 중복된 원소를 제거하라 해결 전략 - ListNode list를 만들고, head의 주소를 저장합니다. - list를 순회하면서, 만약 해당 위치의 값(val)과 다음 위치의 값(val)이 같다면, 다음 위치의 노드를 제거해줍니다. - 다음 위치의 노드가 존재하지 않는다면 while문을 탈출합니다. - head를 반환합니다. 구현 public class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode list = head; while(list != null){ if(list.next == null){ break; } if(list.val == list.next.val){ list.n..