Java/알고리즘 (47) 썸네일형 리스트형 [자바 알고리즘 인터뷰] 9장 스택,큐 (1) - 유효한 괄호 https://leetcode.com/problems/valid-parentheses/description/ - 대중소 세 종류 괄호로 된 입력값이 유효한지 판별하라 풀이 1) 스택 일치 여부 판별 - 열림 괄호인 [,{,( 는 스택에 푸시(push)하고, 닫힘 괄호인 ),},]를 만날 때 스택에서 팝(pop)한 결과가 매핑 테이블 결과와 매칭되는지 확인 - 매핑 테이블을 만들어 놓고 테이블에 존재하지 않으면, 즉 닫힘 괄호가 아닌 경우 무조건 푸시하고, 팝했을 때 열림 괄호가 아닌 경우 false를 리턴하도록 구현 - 입력값이 유효하지 않을 경우, 예를 들어 닫힘 괄호가 두번 연달아 들어오는 경우 스택이 비어 있는데 닫힘 괄호인 경우가 생긴다. 이렇게 되면 중간에 스택이 비게 된다. -> 이.. [자바 알고리즘 인터뷰] 8장 연결 리스트(7) - 역순 연결리스트 2 https://leetcode.com/problems/reverse-linked-list-ii/description/ - 위치 left에서 right까지를 역순으로 만들어라. 위치는 1부터 시작한다. 풀이 1) 반복 구조로 노드 뒤집기 - 우선 변경이 필요한 위치의 바로 앞까지 다음과 같이 이동 //임시 노드 선언ListNode root = new ListNode(0);//임시 노드 다음으로 노드 시작root.next = head; //임시 노드부터 시작해 변경 필요한 위치 앞으로 이동 ListNode start = root;for(int i=0; i - start는 변경이 필요한 2의 바로 앞 지점 1을 가리키고, end는 start.next인 2를 가리킨다. - head는 1인데, 그보다도 더 .. [자바 알고리즘 인터뷰] 8장 연결 리스트(6) - 홀짝 연결 리스트 https://leetcode.com/problems/odd-even-linked-list/description/ - 연결 리스트를 홀수 번째 노드 다음에 짝수 번째 노드가 오도록 재구성하라. 공간 복잡도 O(1), 시간복잡도 O(n)에 풀이하라 풀이 1) 반복 구조로 홀짝 노드 처리 - 홀수 노드 다음에 짝수 노드가 오게 재구성하라고 했으니 홀(Odd), 짝(Even) 각 노드를 구성한 다음 홀수 노드의 마지막을 짝수 노드의 처음과 이어 주면 될 것같다. - 홀수 노드 odd는 1에서 시작하고, 짝수 노드 even은 2에서 시작해 1->3->5, 2->4->6으로 이어지게 한 다음, 홀수 노드의 마지막인 5의 다음 노드를 짝수 노드의 처음인 2로 이어주면 된다. - 짝수 노드가 존재한다면 계.. [자바 알고리즘 인터뷰] 8장 연결 리스트(5) - 페어의 노드 스왑 https://leetcode.com/problems/swap-nodes-in-pairs/description/ - 연결 리스트를 입력받아 페어(pair)단위로 스왑하라 풀이 1) 값만 교환 - 연결 리스트의 노드를 변경하는 게 아닌, 노드 구조는 그대로 유지하되 값만 변경하는 방법 class Solution { public ListNode swapPairs(ListNode head) { //스왑을 진행할 노드 선언 ListNode node = head; //현재 노드와 다음 노드가 존재하면 계속 진행 while(node != null && node.next!=null) { //임시 변수를 이용해 값만 교환.. [자바 알고리즘 인터뷰] 8장 연결 리스트 (4) - 두수의 덧셈 https://leetcode.com/problems/add-two-numbers/description/ 풀이 1) 자료형 변환 - 연결 리스트를 문자열로 이어 붙인 다음에 숫자로 변환하고, 이를 모두 계산한 후 다시 연결 리스트로 바꾸기 1. - 반복 구조로 역순 연결리스트 만들기 public ListNode reverseList(ListNode head) { ListNode prev = null, node = head; //노드 끝으로 이동할 때까지 순회 while(node != null) { //현재 노드의 다음 노드 미리 지정 ListNode next = node.next; //현.. [자바 알고리즘 인터뷰] 8장 연결 리스트(3) - 역순 연결 리스트 https://leetcode.com/problems/reverse-linked-list/description/ - 연결 리스트를 뒤집어라 풀이 1) 재귀 구조로 뒤집기 - 다음 노드 next와 현재 노드 node를 파라미터로 하여 계속해서 재귀 호출- node.next에는 이전 prev 리스트를 계속 연결해주면서 node가 널이 될 때까지 재귀호출하면 마지막에는 백트래킹되면서 연결 리스트가 거꾸로 연결된다. - 맨 처음에 리턴된 prev는 뒤집힌 연결 리스트의 첫 번째 노드가 된다. class Solution { public ListNode reverse(ListNode node , ListNode prev) { //현재 노드인 node가 널이면 리턴 if(node.. [자바 알고리즘 인터뷰] 8장 연결 리스트(2) - 두 정렬 리스트의 병합 https://leetcode.com/problems/merge-two-sorted-lists/description/ - 정렬되어 있는 두 연결 리스트를 합쳐라 풀이 1) 재귀 구조로 연결 - 병합 정렬에서 마지막 조합시 첫 번째 값부터 차례대로 비교하면 한 번에 해결되듯이, 이 또한 병합 정렬의 마지막 조합과 동일한 방식으로 첫 번째부터 비교하면서 리턴 - 먼저 list1과 list2의 값을 비교하여 작은 값이 있는 쪽을 재귀 호출로 엮은 다음 결과를 리턴 - 재귀 호출시 엮는 쪽은 그 다음 노드를 입력값으로 전달 - 어느 한쪽이 널(Null)이 된다면 널이 아닌 노드를 리턴하면서 마무리 class Solution { public ListNode mergeTwoLists(ListNode l.. [자바 알고리즘 인터뷰] 8장 연결 리스트(1) 팰린드롬 연결 리스트 https://leetcode.com/problems/palindrome-linked-list/description/ - 연결 리스트가 팰린드롬 구조인지 판별하라 풀이 1) 스택을 이용한 풀이 - 팰린드롬 여부를 판별하기 위해서는 앞뒤로 모두 추출할 수 있는 자료구조가 필요 - 연결 리스트를 먼저 스택에 복사해 넣은 다음 ,다시 연결 리스트를 앞에서부터 이동하면서 값을 조회하고, 스택은 pop()으로 추출하면서 뒤에서부터 값을 끄집어내어 함께 비교해본다. - 연결 리스트를 스택에 삽입//연결리스트에 스택을 삽입 ListNode node = head; while(node!=null) { stack.add(node.val); .. 이전 1 2 3 4 5 6 다음
