JArchive 프로그래밍 일기

문제

회전하는 큐 백준 1021

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;
​
int n, m; // 큐의 크기, 뽑아내려는 개수.
int target;
deque<int> de;
int cnt = 0;
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    cin >> n >> m;
​
    for(int i = 1; i <= n; i++){
        de.push_back(i); // 1 부터 n까지 숫자 넣기
    }
​
    for(int i = 0; i < m; i++){ // 찾기 시작
​
        cin >> target;
​
        // 타겟의 인덱스를 찾아낸다.
        int targetIdx = 0;
        for(int i = 0; i < de.size(); i++){
            if(de[i] == target){
                targetIdx = i;
                break;
            }
        }
​
        if(targetIdx > de.size()-targetIdx){
            while(1){
                if(de.front() == target) {
                    de.pop_front();
                    break;
                }
                de.push_front(de.back());
                de.pop_back();
                cnt++;
            }
        }
        else{
            while(1){
                if(de.front() == target) {
                    de.pop_front();
                    break;
                }
                de.push_back(de.front());
                de.pop_front();
                cnt++;
            }
        }
    } // for
​
    cout << cnt;
    return 0;
}

리뷰

문제를 주의 깊게 안읽어서 고생했다.

일단 타겟이 deque에서 몇 번째 인덱스인지 찾아내는 것이 중요하다. 

그러면, 2번 연산을 연속 해서 뽑아내는게 빠른지 3번 연산을 해서 뽑아내는게 빠른지 판단할 수 있다.

1번 연산은 pop_front()이다.
2번 연산은 front()를 push_back()하고, pop_front() 한다.
3번 연산은 back()을 push_front()하고, pop_back() 한다.

돌리다가 front()가 뽑아낼 타겟이라면 1번 연산 pop_front() 하고 break 하면 된다.

원소를 뽑아내는게 반드시 front()와 비교해서 pop_front() 해야하는데.

오른쪽으로 돌리다가 pop_back()하는 바람에 계속 틀리게 풀고 있었다.

다시 풀어봐야 할 문제.

문제

탑 백준 2493

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;
​
int main() {
​
    int K, height;
    stack<pair<int,int> > s; // <인덱스, 높이>를 저장한 스택
​
    scanf("%d", &K);
​
    for(int i = 1; i <= K; i++){
​
        scanf("%d", &height);
​
        while(!s.empty()){
            if(s.top().second > height){ // 수신탑 발견한건지 검사
                printf("%d ", s.top().first); // 발견한 수신탑의 인덱스 출력 
                break;
            }
            s.pop(); //수신탑 찾을 때 까지 꺼낸다 
        }
​
        if(s.empty()){ // 수신탑을 못찾은 경우 0
            printf("0 ");
        }
        s.push(make_pair(i, height)); // 탑의 인덱스와 높이를 저장 
    }
​
    return 0;
}

리뷰

헷갈렸는데. 검색을 통해 탑의 인덱스를 저장해야 된다는 것을 알고 코드를 고쳤다.

스택에 (인덱스, 탑 높이) 쌍으로 par를 저장한다.

6 입력

- 스택이 비었으니까 0을 출력하고. 자기자신 (인덱스 1, 높이6)을 스택에 push

현재 스택에 (1, 6) 들어있음

9 입력

- 자신보다 높은 높이가 나올때 까지 pop한다. 6이 제거된다. 스택이 비게된다.

그리고 자기자신 (인덱스 2, 높이9)를 스택에 push

현재 스택에 (2, 9)들어있음

5 입력

- 자신보다 높은 높이를 찾는데, 9가 들어있다.

9의 인덱스인 2를 출력. 그리고 자기자신 (인덱스 3, 높이 5)를 스택에 push

현재 스택에 (2,9), (3,5) 가 들어있음. top은 방금 넣은 5다.

7 입력

- 자신보다 높은 높이 나올때 까지 pop한다. 5가 제거되고 9를 발견하게 된다.

9의 인덱스인 2를 출력. 그리고 자기자신 (인덱스 4, 높이 7) 을 스택에 push

현재 스택에 (2,9),(4,7) 이 들어있음. top은 방금 넣은 7이다.

4입력

- 자신보다 높은 높이인 7이 현재 스택의 top이다.

7의 인덱스인 4를 출력. 그리고 자기자신 (인덱스 5, 높이4)를 스택에 push

현재 스택에 (2,9),(4,7), (5,4) 이 들어있음.

문제

큐2 백준 18258

맞은 코드

#include <bits/stdc++.h>
using namespace std;
​
int N, num;
char order[10];
queue<int> q;
​
int main(void) {
  
    scanf("%d", &N);
​
    while(N--){
​
        scanf("%s", order);
​
        if(!strcmp(order, "push")){
            scanf("%d", &num);
            q.push(num);
        }
        if(!strcmp(order, "pop")){
            if(q.empty()){
                printf("-1\n");
            }else{
                printf("%d\n", q.front());
                q.pop();
            }
        }
        if(!strcmp(order, "size")){
            printf("%d\n", q.size());
        }
        if(!strcmp(order, "empty")){
            if(q.empty()){
                printf("1\n");
            }else{
                printf("0\n");
            }
        }
        if(!strcmp(order, "front")){
            if(q.empty()){
                printf("-1\n");
            }else{
                printf("%d\n", q.front());
            }
        }
        if(!strcmp(order, "back")){
            if(q.empty()){
                printf("-1\n");
            }else{
                printf("%d\n", q.back());
            }
        }
    }
​
    return 0;
}

리뷰

까다로운 문제는 아니었는데.

string 비교와 cin/cout을 하니깐 시간초과가 났었다.

Strcmp() 함수로 문자열 비교를 하고, 입출력은 scanf/printf를 쓰니깐 정답이 떴다.

문제

요세푸스 문제 백준 1158

list 를 이용한 코드

#include <bits/stdc++.h>
using namespace std;
​
int N; // 초기 인원
int K; // 제거할 차례
list<int> L;
list<int> ::iterator cur;
​
void input(){
​
    cin >> N >> K;
​
    for(int i = 1; i <= N; i++){
        L.push_back(i);
    }
​
    cur = L.begin(); // 위치 참조자
​
    cout << '<';
​
    while(L.size() > 1){
​
        // K만큼 이동
        for(int i = 0; i < K-1; i++){
            cur++;
            if(cur == L.end()){
                cur = L.begin();
            }
        }
​
        cout << *cur << ", ";
​
        cur = L.erase(cur);
        if(cur == L.end()){
            cur = L.begin();
        }
    }
​
    cout << *cur << '>';
​
}
​
int main(void) {
​
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    input();
    return 0;
​
}

queue를 이용한 코드

#include <bits/stdc++.h>
using namespace std;
​
int N; // 사람 수
int K; // 제거 순서
queue<int> q;
vector<int> answer; // 제거순서의 사람을 저장한다. 
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    cin >> N >> K;
​
    for(int i = 1; i <= N; i++){
        q.push(i);
    }
​
    while(!q.empty()){
​
        int cnt = K-1;
​
        while(cnt--){
            q.push(q.front());
            q.pop();
        }
        answer.push_back(q.front()); // 제거한 숫자를 저장함 
        q.pop();
    }
​
    cout << '<';
    for(int i = 0; i < answer.size()-1; i++){ // 포맷에 맞춰 답 출력 
        cout << answer[i] << ", ";
    }
    cout << answer[answer.size()-1] << '>';
    return 0;
}

리뷰

queue를 이용해 푸는 것이 좀 더 직관적인 것 같다.

3번째 사람을 제거하려면, 2번 push, pop 한 후에, 정답 배열에 사람 숫자를 저장하고 pop 만 한다.

문제

키로거 백준 5397

"맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;
​
int tc; // 테스트케이스
string inputStr; // 입력받은 키로거 문자열 
list<char> L;
list<char> ::iterator cur;
​
void input(){
​
    cin >> tc; // 테스트케이스 횟수
​
    while(tc--){
        
        cin >> inputStr; // 문자열 입력받기
​
        L.clear(); // list 초기화
​
        cur = L.begin(); // 빈 리스트의 시작점에 커서를 둔다.
​
        for(int i = 0; i < inputStr.length(); i++){
​
            if(inputStr[i] == '<'){ // 커서를 왼쪽으로
                if(cur != L.begin()){
                    cur--;
                }
            }
            else if(inputStr[i] == '>'){ // 커서를 오른쪽으로 
                if(cur != L.end()){
                    cur++;
                }
            }
            else if(inputStr[i] == '-'){ // 백스페이스
                if(cur != L.begin()){
                    cur = L.erase(--cur); // 커서를 앞으로 당긴 후, 삭제.
                }
            }
            else {
                L.insert(cur, inputStr[i]);
            }
        } // for
​
        // 출력
        for(cur = L.begin(); cur != L.end(); cur++){
            cout << *cur;
        }
        cout << '\n';
​
    } // while
}
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    input();
    return 0;
}

---

리뷰

키로거 문자열을 입력받고, 문자열을 순회하면서 list에 문자을 삽입한다.

커서도 list에서 움직이게 했다. 빈 리스트의 시작점에 커서를 뒀다.

백스페이스 처리할 때, 커서를 앞으로 당긴 후에 erase()를 해야 되는 것을 유념하자.

문제

에디터 1406

List 를 이용한 "맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;
​
list<char> strList;
string str;
int M;
char ch, x;
​
void input(){
​
    cin >> str >> M; // 초기 문자열, 명령의 횟수
​
    // 문자열의 문자를 리스트에 넣는다.
    for(int i = 0; i < str.size(); i++){
        strList.push_back(str[i]);
    }
​
    auto cur = strList.end(); // 커서는 마지막을 가리키고 있다
​
    while(M--){ // 명령 수행
​
        cin >> ch;
​
        if(ch == 'P') {
            cin >> x;
            strList.insert(cur, x); // 문자를 커서 왼쪽에 추가
        }
        else if(ch == 'L') {
            if (cur != strList.begin()) { // 맨 처음이 아니면,
                cur--; // 커서를 왼쪽으로 한 칸 옮김
            }
        }
        else if(ch == 'D'){
            if(cur != strList.end()){ // 커서가 맨 마지막이 아니면,
                cur++; // 커서를 오른쪽으로 한 칸 옮김
            }
        }else { // 'B'
            if(cur != strList.begin()){ // 커서가 맨 마지막이 아니면,
                cur--; // 커서 기준 왼쪽이니까 -- 해준다.
                cur = strList.erase(cur); // 문자 삭제 후, 주소값을 갱신
            }
        }
    }// while
​
    for(auto c : strList) cout << c;
}
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    input();
    return 0;
}

Stack 을 이용한 "맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;
​
stack<char> leftStack;
stack<char> rightStack;
string str;
int M;
char ch, x;
​
void input(){
​
    cin >> str >> M;
​
    for(int i = 0; i < str.size(); i++){
        leftStack.push(str[i]);
    }
​
    while(M--){ // 명령 횟수만큼 반복 
​
        cin >> ch; // 명령 문자 
​
        switch(ch){
            case 'P':
                cin >> x; // 추가할 문자 
                leftStack.push(x); // 문자를 커서 왼쪽에 추가
                break;
            case 'L':
                if(!leftStack.empty()){ // 왼쪽 스택에 문자가 있는지 확인 
                    rightStack.push(leftStack.top());  // 왼쪽 스택에 있던 top을 오른쪽 스택에 넣는다 
                    leftStack.pop(); // 실제 pop()연산 수행 
                }
                break;
            case 'D':
                if(!rightStack.empty()){ // 커서 오른쪽에 문자가 있는지 확인 
                    leftStack.push(rightStack.top());
                    rightStack.pop();
                }
                break;
            case 'B':
                if(!leftStack.empty()){
                    leftStack.pop();
                }
                break;
        }// switch
    }// while
​
    while(!leftStack.empty()){ // 문자를 순서대로 꺼내야 하니까. 왼쪽스택에 있던것을 오른쪽으로 전부 이동시킴
        rightStack.push(leftStack.top());
        leftStack.pop();
    }
​
    while(!rightStack.empty()){ // 실제 답 출력 
        cout << rightStack.top();
        rightStack.pop();
    }
}
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    input();
    return 0;
}

연결리스트를 이용한 경우 리뷰

커서의 위치를 저장하기 위해 iterator를 이용했다.

auto cur = strList.end(); // 커서는 마지막을 가리키고 있다

erase 함수로 커서가 가리키는 문자를 삭제하고 나서, 커서의 주소를 갱신해주는 것을 유의해야 한다.

cur = strList.erase(cur); // 문자 삭제 후, 주소값을 갱신

스택을 이용한 경우 리뷰

커서를 기준으로 두고 스택을 2개 사용했다.

커서를 기준으로 왼쪽에 저장할 문자를 담을 스택, 커서를 기준으로 오른쪽에 저장할 문자를 담을 스택.

4가지 연산 모두 커서 위치를 기준으로 발생하기 때문이다.

문제

strfry 백준 11328 c++

"맞았습니다."코드

#include <bits/stdc++.h>
using namespace std;
​
int T;
​
void func(string a, string b){
​
    int cntA[35] = {};
    int cntB[35] = {};
​
    for(int i = 0; i < a.length(); i++){
        cntA[a[i]-97]++;
    }
    for(int i = 0; i < b.length(); i++){
        cntB[b[i]-97]++;
    }
​
    string answer = "Possible\n";
    for(int i = 0; i < 79-61+1; i++){
        if(cntA[i] != cntB[i]){
            answer = "Impossible\n";
            break;
        }
    }
​
    cout << answer;
}
​
void input(){
    cin >> T;
    string a, b;
    for(int i = 0; i < T; i++){
        cin >> a >> b;
        func(a, b);
    }
}
​
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
​
    input();
    return 0;
}

리뷰

소문자 알파벳 개수가 동일한지 비교하면 된다.

소문자 알파벳과 ascii 코드를 매칭하기 위해 문자열에서 97을 뺐다.

소문자 a에서 97을 빼면 0이 나온다.

소문자 a부터 소문자 z까지 아스키코드는 연속적이니까 이렇게 인덱스로 매칭 할 수 있다.

단어에서 a의 개수를 배열의 0인덱스의 값에 저장했다. b의 개수는 배열의 1인덱스 값에 저장했다.