Apes Together Strong.

https://leetcode.com/problems/spiral-matrix/description Q. m x n matrix가 주어질 때, 모든 matrix의 값을 나선 형태로 반환하라. Solution. 나선으로 하나씩 돌게 로직을 만들다 보니, 예외 상황이 많이 생긴다. 따라서 메모리를 조금 더 쓰고, 간결한 접근법을 찾는다. 외피부터 시계방향으로 데이터를 얻는다. map, dictionary를 사용해, 중복을 방지 한다. 다음 한단계 내피(x+1, y+1)로 들어온다. 이 과정을 Width/2 까지 진행한다. 많은 중복이 생기겠지만, 로직을 단순화 하고, set 자료구조를 써서 중복데이터를 억제한다. 더보기 int CellToIndex(int iX, int iY, int W) { return W..

https://leetcode.com/problems/reverse-linked-list Q. 주어진 리스트를 뒤집어라. Solution. 현재 노드의 '다음' 포인터를 '이전' 노드로 설정한다. 이것의 반복이 다 이다. public ListNode ReverseList(ListNode head) { ListNode node = head; ListNode prev = null; while(node != null) { ListNode next = node.next; node.next = prev; prev = node; node = next; } return prev; } 적절한 결과. 이 문제와, 리스트를 반으로 자르는 문제는 linked list의 기본이 되는 문제다. 완전히 숙지하는 것이 좋을 것이다.

https://leetcode.com/problems/intersection-of-two-linked-lists/description Q. 두개의 노드가 도중에 교차할 때 해당 교차지점을 찾아서 반환하라. Solution 방법을 알면 간단한 문제다. 시작 지점을 align 시키는 것이 키인데, 보통의 풀이법은 두 리스트를 하나씩 전진시켜, 끝에 도달하면 반대 쪽 head에서 다시 출발한다. 이때 재출발 후, 두 노드가 만나는 지점이 교차점이 된다. 두 노드의 오프셋이 다르므로 이를 다른 노드의 시작점으로 재출발 시키면서 오프셋을 동기화 시킨 것이다. 더보기 public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { ListNode node..

Q. 주어진 리스트를 오름차순 정렬하라. 이때 정렬시간을 O(nxlogn) 으로 하여라. Solution. 분할 정렬 하라는 것이다. 분할 병합 정렬을 하기 위한 방법을 정리 해 본다. 우선 list를 2개로 계속 나눈다. 리스트가 하나의 노드만 가질때까지 계속 쪼갠다. 이후로 작은 것 먼저 이어서 위로 반환한다. 분할 조립이 분할/순차적으로 되어야 하므로, 재귀함수가 필요하다. 로직대로 코드를 만든다. 더보기 public ListNode SortList(ListNode node) { // 1개의 노드(이하)가 되면, 그냥 반환한다. if(node == null) return null; if(node.next == null) return node; // break list. ListNode fast = ..

https://leetcode.com/problems/linked-list-cycle-ii/description Q. 주어진 Linked list 의 cycle의 시작점을 찾아 반환하라. 없으면 null을 반환하라. Solution 잘 알려진 linked list의 순환점을 찾는 문제이다. 우선 순환을 찾는 방법은 fast와 slow pointer를 운용하면서 두 포인터가 만나는 지점을 찾는 것이다. 이때 두 포인터가 만나는 부분은 head부터 cycle의 순환 시작점까지 거리를 k 라고 한다면 slow가 cycle 시작점에 위치 시, fast는 loop안에서 k 앞의 위치에 있다. 즉 현재 fast의 위치는 loop안에서 k, slow는 0 이라고 생각할 수 있다. head ---- slow --- f..

Q. 주어진 리스트에 순환이 있는지 판단하라. Solution. 순환이 있는 지 판단하는 가장 쉬운 방법은 fast, slow node를 순환시키고 같은 위치에 존재하는 지점이 있는지 확인하는 것이다. 잘 알려진 방법이므로, 이 문제가 easy level 이 된다. 더보기 public bool HasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast!=null && fast.next!=null) { slow = slow.next; fast = fast.next.next; if(slow == fast) return true; } return false; } 적절한 결과를 얻었다.

Q. 주어진 list를 k 그룹 단위로 reverse하라. 이때 해당 단위가 k 개가 되지 않으면 그냥 두어라. Solution. list를 뒤집는 방법을 안다면 크게 어렵지는 않을 것 같다. 단위로 뒤집고 연결 부위 예외 처리를 충분히 해 준다. 더보기 public ListNode ReverseKGroup(ListNode head, int k) { ListNode Reverse(ListNode head, int cnt, out ListNode outNext) { // check count. ListNode node = head; int count = cnt; outNext = null; while(true) { if(node == null) return head; if(--count == 0) brea..

https://leetcode.com/problems/swap-nodes-in-pairs/description Q. 주어진 리스트를 각 쌍을 뒤집는 꼴로 변형하라. Solution. 직관대로 뒤집어 재 연결하였다. 예외처리가 좀 필요하다. 깔끔한 코드는 아닌 듯. 더보기 public ListNode SwapPairs(ListNode head) { ListNode front = null; ListNode tail = head; ListNode prev = null; head = null; while(tail is not null) { front = tail.next; ListNode next = front!=null ? front.next : null; if(front != null) front.next ..

https://leetcode.com/problems/merge-k-sorted-lists/description Q. k개의 정렬된 list 배열이 주어질 때, 이 모든 배열을 정렬된 상태로 하나의 리스트로 병합하여라. Solution. priority queue를 사용하면 간단한 문제. 이를 이용해서 코드를 만들어 본다. 더보기 C# public ListNode MergeKLists(ListNode[] lists) { PriorityQueue pQ = new PriorityQueue(); for(int q = 0; q < lists.Length; ++q) { if(lists[q] != null) pQ.Enqueue(lists[q], lists[q].val); } ListNode head = null; ..

https://leetcode.com/problems/merge-two-sorted-lists/description Q. 두개의 정렬된 리스트를 하나의 리스트로 병합하라. Solution. 직관대로 그냥 하면 되겠다. 더보기 C# public ListNode MergeTwoLists(ListNode list1, ListNode list2) { ListNode head = null; ListNode n1 = list1; ListNode n2 = list2; ListNode prev = null; while(n1!=null || n2!=null) { int v1 = n1!=null ? n1.val : int.MaxValue; int v2 = n2!=null ? n2.val : int.MaxValue; Lis..