Java/알고리즘 (51) 썸네일형 리스트형 [자바 알고리즘 인터뷰] 9장 큐,스택 (5) 스택을 이용한 큐 구현 https://leetcode.com/problems/implement-queue-using-stacks/ - 스택을 이용해 다음 연산을 지원하는 큐를 구현하라. push(x) : 엘리먼트 x를 큐 마지막에 삽입한다. pop() : 큐 처음에 있는 엘리먼트를 제거한다. peek() : 큐 처음에 있는 엘리먼트를 조회한다. empty() : 큐가 비어 있는지 여부를 리턴한다. 풀이 1) 스택 2개 사용 - 가장 먼저 삽입된 아이템을 끄집어 내야 하는데, 스택은 아무리 추가, 삭제를 반복해도 가장 가장 마지막에 삽입된 아이템만 넣고 빼기를 반복하므로 하나의 스택만을 이용해서는 풀 수 없다. - 이 문제를 풀기 위해서는 2개의 스택이 필요하다. - 특히 추출시 pop()과 조회 시 peek()는 결.. [자바 알고리즘 인터뷰] 9장 스택,큐 (4) 큐를 이용한 스택 구현 https://leetcode.com/problems/implement-stack-using-queues/ - 큐를 이용해 다음 연산을 지원하는 스택을 구현하라. push(x) : 엘리먼트 x를 스택에 삽입한다. pop() : 스택의 첫 번째 엘리먼트를 삭제한다. top() : 스택의 첫 번째 엘리먼트를 가져온다. empty() : 스택이 비어있는지 여부를 리턴한다. 풀이 1) push()할 때 큐를 이용해 재정렬 - 큐를 선언 하고 큐 추상 자료형의 기본 연산으로 구현 - 가장 복잡한 부분은 push()이다. - 엘리먼트를 삽입한 후에 방금 삽입한 엘리먼트를 맨 앞에 두는 상태로 전체를 재정렬하면 나머지는 기본적인 큐 연산으로 쉽게 구현이 가능하다. class MyStack { //큐.. [자바 알고리즘 인터뷰] 9장 스택, 큐 (3) 일일 온도 https://leetcode.com/problems/daily-temperatures/description/ - 매일의 온도 리스트 temperatures를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라 풀이 1) 스택 값 비교 - 현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교해서, 더 높다면 다음과 같이 스택의 값을 pop()으로 꺼내고, 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 업데이트 - 그리고 현재 인덱스를 다시 스택에 삽입한다. //현재 온도가 스택에 있는 온도보다 높다면 꺼내서 결과를 업데이트 while(!stack.isEmpty() && temperat.. [자바 알고리즘 인터뷰] 9장 스택,큐(2) - 중복 문자 제거 https://leetcode.com/problems/remove-duplicate-letters/description/ - 중복된 문자를 제외하고 사전식 순서(Lexicographical Order)로 나열하라 풀이 1) 재귀를 이용한 분리 사전식 순서(Lexicographical Order) - 사전에서 가장 먼저 찾을 수 있는 순서 - bcabc에서 중복 문자를 제외하면 사전에서 가장 먼저 찾을 수 있는 문자열은 abc가 된다. - ebcabc가 입력값이라면 결과는 eabc가 된다. -> e 문자 자체는 해당 문자열 내에서는 사전에서 가장 뒤에 있지만 e는 입력값에서 딱 한번만 등장하고, a,b,c는 뒤이어 등장하기 때문에 e의 위치를 변경할 수 없기 때문이다. - ebcabce라면 .. [자바 알고리즘 인터뷰] 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) { //임시 변수를 이용해 값만 교환.. 이전 1 2 3 4 5 6 7 다음
