greentea31's Note

https://leetcode.com/problems/odd-even-linked-list/

풀이 과정

1 -> 2 -> 3 -> 4 -> 5 -> 6을 1 -> 3 -> 5 -> 2 -> 4 -> 6과 같이 홀수 번째 링크드 리스트 이후에 짝수 번째 링크드 리스트가 오게 하는 문제이다.

홀수번째 인덱스와 짝수번째 인덱스를 가리키는 변수를 반복문으로 바꿔가면서 문제를 해결하였다.

소스 코드

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        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

https://www.acmicpc.net/problem/5397

풀이 과정

알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표를 인식해서 사용자가 입력한 단어가 무엇인지 출력하는 문제이다.

현재 커서의 위치에 따라 알파벳이 추가되는 위치, 삭제되는 위치가 결정된다. 배열로 문자열을 다룬다면 커서의 위치가 문장의 중간일 때 문자의 생성, 삭제 연산이 O(N)이 되어 비효율적인 코드가 된다. 생성, 삭제 연산을 O(1)로 만들어 줘야 한다.

1. 현재 커서의 위치를 2개의 스택으로 표현하기

커서 왼쪽에 있는 문자들을 1번 스택, 커서 오른쪽에 있는 문자들을 2번 스택에 저장한다고 하자. 그렇다면 문자의 삽입은 1번 스택에 push 연산을 해주는 것과 같으므로 O(1), 문자의 삭제는 1번 스택에 pop 연산을 해주는 것과 같으므로 O(1)이다. 화살표 입력시 1번 스택과 2번 스택의 top 요소들을 바꿔가면서 커서 왼쪽 문자, 커서 오른쪽 문자들을 유지해주면 된다.

모든 입력을 받았으면, 2번 스택의 요소들을 1번 스택에 전부 옮기면 모든 문자가 s1에 저장되게 된다. 이를 출력하면 되는데, s1에 있는 것을 그대로 출력시 문자열이 거꾸로 출력되므로 s2에 다시 옮겨담은 후 출력해주어야 원하는 문자열을 얻을 수 있다.

2. 링크드 리스트로 문자열을 표현하기

링크드 리스트에서는 삽입, 삭제 연산이 O(1)에 이루어지므로 효율적으로 커서의 위치에서의 삽입, 삭제 연산을 수행할 수 있다.

소스 코드

스택

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--) {
        stack<char> s1;
        stack<char> s2;
        string L;
        cin >> L;
        for (char letter : L) {
            if (letter == '<') {
                if (s1.empty()) continue;
                s2.push(s1.top());
                s1.pop();
            } else if (letter == '>') {
                if (s2.empty()) continue;
                s1.push(s2.top());
                s2.pop();
            } else if (letter == '-') {
                if (s1.empty()) continue;
                s1.pop();
            } else {
                s1.push(letter);
            }
        }

        while(!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }

        while(!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }

        while(!s2.empty()) {
            cout << s2.top();
            s2.pop();
        }

        cout << '\n';
    }

    return 0;
}

https://leetcode.com/problems/swap-nodes-in-pairs/

풀이 과정

링크드 리스트를 2개씩 짝지어서 순서를 바꾸라는 문제이다.

중첩 함수 change를 재귀 함수로 사용하여 문제를 해결하였다.

소스 코드

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def change(prev, node):
            prev.next, node.next = node.next, prev
            if prev.next and prev.next.next:
                temp = prev.next
                prev.next = temp.next
                change(temp, prev.next)
        
        
        root = head
        if head and head.next:
            root = head.next
            change(head, head.next)
        return root

https://leetcode.com/problems/add-two-numbers/

풀이 과정

2개의 링크드 리스트를 더한 결과가 저장되어 있는 링크드 리스트의 head 포인터를 반환하는 문제이다.

carry를 이용해 받아올림을 구현하여 덧셈의 결과를 저장한 새로운 링크드 리스트를 만들었다.

소스 코드

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        root = head = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            sum_val = 0
            if l1:
                sum_val += l1.val
                l1 = l1.next
            if l2:
                sum_val += l2.val
                l2 = l2.next
            carry, val = divmod(sum_val + carry, 10)
            head.next = ListNode(val)
            head = head.next
        
        return root.next

https://www.acmicpc.net/problem/3273

풀이 과정

배열에서 두 요소의 합이 x가 되는 경우의 수를 구하는 문제이다.

O(N^2)인 완전 탐색방법으로 풀 수는 있겠지만 배열의 길이가 10만까지 들어오므로 O(N^2)로 처리하면 1초내로 연산이 다 불가능하고 시간 초과가 발생한다.

해결 방법은 크게 2가지가 있다.

1. 투 포인터

배열을 정렬한 뒤, left, right 포인터를 배열의 시작지점, 끝부분에 위치시킨다. 그 후 배열의 left번째 index의 원소 + right번째 index의 원소를 x와 비교한 후, x보다 작으면 left를 전진, 0보다 크면 right를 후진, x와 같으면 left, right를 전진, 후진 시킨 뒤 정답을 1 늘려주면 된다.

2. 배열로 자연수 존재 여부 판단

(x - 배열의 원소) 라는 수가 나온 적이 있는지를 체크하는 배열을 두고, 등장한 적이 있으면 합해서 x가 되므로 답의 개수를 하나씩 늘리면 된다.

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int x;
    cin >> x;

    sort(a, a+n);

    int left = 0;
    int right = n-1;
    int answer = 0;

    while (left < right) {
        int temp = a[left] + a[right];
        if (temp < x) {
            left++;
        } else if (temp > x) {
            right--;
        } else {
            left++; right--;
            answer++;
        }
    }

    cout << answer;

    return 0;
}

배열

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
bool exist[2000005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int x;
    cin >> x;

    int answer = 0;

    for (int i = 0; i < n; i++) {
        if (x-a[i] > 0 && exist[x-a[i]]) answer++; // 나온 적 있으면 정답 증가
        exist[a[i]] = true; // 나왔다고 처리
    }

    cout << answer;

    return 0;
}

https://leetcode.com/problems/reverse-linked-list/

풀이 과정

링크드 리스트를 뒤집는 문제이다.

링크드 리스트를 뒤집는 방법은 반복문으로 뒤집기, 재귀를 활용해서 뒤집기 2가지 방법이 가능하고 문제에서도 후속조치로 2가지 방법으로 모두 구현할 수 있냐고 묻고 있다.

재귀, 반복 2가지 방법으로 구현하였다.

소스 코드

재귀

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(node, prev=None):
            if not node:
                return prev
            next, node.next = node.next, prev
            return reverse(next, node)
        return reverse(head)

반복

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        rev = None
        answer = []
        while head:
            rev, rev.next, head = head, rev, head.next
        return rev

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

풀이 과정

왼쪽, 오른쪽으로 2칸까지 다른 건물에 의해 뷰가 가려지지 않을 때, 조망권이 확보되었다고 하는데 여러 건물의 높이가 주어졌을 때 조망권이 확보된 세대의 수를 구하는 문제이다.

각 건물에 대해 왼쪽으로 2칸, 오른쪽으로 2칸에 있는 모든 건물의 높이를 확인 후,  현재 건물 - 근처 가장 높은 건물의 높이를 정답에 더해주면 된다. 현재 건물이 더 낮아서 조망권이 확보되는 세대가 없다면, 아무 것도 더해주지 않으면 된다.

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T, garo, num;
    int number = 1;
    T = 10;
    while(T--) {
        int answer = 0;
        cin >> garo;
        vector<int> V(garo);
        for (int i = 0; i < garo; i++) {
            cin >> num;
            V[i] = num;
        }
        for (int i = 2; i < garo - 2; i++) {
            int temp = max({V[i-2], V[i-1], V[i+1], V[i+2]});
            if (V[i] > temp) answer += (V[i] - temp);
        }

        cout << '#' << number++ << ' ' << answer << '\n';
    }

    return 0;
}

https://leetcode.com/problems/palindrome-linked-list/

풀이 과정

링크드 리스트의 시작 포인터를 입력 받아서, 전체 링크드 리스트의 데이터가 팰린드롬인지 확인하는 문제이다.

팰린드롬이란 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬이라 한다.

문제를 해결하는 방법은 2가지가 떠오른다.

1. 링크드 리스트의 데이터들을 Deque에 전부 다 저장해놓고 Deque.popleft(), Deque.pop()을 해가면서 앞, 뒤 원소가 같은지 체크해가기.

2. 링크드 리스트를 2칸씩 뛰어가며 순회하는 fast, 1칸씩 뛰어가며 순회하는 slow를 두면 fast가 순회를 마치면 slow는 링크드 리스트의 절반까지 순회했을 것이라 기대할 수 있다. slow로 순회할 때 여태 순회했던 링크드 리스트의 원소를 역순으로 가지고 있는 새로운 링크드 리스트를 만들고, slow가 절반까지 순회했으면 절반 이후의 나오는 데이터들과 역순 링크드 리스트의 데이터가 같은지 아닌지를 확인하는 방법이 있다.

a -> b -> c -> b -> a의 링크드 리스트가 존재한다면,

fast: a -> c -> a

slow: a -> b -> c 순으로 순회가 진행되고 역순 링크드 리스트 c -> b -> a가 만들어진다. 전체 링크드 리스트의 중간부터의 링크드 리스트가 c -> b -> a 이고, 역순 링크드 리스트가 c -> b -> a이니 팰린드롬 문자열로 이루어진 링크드 리스트라고 판단할 수 있는 것이다.

소스 코드

deque 풀이

import collections

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        temp = collections.deque()
        while head.next is not None:
            temp.append(head.val)
            head = head.next
        temp.append(head.val)
        while len(temp) > 1:
            if temp.popleft() != temp.pop():
                return False
        return True

링크드 리스트 풀이

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        rev = None
        slow = fast = head
        
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
            
        if fast: # 길이가 홀수면
            slow = slow.next # 한칸 더
        
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        
        return not rev

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

풀이 과정

각 날짜별로 주식의 가격이 주어지는데, 싸게 사서 비싸게 팔때의 최대 이익을 구하는 문제이다.

각 날짜에서 현재 가격 - 가장 싸게 살수 있던 가격을 계산하면서 계산한 값중 가장 큰 값을 반환하면 된다.

소스 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = 10001
        profit = 0
        for price in prices:
            min_price = min(price, min_price)
            profit = max(profit, price - min_price)
        return profit

https://leetcode.com/problems/product-of-array-except-self/

풀이 과정

배열을 입력받고, 각 배열의 원소에 대해 자기 자신을 제외한 나머지 원소의 곱의 배열을 구하는 문제이다.

문제를 읽고 나서 바로 드는 생각이라면 배열의 전체 원소를 곱해놓고 저장한 뒤, 각 배열의 원소를 나누면서 저장하는 방법일 텐데 이 방법은 다음과 같은 2가지 문제 때문에 안된다.

1. 배열에 0이 포함되어 있는 경우

    [3, 3, 0, 3, 3]이 입력일 때의 정답은 [0, 0, 81, 0, 0]이어야 하는데 전체 원소의 곱을 구해놓고 각 원소로 나누면 3번째 원소를 처리하기가 곤란해진다. 0 / 0 을 처리할 수가 없기 때문이다.

2. 문제에서 나누기 연산을 금지한다고 조건을 걸었음

    나누기 말고 다른 방법으로 풀어주기를 문제에서 원하고 있다.

DP로 문제를 풀 때 흔히 사용되는 누적합 배열을 만들어서 이 문제를 해결할 수 있다. 이 문제의 경우엔 누적합이 아니라 누적곱이다.

길이가 n+1인 입력이 들어왔을 때, d[i] = 0부터 i-1번째까지의 누적곱, d2[i] = n부터 i+1번째까지의 누적곱이라고 하면, answer[i] = d[i] * d2[i]가 성립한다.

위의 식을 사용해서 문제를 해결하였다. 근데 문제에서 메모리 최적화를 후속 조치로 요구했기에, d[i], d2[i]를 선언하지 않고 출력을 위한 answer 리스트만 선언한 뒤 for문 2번 돌려서 문제를 해결하였다.

소스 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        answer = [1 for _ in range(len(nums))]
        product = 1
        for i in range(1, len(nums)):
            product *= nums[i-1]
            answer[i] *= product
        product = 1
        for i in range(len(nums)-2, -1, -1):
            product *= nums[i+1]
            answer[i] *= product
        return answer