Brute force Study

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

힙을 이용하여 문제를 해결해야 하기 때문에 C++에서 제공하는 priority_queue를 사용할 수 있다.

절대값을 기준으로 비교하기 때문에 함수 객체를 만들고, 우선순위 큐의 comparator로 사용하여 문제를 해결하면 된다.

comparator의 구체적인 작동방식이 헷갈려서 우선순위 큐에서 비교자의 작동 방식에 대해 적어보겠다.

비교자의 작동 방식

비교자의 작동 방식을 더 구체적으로 이해해봅시다.

여기서 간주한다는 의미는, 우선순위가 낮다는 의미이다.

• std::less는 x < y가 true일 때 x가 y보다 작다고 간주합니다. 최대 힙에서 이는 큰 값이 높은 우선순위를 가지게 만듭니다.
  • x가 y보다 작을 때, 작다고 간주하는게 당연하다고 생각할 수 있다. 하지만 std::greater는 x가 y보다 클 때 x가 y보다 작다고 간주한다.
  • x값이 y값보다 작을 때 x의 우선순위가 낮다는 의미이다. 값이 작은게 우선순위가 낮다 --> 큰 값이 우선순위가 높다 --> 최대 힙
• std::greater는 x > y가 true일 때 x가 y보다 작다고 간주합니다. 최소 힙에서 이는 작은 값이 높은 우선순위를 가지게 만듭니다.
  
  • x값이 y값보다 클 때 x의 우선순위가 낮다는 의미이다. 값이 큰 게 우선순위가 낮다 --> 작은 값이 우선순위가 높다 --> 최소 힙

따라서, std::less를 사용하면 큰 값이 우선순위를 가지게 되어 최대 힙이 되고, std::greater를 사용하면 작은 값이 우선순위를 가지게 되어 최소 힙이 됩니다.

이 원리를 이해하고 함수 객체를 만들어 문제를 해결해보자. 

Code

함수 객체를 따로 만들긴 귀찮아서 람다 함수를 이용했다.

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, x;
    auto compare = [](int a, int b) { 
        if (abs(a) == abs(b))
			return a > b;
		else
			return abs(a) > abs(b);
    };
    priority_queue<int, std::vector<int>, decltype(compare)> absHeap(compare);
    cin >> n;
    while (n--) {
        cin >> x;
        if (x != 0) {
            absHeap.push(x);
        }
        else {
            if (absHeap.empty()) {
                cout << 0 << '\n';
            }
            else {
                cout << absHeap.top() << '\n';
                absHeap.pop();
            }
        }
    }
}

문제

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

시간 초과된 풀이

#include <iostream>
using namespace std;

int count;

int recursion(string s, int l, int r){
    ::count++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(string s){
    return recursion(s, 0, s.length() - 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    string temp;
    cin >> n;
    while (n--) {
        ::count = 0;
        cin >> temp;
        cout << isPalindrome(temp) << " " << ::count << '\n';
    }
}

• 함수에서 매개변수 값을 복사하는 시간으로 인해 시간초과 발생

해결 방법 : call-by-reference, 즉 값을 복사하는 것이 아니라, 참조하여 실행 시간을 줄인다

#include <iostream>
using namespace std;

int count;

int recursion(string &s, int l, int r){ // 문자열 참조
    ::count++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(string &s){ // 문자열 참조
    return recursion(s, 0, s.length() - 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    string temp;
    cin >> n;
    while (n--) {
        ::count = 0;
        cin >> temp;
        cout << isPalindrome(temp) << " " << ::count << '\n';
    }
}

문제

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

잘못 접근하기 좋은 풀이

문제에 나와있는 그대로 모든 원소를 삽입, pop을 해보겠다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Queue<Integer> queue = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) {
                queue.add(Integer.parseInt(st.nextToken()));
            }
            else {
                stack.add(Integer.parseInt(st.nextToken()));
            }
        }
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int x;
        for (int i = 0; i < m; i++) {
            x = Integer.parseInt(st.nextToken());
            for (int j = 0; j < n; j++) {
                if (arr[j] == 0) {
                    queue.add(x);
                    x = queue.poll();
                }
            }
            bw.write(x + " ");
        }
        bw.flush();
        bw.close();
    }
}

시간 복잡도(시간 제한을 통과 하지 못한 풀이)

O(nm)으로 시간 제한 1초를 넘어버린다. 불필요한 연산이 포함되어 있다.

-----------------------------------------

접근

• 스택 자료구조의 경우 삽입된 값을 다시 pop을 하기 때문에, 스택의 연산에 대해 신경쓰지 않아도 된다.
  • 예제 입력 2처럼 스택으로만 이루어 진 경우 삽입한 값이 그대로 return 된다
• 따라서 queuestack 내에서 queue가 존재하는 경우 queue의 연산이 작동하는 것을 생각해보자

예제 입력 1을 예시로 봐보자. 큐에는 (후단) [4, 1] (전단) 가 있다.

• 2를 삽입하면
  • 큐 : (후단) [1, 2] (전단),  4가 리턴된다
• 4를 삽입하면
  • 큐 : (후단) [2, 4] (전단), 1이 리턴된다
• 7를 삽입하면
  • 큐 : (후단) [4, 7] (전단),  2가 리턴된다

즉, 후단에서 pop한 값이 리턴되고, 삽입하려는 값은 큐의 전단에 삽입된다. 이를 통해 덱(Deque) 자료구조를 이용해야 겠다는 생각을 해야한다. pollLast()를 통해 리턴되는 값을 찾아야 한다

삽입하려는 값을 덱에 삽입한 후 삽입한 횟수 만큼 pollLast()를 해도 문제를 통과할 수 있고, 큐의 크기와 삽입하려는 수열의 길이의 대소관계를 비교해서 경우에 따라 코드를 세분화해도 된다(세분화 하는 경우 코드가 조금 길어진다).

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Deque<Integer> queue = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        int temp;
        for (int i = 0; i < n; i++) {
            temp = Integer.parseInt(st.nextToken());
            if (arr[i] == 0) {
                queue.add(temp);
            }
        }
        int m = Integer.parseInt(br.readLine());
        int queueSize = queue.size();
        if (queueSize == 0) {
            System.out.print(br.readLine());
            return;
        }
        else if (m > queueSize) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < queueSize; i++) {
                bw.write(queue.pollLast() + " ");
            }
            for (int i = 0; i < m - queueSize; i++) {
                bw.write(st.nextToken() + " ");
            }
        }
        else if (m == queueSize) {
            for (int i = 0; i < queueSize; i++) {
                bw.write(queue.pollLast() + " ");
            }
        }
        else {
            for (int i = 0; i < m; i++) {
                bw.write(queue.pollLast() + " ");
            }
        }
        bw.flush();
        bw.close();
    }
}