moonscode

/** * [교집합] * 단방향 연결리스트 두개가 주어졌을때 이 두 리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라 * 여기서 주소는 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. * 즉 첫번째 리스트에 있는 k번째 노드와 두번째 리스트에 있는 j번쨰 노드가 주소까지 완전히 같다면 교집합 원소이다. * * [풀이] * => 리스트의 노트간에 공유가 가능한가 * => 만약 주소가 같은 노드가 있다면 그 뒤로는 모두 같다. * => 마지막 노드는 항상 같다. * * */ public class Q07 { /* Node */ static class Node { Node next; int data; Node(int data) { this.data = data; } } /* Result ..

/** * [회문] * 주어진 연결리스트가 회문인지 검사하는 함수를 작성 * * [풀이] * => 리스트 내부함수로 구현하는가 ? * => 양방향인가 단방향인가 ? * => 전체 길이를 캐싱할 수 있는가 ? * */ public class Q06 { public static void main(String[] args) { } /* Node */ static class Node { Node next; int data; Node(int data) { this.data = data; } } /* isPalindromeA */ static boolean isPalindromeA(Node head) { Node reversed = reverseAndClone(head); return isEqual(head, re..

/** * [리스트의합] * 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로표현할 수 있다. * 각 숫자는 역순으로 배열되어 있는데 첫번째 자릿수가 리스트의 맨 앞에 위치하게 배열된다는 뜻이다. * 이와 같은 방식을 표현된 숫자 두개가 있을 때 이 두수를 더해 그 합을 연결 리스트로 반환하는 함수를 작성 * * [풀이] * => 리스트를 직접구현 ? * => 최대 혹은 최소 몇자리수까지 리스트가 존재하는가 ? * * */ public class Q05 { public static void main(String[] args) { sumList(Arrays.asList(9, 9, 9), Arrays.asList(9, 9, 9)); // 1998 } /* sumList - 외부구현 *..

/** * [분할] * 값 x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들 보다 앞에 오도록 하는 코드를 작성 * 만약 x가 리스트에 있다면 x는 그보다 작은 원소들 보다 뒤에 나오기만 하면 된다. * 즉, 원소 x는 오른쪽그룹 어딘가에 존재하면 된다. 왼쪽과 오른쪽 사이에 있을 필요는 없다. * * [예제] * (3) > [5] > 8 > [5] > 10 > (2) > (1) [분할5] * 3 > 1 > 2 > 10 > 5 > 5 > 8 * * [풀이] * => 요청받은 분할값 뒤로 분할값보다 작은게 있으면 앞으로 보내면 된다. * * */ public class Q04 { class Node { Node next; int data; } /* partitionA - 두개의 리스트를 만..

/** * [중간노드삭제] * 단방향 연결리스트가 주어졌을때 중간(처음과 끝이 아님)에 있는 노드 하나를 삭제하는 알고리즘을 구현해라 * 단 삭제할 노드에만 접근할 수 있다. * * Poinst. * => 리스트 내부함수 ? 외부함수 ? * => 삭제는 인덱스로 ? 객체로 ? * * */ public class Q03 { class Node { Node next; int data; } class MyList { Node head; MyList() { } // == 노드 기준 (O) - 마지막 노드를 삭제할 수 없음 == boolean delete(Node node) { Node next = node.next; node.data = next.data; node.next = next.next; return ..

/** * [뒤에서 k번째 원소 구하기] * 단방향 연결리스트가 주어졌을 때 뒤에서 k 번째 원소를 찾는 알고리즘을 구현 * * [풀이] * => 전체길이를 캐싱하고 있는가 ? * => 전체길이를 구하고 재차 뒤에서 K번째를 구함 * */ public class Q02 { public static void main(String[] args) { } /* Node */ static class Node { Node next; int data; Node(int data) { this.data = data; } } /* getNodeFromRear */ static Node getNodeFromRear(Node head, int k) { if(head == null) return null; Node node =..

/** * [중복없애기] * 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성 * 임시버퍼를 사용하지 않고 만들수 있을까? * * [풀이] * => 리스트의 내부구현인가 ? 외부구현인가 ? * => 외부구현일때, 주어진 리스트를 사용해도 되나 ? * => List Iterater 활용 * => Set 으로 데이터 임시저장 * */ public class Q01 { public static void main(String[] args) { List list = new LinkedList(); list.add(1); list.add(1); list.add(2); list.add(2); list.add(3); list.add(3); deleteDuplicationA..

/** * [행렬회전] * 이미지를 표현하는 N * N 행렬 * 이미지의 각 픽셀은 4바이트로 표현됩니다. 이미지를 90도 회전시키는 메소드를 작성 * 행렬을 추가로 사용하지 않고서도 만들수 있습니까 ? * * [풀이] * => 픽셀이 4바이트, int 배열 * => 일반화해서 규칙을 찾아야함 * * */ public class Q07 { /* main */ public static void main(String[] args) { // == sample == int[][] square = new int[][] { new int[] { 1, 2, 3 }, new int[] { 4, 5, 6 }, new int[] { 7, 8, 9 } }; printSquare(square); System.out.print..

/** * [문자열회전] * 한 단어가 다른 문자열에 포함되어 있는지 판변하는 isSubString이라는 메서드가 있다고 가정 * s1과 s2의 두 문자열이 주어졌고, s2가 s1을 회전시킨 결과인지 판별하고자함 * 가령 waterbottle은 erbottlewat을 회전시켜서 얻을 수 있는 문자열 * isSubString 메소드를 한번만 호출해서 판별하는 코드를 작성 ( 한번만 잘라서 같은 문자열이 되는지 ) * *[풀이] * => 회전이란 의미를 명확히 * => [방법1] 두번의 패턴을 비교하는 방법 * => [방법2] 1번의 회전으로 같아진다면 문자열에 마지막에 갔을때 다시 처음으로 가면 문자열이 이어짐 * */ public class Q09 { /* main */ public static void..

/** * [0행렬] * M * N 행렬의 한 원소가 0일 경우 * 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성 * * [풀이] * => 스캔하며 문자열이 0인 것을 찾음 * => 찾음과 동시에 요청사항을 처리하면 * => 후반부에 처리에 의해서 원하지 않은 "0"이 발생할 수 있음 * => 찾아진 0에 대해서 요청사항을 처리해줌 * * */ public class Q08 { /* main */ public static void main(String[] args) { // == sample == int[][] square = new int[][] { new int[] { 1, 2, 1, 3, 1 }, new int[] { 4, 5, 0, 6, 1 }, new int[] { 7..