Apes Together Strong.

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. 주어진 숫자 num 을 세 자리마다 ","로 구분되어지는 숫자 string으로 출력하라. 예) 1234567 => "1,234,567" Solution 문제 자체는 딱히 어려움이 없다. 마지막 자리수 구하는 방법으로 string을 만들어 나가고, 3자리마다 ","를 더한다. 마지막 자리부터 string을 만들었으므로, 마지막에 string을 뒤집으면 원하는 결과가 된다. string NumToString(long num) { string ret = ""; int cnt = 0; while(num > 0) { ret += (num%10).ToString(); ++cnt; if(cnt%3 == 0) ret += ","; num /= 10; } // c# string 뒤집기, 알아두면 좋을 듯. char..

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/lru-cache  Q. LRU cache를 사용하도록 class를 디자인 하라.  입력은, key, value의 두개의 int type이 들어오며, key가 같으면 overwrite 하고 없으면 add 하라.  Solution.  key를 기준으로 data에 접근해야 하므로, 우선 map 이나 dictionary 타입의 구조가 필요하다. 그리고,  마지막으로 덜 사용한데이터에 바로 접근해야 하므로, list 구조가 필요하다.  c# 에서는 iterator가 없으므로, 아래와 같이 더블 링크드 리스트를 사용해서 데이터에 바로 접근하면 적당하다. public class DoubleListNode { public int val, key; pub..

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 ..

코드 작성하는 인터뷰에 쉽지만 자주 나는 shuffle 문제를 정리 해 보기로 한다. 방법을 알면 쉽지만, 모르면 까다로울 수 있다. Q. 카드가 n 장 주어진다. 이때 이 카드를 랜덤하게 shuffle해서 반환하라. Solution. random을 활용해야 하는 것은 확실하다. 직관적으로 생각해 보면, 루프를 n 번 돌며 랜덤을 생성하고, 나왔던 수가 나온다면 다시 랜덤 번호 생성을 하면 될 것같다. 이 방법은 최적일 때 O(N)이지만, 최적일 확률은 거의 없다. 따라서 다른 방법을 생각해 본다. 랜덤한 위치의 카드를 하나 고른다. (1 ~ n 까지의 수 중 하나의 random 번호를 생성한다. ) 이 카드를 0번 위치의 카드와 교체한다. 다시 1번부터 랜덤한 위치의 카드를 고른다. 이 카드를 1번 위..

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..

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description Q. 단일 리스트에서 뒤에서 n 번째 노드를 찾아 제거하여라. Solution. 우선 단일 리스트에서 뒤에서 n 번째 노드를 어떻게 찾는가. 노드 두개를 가지고 하나를 먼저 출발시킨다. (fastNode) 이 노드가 앞에서 n번째 진행하면, 그 후에 다음 노드를 head에 둔다.(slowNode) fastNode가 리스트에 끝에 도달할 때까지 두 노드를 하나씩 진행 시킨다. 이 결과, slowNode가 바로 뒤에서 n 번째 노드가 된다. 이제 이 slowNode만 삭제하면 되겠다. 우리가 앞에서 부터 진행하므로, slowNode의 바로 앞노드를 알 수 있다.(prevNod..