greentea31's Note

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

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

//struct NODE {
//    struct NODE *prev, *next;
//    int data;
//};

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;

void traverse() {
    int cur = nxt[0];
    while(cur != -1) {
        cout << dat[cur] << ' ';
        cur = nxt[cur];
    }
    cout << '\n';
}

void insert(int addr, int num) {
    dat[unused] = num;
    pre[unused] = addr;
    nxt[unused] = nxt[addr];
    if (nxt[addr] != -1) pre[nxt[addr]] = unused;
    nxt[addr] = unused;
    unused++;
}

void erase(int addr) {
    nxt[pre[addr]] = nxt[addr];
    if (nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

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

    fill(dat, dat+MX, -1);
    fill(pre, pre+MX, -1);
    fill(nxt, nxt+MX, -1);


    return 0;
}

출처

https://blog.encrypted.gg/932?category=773649 

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

https://leetcode.com/problems/array-partition/

풀이 과정

배열을 입력 받고, 배열의 원소를 2개씩 짝지은 후, 짝에서 작은 값들의 합이 가질 수 있는 최대값을 출력하는 문제이다.

[1, 3, 2, 6, 4, 5]을 생각해보자. 1은 어떤 원소랑 짝지어지던 짝의 작은 값은 자신이 될 것이고, 합의 최대값을 만들기 위해서는 다른 수중 가장 작은 수인 2를 가져오는게 맞을 것이다.

3도 마찬가지다 1, 2가 이미 짝지어졌으니 6 4 5중 어떤 수랑 짝이 지어지던 짝의 작은 값은 자신이 될 것이고, 합의 최대값을 만들기 위해서는 남은 수중 가장 작은 4랑 묶이는게 맞을 것이다.

이런식으로 생각하다보면 그냥 배열을 오름차순 정렬한 다음에 앞에서 부터 2개씩 짝짓고, 짝의 작은 값을 다 더하면 합의 최대값이 될 것이라고 판단할 수 있다. 짝도 지을 필요가 없다. 정렬후 짝수번째 index의 원소의 합을 구해주면 된다.

소스 코드

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        answer = 0
        nums.sort()
        for i in range(0, len(nums), 2):
            answer += nums[i]
        return answer

좀 더 효율적이고 짧은 코드

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2])

https://leetcode.com/problems/3sum/

풀이 과정

배열에서 합이 0을 이루는 3개의 원소를 출력하는 문제이다.

가장 간단하게 생각하면 완전 탐색으로 O(N^3)으로 풀 수 있을 것이다. 하지만 완전 탐색으로 풀이하면 Time Out으로 풀이에 실패한다. 더 빠르게 문제를 해결할 수 있는 효율적인 코드를 찾아야 한다.

정렬후 투 포인터 알고리즘을 사용하면 문제를 해결할 수 있다. 우선 정렬을 한 후, 각 배열의 원소를 축으로 한번씩 둔 다음, 축의 바로 다음 원소를 left 포인터, 배열의 마지막 원소를 right 포인터로 둔 뒤, 합이 0보다 작으면 left 포인터를 전진, 0보다 크면 right 포인터를 후진 시키는 식으로 O(N^2)만에 문제를 해결할 수 있다.

소스 코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        
        for i, a in enumerate(nums):
            # same value as before so continue
            if i > 0 and a == nums[i-1]:
                continue
                
            l,r = i+1, len(nums)-1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -=1
                elif threeSum < 0:
                    l+= 1
                else:
                    res.append([a,nums[l],nums[r]])
                    l += 1
                    while nums[l] == nums[l-1] and l<r:
                        l+= 1
        return res

https://school.programmers.co.kr/learn/courses/30/lessons/64065

풀이 과정

튜플을 표현하는 집합을 문자열로 받아서 튜플을 출력하는 문제이다.

튜플은 순서가 다르면 원소가 같더라도 다른 튜플이지만, 집합은 순서가 달라도 같은 집합이다. 한 튜플을 표현하는 집합은 다양한 순서로 입력받을 수 있는데 어떻게 하나의 튜플을 식별이 가능한가?

어떤 순서로 들어와도 동일하게 처리하기 위해서 집합을 길이가 짧은 순서대로 오름차순 정렬을 해버리면 된다.

{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}가 어떤 튜플을 가리키는지 알기 위해서는 길이 순서대로 정렬을 하면,

{2}, {2, 1}, {1, 2, 3}, {1, 2, 4, 3}이 되는데 숫자가 추가된 순서대로 튜플에 원소를 넣어주면 집합이 어떤 튜플을 표현하는지 쉽게 알 수 있다. 앞에 표현한 집합은 (2, 1, 3, 4) 튜플을 표현함을 알 수 있다.

문자열로 들어온 집합을 어떻게 처리할지는 정답이 없지만 [[1, 2, 3], [2, 1], [1, 2, 4, 3], [2]]와 같은 2차원 리스트로 받은 후 길이 순으로 정렬해서 문제를 해결하게끔 구현하였다.

소스 코드

def solution(s):
    answer = []
    temp = [[]]
    temp_num = 0

    for index in range(len(s)-1):
        if s[index].isnumeric():
            temp_num *= 10
            temp_num += int(s[index])
        elif s[index] == ',':
            if s[index-1] == '}' and s[index+1] == '{':
                continue
            temp[-1].append(temp_num)
            temp_num = 0
        elif s[index] == '}':
            temp[-1].append(temp_num)
            temp_num = 0
            temp.append([])

    del temp[-1]
    temp.sort(key=len)

    for i in temp:
        for j in i:
            if j not in answer:
                answer.append(j)
    return answer