greentea31's Note

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

풀이 과정

(, ), [, ]로 이루어진 문자열을 보고, 올바른 괄호 문자열인지 판단하고, 맞으면 문제의 조건에 맞게 괄호의 값을 출력하는 문제이다.

올바른 괄호 문자열 판단 자체는 )가 들어오면 스택탑이 (, ]가 들어오면 스택탑이 [인지 판단만 해주면 되는데 괄호의 값을 계산하기가 조금 까다롭다. 

(,나 [가 나오면 정답에 더해질 변수를 (초기값 1)을 문제의 조건에 맞게 2나 3을 곱해주고, )나 ]가 나오면 스택이 아닌 문자열에서 바로 앞에 있는 문자가 뭐였는지에 따라 변수를 정답에 더하고 변수를 나눌지, 아니면 그냥 변수를 나눌지 판단해주어야 한다.

예제로 주어진 문자열에서 정답에 더해질 변수 mul과 정답 변수 ans의 변화는 위의 그림과 같은데, 밑의 문제를 풀기 위한 아이디어와 동일한 아이디어를 사용해 괄호의 값을 구하게 된다.

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

올바른 괄호 문자열 판단의 아이디어, 쇠막대기 문제의 아이디어를 모두 활용해야 하는 문제였다.

소스 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    stack<char> st;
    string s;
    cin >> s;

    int ans = 0;
    int mul = 1;

    for (int i = 0; i <= s.length(); i++) {
        if (s[i] == '(') {
            mul *= 2;
            st.push('(');
        } else if (s[i] == '[') {
            mul *= 3;
            st.push('[');
        } else if (s[i] == ']') {
            if (st.empty() || st.top() != '[') {
                cout << 0;
                return 0;
            }

            if (s[i-1] == '[') ans += mul;
            st.pop();
            mul /= 3;
        } else if (s[i] == ')') {
            if (st.empty() || st.top() != '(') {
                cout << 0;
                return 0;
            }

            if (s[i-1] == '(') ans += mul;
            st.pop();
            mul /= 2;
        }
    }

    if (st.empty()) cout << ans;
    else cout << 0;

    return 0;
}

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

풀이 과정

배열에 R(뒤집기), D(첫 번째 수 버리기) 연산을 합쳐서 10만 번 이하로 시행할 때, 배열의 최종 결과를 구하는 문제이다.

배열을 뒤집는 연산은 O(N)이고, 첫 번째 수를 버리는 연산도 O(N)이다. 배열이 아닌 큐를 사용하면 첫번째 수를 버리는 연산을 pop()으로 O(1)만에 수행할 수 있으니 큐로 문제를 풀면 좋을 것 같다는 생각이 든다.

그런데 R을 인식했을 때 실제로 배열을 뒤집으면 시간 초과가 발생한다. 배열에 들어있는 수가 문제에서 주어진 최대 값인 10만 개가 주어졌다고 가정하고, 수행할 함수 p가 길이가 10만이라고 해보자. p가 전부 다 R로 꽉 차있어도 실제로 10만 번 뒤집을 필요까지는 없다. R이 2번 연속으로 나오면 아무 연산을 안 해도 2번 뒤집은 것이랑 같은 결과를 내기 때문이다.

따라서 RDRDRDRDRDRD..... RDRDRDRD 이런 식으로 나와서 R이 50000번 나오는 경우가 가장 시간이 오래 걸리는 경우일 것이다. 10만 크기의 배열을 5만 번 뒤집을 때 연산 횟수를 어림잡아 계산하면 10만 * 5만 = 50억인데, 시간제한 1초 내에 50억 번의 연산을 할 수는 없다.

R이 짝수번 연속으로 나올 때 연산을 무시해서 연산 횟수를 줄여도 시간 내에 문제를 해결할 수 없으니 이 문제를 시간 내에 해결하려면 뒤집기 연산이 나왔을 때 배열을 실제로 뒤집으면 안 된다.

배열이 뒤집힌 상태에서 첫 번째 수 버리기 연산을 하는 것은 배열의 마지막 수를 버리는 연산과 같다. 또한 배열이 뒤집힌 상태이면 배열을 역순으로 출력하고, 뒤집히지 않은 상태일 때 그대로 출력한다면 배열을 뒤집지 않고도 첫 번째 수 버리기 연산과 배열의 출력이 이루어 질 것이다.

따라서 배열이 뒤집혔는지를 판단하는 변수 하나를 두고, 변수의 값에 따라 첫번째 수를 버릴지, 마지막 수를 버릴지, 똑바로 출력할지, 반대로 출력할지를 판단해서 문제를 해결할 수 있다. 첫번째 수, 마지막 수를 O(1)로 버릴 수 있는 자료구조는 덱이므로 덱을 사용해서 문제를 해결하였다.

소스 코드

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

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

    int T;
    cin >> T;

    while(T--) {
        deque<int> DQ;
        int t = 0;
        bool errorFlag = false;

        string s;
        cin >> s;

        int num;
        cin >> num;

        string numbers;
        cin >> numbers;


        // 문자열 파싱후 덱에 삽입
        int parse_number = 0;
        for (char let : numbers) {
            if (isdigit(let)) {
                int parse = int(let) - 48;
                parse_number = parse_number * 10 + parse;
            } else {
                if (parse_number == 0) continue;
                DQ.push_back(parse_number);
                parse_number = 0;
            }
        }


        for (char let : s) {
            if (let == 'R') {
                t = (t+1) & 1;
            } else if (let == 'D') {
                if (DQ.empty()) {
                    cout << "error\n";
                    errorFlag = true;
                    break;
                }

                if (t == 0) {
                    DQ.pop_front();
                } else {
                    DQ.pop_back();
                }
            }
        }

        if (errorFlag) continue;

        cout << '[';
        int save_size = DQ.size();

        for (int i = 1; i <= save_size; i++) {
            if (t == 0) {
                cout << DQ.front();
                DQ.pop_front();
            } else {
                cout << DQ.back();
                DQ.pop_back();
            }
            if (i == save_size) break;
            cout << ',';
        }

        cout << "]\n";
    }

    return 0;
}

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

풀이 과정

양방향 순환 큐를 회전시키면서 원하는 수를 모두 뽑아내려면 필요한 최소 회전 횟수를 구하는 문제이다.

덱을 회전시키면서 원하는 숫자를 모두 뽑아가면서 회전을 몇번 시켰는지 구하면 된다. 근데 원하는 수가 큐의 앞에 있는 수를 뒤로 넘겨가면서 찾아야 빠른지, 뒤에 있는 수를 앞으로 넘겨가면서 빠른지 어떻게 구분이 가능할까?

판단하려면 일단 찾고자 하는 수가 덱의 몇번째 index에 있는지 알아야 한다. find(DQ.begin(), DQ.end(), num)으로 num이 존재하는 위치의 주소값을 받아오고 거기서 DQ.begin()을 빼서 index를 구해주자.

여기서 구한 index의 2배가 덱의 사이즈보다 작으면 앞에 있는 수를 뒤로 넘기는게 빠르고, 크면 뒤에 있는 수를 앞으로 넘기는게 빠를 것이다. 예시를 들면 0 1 2 3 4 5 6 7 8 9에서 라는 덱에서 4는 4번째 index에 있으므로 4*2 < 10 이므로 앞에서 찾는게 빠를 것이라고 생각할 수 있다.

5는 5번째 index에 있는데, 5*2 < 10이다. index의 2배가 덱의 사이즈랑 같은 경우에는 앞에서 찾던 뒤에서 찾던 횟수의 차이가 없으나, 뒤에서 찾도록 구현하였다.

소스 코드

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

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

    deque<int> DQ;

    int N;
    cin >> N;

    for (int i = 1 ; i <= N; i++) {
        DQ.push_back(i);
    }

    int M;
    cin >> M;

    int answer = 0;

    while(M--) {
        int num;
        cin >> num;
        int idx = find(DQ.begin(), DQ.end(), num) - DQ.begin(); // num의 index값
        while (DQ.front() != num) {
            if (2*idx < DQ.size()) {
                DQ.push_back(DQ.front());
                DQ.pop_front();
            } else {
                DQ.push_front(DQ.back());
                DQ.pop_back();
            }
            answer++;
        }
        DQ.pop_front();
    }

    cout << answer;

    return 0;
}

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

풀이 과정

탑이 왼쪽으로 레이저를 쏠 때, 먼저 만나는 높이가 쏜 탑보다 크거나 같은 탑에 레이저가 도달하는데, 각 탑에서 쏜 레이저는 어떤 탑에서 수신하는지 출력하는 문제이다.

스택에 탑의 높이와 인덱스를 넣는다. 다음 건물이 들어왔을 때, 건물의 높이보다 크거나 같은 높이가 나올때 까지 스택 탑의 원소를 비운 후, 스택 탑의 index를 출력하면 그 index의 탑 높이는 입력받은 건물의 높이보다 같거나 클 것이므로 레이저가 도달할 것임을 알 수 있다.

소스 코드

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

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

    stack<pair<int, int>> st;
    st.push(make_pair(100000001, 0));

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        int num;
        cin >> num;

        while (st.top().first < num) {
            st.pop();
        }

        cout << st.top().second << ' ';

        st.push(make_pair(num, i));
    }

    return 0;
}

https://leetcode.com/problems/valid-parentheses/

풀이 과정

(, {, [, ), }, ]의 괄호가 주어질 때 주어진 문자열이 올바른 괄호 문자열인지 판단하는 문제이다.

스택으로 풀 수 있는 유명한 문제이다. 여는 괄호가 나왔을 때는 그냥 스택에 넣고 닫는 괄호가 나왔을 때는 스택 탑이 동일한 종류의 여는 괄호인지 확인하고 맞으면 스택 pop, 아니면 올바른 괄호 문자열이 아니므로 False를 리턴해주면 된다.

모든 문자열을 살펴봤을 때 스택이 비어있어야 한다. 스택이 비어있지 않으면 닫히지 않은 괄호가 존재하는 것이므로 올바른 괄호 문자열이 아니다.

소스 코드

class Solution:
    def isValid(self, s: str) -> bool:
        st = []
        for letter in s:
            if letter in ['(', '{', '[']:
                st.append(letter)
            elif letter == ')':
                if st and st[-1] == '(':
                    st.pop()
                else:
                    return False 
            elif letter == '}':
                if st and st[-1] == '{':
                    st.pop()
                else:
                    return False 
            elif letter == ']':
                if st and st[-1] == '[':
                    st.pop()
                else:
                    return False 
        return True if not st else False

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next


class Stack:
    def __init__(self):
        self.last = None
    
    def push(self, item):
        self.last = Node(item, self.last)
    
    def pop(self):
        item = self.last.item
        self.last = self.last.next
        return item

출처

https://search.shopping.naver.com/book/catalog/32456486633

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