자료구조와 알고리즘 - 배열과 리스트(2)

---

1. 배열 - Trappingg Rain Water 풀이

-문제출처:https://leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

- > 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.
- https://www.geeksforgeeks.org/trapping-rain-water/ 참고

java

// 리트코드 빗물 트래핑
class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int n = height.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            while ((!stack.isEmpty())
                   && (height[stack.peek()] < height[i])) {
                int pop_height = height[stack.peek()];
                stack.pop();
                if (stack.isEmpty()) {
                    break;}
                int distance = i - stack.peek() - 1;
                int min_height = Math.min(height[stack.peek()],height[i])- pop_height;
                ans += distance * min_height;
            }
            stack.push(i);
        }
        return ans;
    }
}

python

# 리트코드 빗물 트래핑
# 높이가 올라가지 않을 때 모든 높이를 스택에 저장
"""왼쪽부터 탐색을 하며 높아지는 지점 a를 만나면
a보다 높은 지점의 좌표가 나오기 전까지 스택에서 위치를 꺼낸다. 
그리고 꺼낸 위치와 a의 좌표를 이용해 더할 물의 양을 구한다."""
class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        volume = 0
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                if len(stack) == 0:
                    break
                distance = i - stack[-1] - 1
                water = min(height[i], height[stack[-1]]) - height[top]
                volume += distance * water
            stack.append(i)
        return volume

 

2. 리스트 - Odd Even Linked List

-문제출처: https://leetcode.com/problems/odd-even-linked-list/

Odd Even Linked List - LeetCode

- > 연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라 . 공간 복잡도 O(1), 시간복잡도 O(N)에 풀이하라

java

// 리트코드 홀짝 연결 리스트

public class oddEvenList {
    public ListNode oddEvenList(ListNode head) {
    	if (head == null) { 
    			return head;
    		}

        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;

        while (odd.next != null && even.next != null) {
            odd.next = odd.next.next;
            even.next = even.next.next;
            odd = odd.next;
            even = even.next;
        }

        odd.next = evenHead;
        return head;  
    }
}

python

# 홀짝 연결 리스트
"""
홀/짝 각 노드를 구성한 다음, 홀수 노드의 마지막을 짝수와 연결한다.
"""
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        odd=head
        even=head.next
        even_head=head.next
        # 반복하면서 홀짝 노드 처리
        while even and even.next:
            odd.next,even.next=odd.next.next,even.next.next
            odd,even=odd.next,even.next
        #홀수 노드의 마지막을 짝수 헤드와 연결
        odd.next=even_head
        return head

 

+ next /iter 함수

iter (호출가능한 객체, 반복을끝낼값) 
-  객체의 __iter__ 메서드를 호출
- 반복을 끝낼 값을 지정하면 특정 값이 나올 때 반복을 끝냄

next(반복가능한객체, 기본값)
- 반복 가능 객체의 다음 요소 반환.
- 반복할 수 있을 때는 해당 값을 출력하고, 반복이 끝났을 때는 기본값을 출력