언제쯔음

코드를 보는 것보다 문제를 이해하여 직접 짜보는 것이 중요하다고 생각되어 이해하기 쉽도록 적어놓았습니다.

문제를 이해하는 것도 문제를 풀다보면 늘겠죠 ㅜㅜ

와 진짜 어렵다.

처음에 vector를 이용하여 Reverse해서 했다. 틀렸다. 시간 초과
오 그러면 자료구조사용하지 말고 string만 문자열로만 풀어볼까! 물론 reverse를 사용했다. 시간 초과

시간 초과~~ revrse때문이다. 란 생각을 했다.
revrser를 대신할 수 있는 것은 deque..

deque를 이용하여 출력했는데 답이 틀린다. 어..? 왜지 구렁텅이로 빠져간다.

www.acmicpc.net/board/view/25456

질문 게시판에 보면

• 빈 배열은 []로 출력해야 합니다. 아무것도 출력하지 않거나, error를 출력하거나, 무조건 원소를 하나 출력하고 시작하려고 하면 안 됩니다.

이 부분...!!!!

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;

    while(T--){
        deque<int> dq;
        string ins, data;
        int dataNumber;
        bool isReverse = false, isError = false;
        cin >> ins >> dataNumber >> data;

        // 수를 덱에 집어 넣기
        string temp = "";
        for(int i=0; i<data.size(); i++){
            if(data[i] == '[') continue;
            else if( '0' <= data[i] && data[i] <= '9'){
                temp += data[i];
            } else if( (data[i] == ',' || data[i] == ']') && temp != "" ){
                dq.push_back(atoi(temp.c_str()));
                temp = "";
            }
        }
        
        // 명령어 따라 처리하기.
        for(int i=0; i<ins.size(); i++){
            if(ins[i] == 'R') isReverse = !isReverse;
            else if(ins[i] == 'D'){
                if(dq.empty()){
                    isError = true;
                    break;
                }
                if(isReverse) dq.pop_back();
                else dq.pop_front();
            }
        }

        // 출력하기
        if(isError){
            cout << "error\n";
        } else if(dq.empty()){
            cout << "[]\n";
        } else if(isReverse){ // 거꾸로
            cout << "[";
            while(dq.size()>1){
                cout << dq.back() << ",";
                dq.pop_back();
            }
            cout << dq.back() << "]\n";
        } else{
            cout << "[";
            while(dq.size()>1){
                cout << dq.front() << ",";
                dq.pop_front();
            }
            cout << dq.front() << "]\n";
        }

    }
}

진짜 어렵ㄷ ㅜ

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

int N, M;
deque<int> dq;

int checkF(int temp){
    int count = 0;
    for(auto it=dq.begin(); it!=dq.end(); it++){
        if(*it == temp) return count;
        count++;
    }
}

int checkB(int temp){
    int count = 0;
    for(auto it=dq.end(); it!=dq.begin(); it--){
        if(*it == temp) return count;
        count++;
    }
}

int main(){
    int count = 0;
    cin >> N >> M;
    for(int i=1; i<=N; i++) dq.push_back(i);
    for(int i=0; i<M; i++){
        int temp;
        cin >> temp;

        if(temp == dq.front()) dq.pop_front();
        else if( checkF(temp) < checkB(temp) ){
            for(auto it=dq.begin(); it!=dq.end(); it++ ){
                if(temp == *it){
                    dq.pop_front();
                    break;
                } else{
                    dq.push_back(*it);
                    dq.pop_front();
                    count++;
                } 
            }
        } else {
            for(auto it=dq.begin(); it!=dq.end(); it--){
                if(temp == *it){
                    dq.pop_front();
                    break;
                } else{
                    dq.push_front(dq.back());
                    dq.pop_back();
                    count++;
                }
            }
        }
    }
    cout << count;
}

STL에서 지원해주는 Queue는 begin, end 함수가 없어서 iterator를 돌리지 못한다. Deque에는 있어서 가능하다.

그 사실을 이번 문제에서 알게 되었다.

또한 Visual Stdio Code를 사용하여 문제를 사용하고 있었는데 전역변수를 어떻게 보는지 잘 몰랐다.

Watch에 변수를 추가하여 확인가능했다. 새로운 사실!

자료구조 List로 구현하면 되겠다라고 생각했다. 그리고 쉬운 문제라고 생각했는데 꽤 오래 걸렸다. 자괴감 ON

처음에는 아예 문자열 자체를 벡터에 넣어보기도 하고 string으로 하나하나 따라서 구현하다가 이상함을 느꼈고 시간은 1시간이 흘러있었다. 다시 노트에 끄적여보니 커서가 생각났다. 이거 그냥 편집기와 동일한 것 같다!란 생각

그래서 커서를 구현하려니까 이터레이터가 생각났다.
문제는 처음에 리스트에 아무것도 없어서 지정해봤자. 이터레이터가 가리키는 곳이 없다.?
그래서 커서를 따로 내가 int형으로 구현해서 index로 가리켜주자.란 생각으로 구현했다.

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

int main(){
    int T;
    cin >> T;

    while(T--){
        vector<char> v;
        int cusor = 0;
        string s;
        cin >> s;

        for(int i=0; i<s.length(); i++){
            if(s[i] == '<'){
                if(v.size() != 0) cusor--;
            } else if(s[i] == '>'){
                if(cusor < v.size() ) cusor++;
            } else if(s[i] == '-'){
                if(cusor != 0){
                    auto it = v.begin();
                    v.erase(it+cusor-1);
                }
            } else{
                v.insert(v.begin()+cusor,s[i]);
                cusor++;
            }
        }
        for(auto it = v.begin(); it!=v.end(); it++)
            cout << *it;
        cout << "\n";
    }

음! 안된다! 런타임 에러가 뜬다.뭐가 문제인지 모르겠다.
그래서 수정했다.

#include "iostream"
#include <list>
using namespace std;

int main(){
    int T;
    cin >> T;

    while(T--){
        list<char> v;
        int cursor = 0;
        string s;
        cin >> s;

        for(int i=0; i<s.length(); i++){
            if(s[i] == '<'){
                if(v.size() != 0) cursor--;
            } else if(s[i] == '>'){
                if(cursor < v.size() ) cursor++;
            } else if(s[i] == '-'){
                if(v.size() != 0){
                    auto it = v.begin();
                    for(int i=0; i<cursor-1; i++) it++;
                    v.erase(it);
                }
            } else{
                auto it = v.begin();
                for(int i=0; i<cursor; i++) it++;
                v.insert(it,s[i]);
                cursor++;
            }
        }
        for(auto it = v.begin(); it!=v.end(); it++)
            cout << *it;
        cout << "\n";
    }
}

또 런타임 에러가 난다! 코드가 더럽다. 복잡하고 억지스럽다.

#include "iostream"
#include <list>
using namespace std;

int main(){
    ios::sync_with_stdio(NULL);
    cin.tie(0);
    int T;
    cin >> T;

    while(T--){
        list<char> v;
        auto cursor = v.begin();
        string s;
        cin >> s;

        for(int i=0; i<s.length(); i++){
            if(s[i] == '<'){
                if(v.begin() != cursor) cursor--;
            } else if(s[i] == '>'){
                if(cursor != v.end() ) cursor++;
            } else if(s[i] == '-'){
                if(cursor != v.begin()){
                    cursor--;
                    cursor = v.erase(cursor);
                }
            } else{
                cursor = v.insert(cursor,s[i]);
                cursor++;
            }
        }
        for(auto it = v.begin(); it!=v.end(); it++)
            cout << *it;
        cout << "\n";
    }
}

이터레이터를 사용하는 방법을 알게되었다. 지정 안 되었던 이터레이터를 삽입할 때 지정해주고, 제거할 때 도 지정해준다. 이런 식으로 코드가 훨씬 깔끔하다.
숙제가 남았다. int cursor로 어떻게 구현해서 백준 문제를 통과할 수 있을까?

#include "iostream"
using namespace std;

int dp[41] = { 0, 1 };

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    int data[T];
    int max = -5;
    for(int i=0; i<T; i++){
        cin >> data[i];
        if( data[i] > max){
            max = data[i];
        }
    }

    for(int i=2; i<=max; i++){
        dp[i] = dp[i-1]+dp[i-2];
    }

    for(int i=0; i<T; i++){
        if(data[i] == 0) cout << "1 0\n";
        else if(data[i] == 1) cout << "0 1\n";
        else cout << dp[data[i]-1] << " " << dp[data[i]] << "\n";
    }
}

반복문으로 원하는 값까지 더해서 출력하는 것이 빠른 것 같다고 생각이 든다.

재귀 호출, DP, 반복문 모두 구현해서 각 속도를 확인을 해보긴 해야겠다.

많이 틀렸고, 시간을 단축시켰다. 시간 단축시킨 경험을 남기려고 글을 쓴다.

알고리즘 분류에 이분 탐색이라고 적혀있었고, 문제만 읽어봐도 숫자로 된 것은 직접적으로 찾아들어가 반환해주면 된다.
문제는 string으로 된 포켓몬 이름들을 찾아 들어가는 것이 문제였다. 정답 비율 보고 이건 순차적으로 찾으면 바로 퇴짜겠구나도 감이 올 것이고, 이분 탐색으로 푸는 것이 정당했다. 어찌 되었든 간에 이분 탐색이다!!!!!!!!
참고로 다른 사람들은 Map으로 푸는 것을 선호하는 것 같았다.

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

bool compare(pair<int, string> a, pair<int, string> b){
    return a.second < b.second;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    int n, m;
    vector<pair<int, string>> pocketmonName;
    cin >> n >> m;
    string numbers[n];
    string temp;
    for(int i=1; i<=n; i++){
        cin >> temp;
        pocketmonName.push_back(make_pair(i, temp));
        numbers[i-1] = temp;
    }
    sort(pocketmonName.begin(), pocketmonName.end(), compare); // 포켓몬 이름으로 정렬
    for(int i=0; i<m; i++){
        cin >> temp;
        if(temp[0] >= '0' && temp[0] <= '9'){
            int t = stoi(temp);
            cout << numbers[t-1] << "\n";
        } else{
            int start = 0;
            int last = n-1;
            int mid;
            while(start <= last){
                mid = (start+last)/2;
                if(temp == pocketmonName[mid].second){
                    cout << pocketmonName[mid].first << "\n";
                    break;
                } else if(temp > pocketmonName[mid].second){
                    start = mid+1;
                } else{
                    last = mid-1;
                }
            }
        }
    }
}

벡터에 int, string 순으로 하고 compare 함수를 만들어 string 기준으로 정렬을 했다. 느렸다. 248ms가 나온 코드가 이거다.

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

int n, m;
vector<pair<string, int>> pocketmonName;

int inputString(string &temp){
    int start = 0;
    int last = n-1;
    int mid;
    while(start <= last){
        mid = (start+last)/2;
        if(temp == pocketmonName[mid].first){
            return pocketmonName[mid].second;           
        } else if(temp > pocketmonName[mid].first){
            start = mid+1;
        } else{
            last = mid-1;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    cin >> n >> m;
    string numbers[n];
    string temp;
    for(int i=1; i<=n; i++){
        cin >> temp;
        pocketmonName.push_back(make_pair(temp, i));
        numbers[i-1] = temp;
    }
    sort(pocketmonName.begin(), pocketmonName.end()); // 포켓몬 이름으로 정렬
    for(int i=0; i<m; i++){
        cin >> temp;
        if(temp[0] >= '0' && temp[0] <= '9'){
            int t = stoi(temp);
            cout << numbers[t-1] << "\n";
        } else{
            cout << inputString(temp) << "\n";
        }
    }
}

벡터의 int , string 순서를 바꿔서 정렬했다. 속도는 128ms로 나왔다.
이 문제를 풀면서 신기했던 것은 문자를 비교할 때

이런 식으로 값이 크고 다른 것을 알 수 있다.< 문자열을 비교할 때 "사전에 먼저 나오면 작다"
그래서 else if(temp > pocketmonName[mid].first) 이런 식으로 비교가 가능하다.
또 하나 신기했던 것은 숫자와 문자를 받을 때 확인 방법이다.
숫자는 앞자리가 숫자면 숫자라

if(temp[0] >= '0' && temp[0] <= '9')
이런 식으로 확인하면 된다. 그리고 stoi로 문자 자체를 int로 바꿔 출력하면 된다.

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, num, k = 0, temp, count = 0;
    pair<int, int> t;
    cin >> n;
    while(n--){
        queue<pair<int,int>> q;
        priority_queue<int> qq;
        count = 0;
        cin >> num >> k;

        for(int i=0; i<num; i++){
            cin >> temp;
            if(i == k) q.push(make_pair(temp, 1));
            else q.push(make_pair(temp, 0));
            qq.push(temp);
        }

        if(q.size() == 1) cout << "1\n";
        else {
            while(!q.empty()){
                t = q.front();
                q.pop();
                if(qq.top() != t.first ) q.push(t);
                else{
                    qq.pop();
                    count++;
                    if(t.second == 1){
                        cout << count <<"\n";
                        break;
                    }
                }
            }
        }
    }
}

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

class Solution {    public int solution(int[] priorities, int location) {
        int answer = 0;

        Queue<print_info> prior_Q = new LinkedList<print_info>();
        Iterator<print_info> it;

        // Queue 생성
        for (int i = 0; i<priorities.length; i++)
            if(i != location)
                prior_Q.add(new print_info(priorities[i], false));
            else
                prior_Q.add(new print_info(priorities[i], true));

        print_info A;
        boolean check = true;
        while(!prior_Q.isEmpty()) {
            check = true;
            A = prior_Q.poll();
            it = prior_Q.iterator();
            while (it.hasNext()) {
                if (A.data < it.next().data) {
                    check = false;
                    break;
                }
            }
            // check가 true라면 큐 안 요소 중에서 A가 크다는 것을 의미함
            if (check && A.flag){
                answer++;
                break;
            } else if(check) {
                answer++;
            } else {
                prior_Q.add(new print_info(A.data, A.flag));
            }

        }
        return answer;
    }
    static class print_info {
        int data;
        boolean flag;
        public print_info(int data, boolean flag){
            this.data = data;
            this.flag = flag;
        }
    }
}

c++은 2020.4.24에 짠 코드이고, Java는 대략 2월 초중에 짠 코드이다.
c++의 경우 두개의 큐, queue와 우선순위 queue를 사용하여 짠 코드이다. 방금 짜서 그런지 c++이 더 간결하다고 생각이 든다.
Java로 짠 2월달 아기는 다시 읽을 때 뭐지? 이 생각을 조금 했다. ㅋㅋㅋㅋ
다시 보니 c++과 동일하게 data와 flag를 가져 내가 원하고자하는 수를 찾고자했다.
다른 점은 우선 순위 큐를 사용하지 않고 이걸 queue를 한 바퀴 돌아서 값이 제일 큰지 확인한다. 그 다음 제일 크고 flag가 true이라면 answer값을 반환한다.

사실 c++로 짜면서도 큐를 한 바퀴 돌까 생각했는데 도무지 귀찮아서 그럴 생각이 들지 않았는데 2월달에 난 귀찮아도 일단 풀었다. 대단하다 ! 굿굿

혹시나 싶어 sort를 사용하여 제출 당연 실패

메모리 초과가 뜨길래 내 머리로는 안 된다는 것을 깨닫기 시작했고 검색을 했다.
입력되는 수의 제한이 10000이라는 것을 이용하여 정렬을 하지 않고

배열을 100001칸으로 선언하여 index값으로 출력하는 방식으로 푸는 분을 보고 신기했다.

배열에 값을 넣지 않으니 시간 복잡도에서 이득을 보고 문제가 풀렸다. 정렬을 이렇게 생각해도 된다는게 진짜 신기했다.
잘 배워 갑니다.