JArchive 프로그래밍 일기

백준 2468번 안전 영역 문제를 풀어서 바킹독 알고리즘 강의 풀이 레포지토리에 PR했다. 

이번에 올리는 PR이 3번째라... 제발 merge되기를 빌었는데. 드디어 되서 기뻤다.

어젯밤에 반례를 못찾고 왜 틀렸는지 못찾아서 2시간이나 잡아먹은 문제라... 

그리고 앞으로 변수명은 i,j로 꼭 맞춰야겠다. 

유툽 강의 댓글에 이 문제에 대해 질문하고 내 코드를 달아놨는데.

우연히 바킹독님 유튜브 라이브때 접속해계셔서. 밤에 라이브때 내 코드를 띄워놓고(좀 부끄러웠지만..) 바로 반례찾아주셨다. 

감동이었고 감사했다. 

나도 바킹독님 처럼 다른사람을 도울 수 있는 능력과 마음을 가진 사람으로 성장하고 싶다는 생각을 다시금 했다. 

바킹독님 알고리즘 문제 풀이 레포지토리에 내 코드를 PR 올렸다. (두근두근)

다른 분 레포에 PR을 올려본건.. 처음인데. 

바킹독님으로부터 코드 리뷰를 받았다. 레포지토리의 컨벤션 지키는 것에 실수가 있고 파일명이 꼬여서라는 이유로 Close 됬지만.

덕분에 short-circuit evaluation을 다시 상기시키며 내 코드가 어떻게 나아질 수 있는지 배울 수 있어서 기뻤다. 

동작은 하는데, 찜찜하고 어떻게 더 낫게 고치는지 방법을 못찾겠는 상태였었는데.

이제 속시원.

바킹독님이 컨벤션을 고쳐주시고 (Tab -> space2개.. etc) 코드의 아쉬운점을 고쳐서 새로 올려주셨다.  

Authored by 내 닉네임이 올라가니까 설레기도 하고. 더 잘하고 싶다는 마음과 재미도 생겼다. 

앞으로도 화이팅.

문제

괄호의 값 2504

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;
​
stack<char> s;
string str;
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    getline(cin, str);
​
    bool check = true; // 짝이 안맞는 틀린 괄호인지 체크 
​
    int sum = 0; // 누적해서 더해질 값
    int num = 1; // 곱해질 값
​
    for(int i = 0; i < str.length(); i++){ // 괄호가 틀린 경우를 필터링
​
        if(str[i] == '(' || str[i] == '[') {
            s.push(str[i]); continue;
        }
        else if(str[i] == ']' && s.size() > 0){
            if(s.top() == '[') {
                s.pop();
                continue;
            }
        }
        else if(str[i] == ')' && s.size() > 0){
            if(s.top() == '(') {
                s.pop();
                continue;
            }
        }
        check = false; break;
    }
​
    if(!check || !s.empty()){ // 틀린 괄호쌍이니까 0 출력 후 종료 
        cout << '0';
        return 0;
    }
​
    while(1){ // 스택이 비어 있도록 처리
        if(s.empty()) break;
        s.pop();
    }
​
    for(int i = 0; i < str.length(); i++){
​
        if(str[i] == '('){
            s.push(str[i]);
            num *= 2; // 여는 괄호들이 겹치면 2배가 된다.
        }
        else if(str[i] == ')'){
​
            if(str[i-1] == '('){ // 직전 괄호가 여는 괄호였다면
                sum += num;
            }
            s.pop();
            num /= 2;  // 괄호 () 한쌍이 제거됬으니까 곱해질 값을 /2 해준다.
        }
        else if(str[i] == '['){
            s.push(str[i]);
            num *= 3;
        }
        else if(str[i] == ']'){
​
            if(str[i-1] == '['){ // 직전 괄호가 여는 괄호였다면
                sum += num;
            }
            s.pop();
            num /= 3;  // 괄호 [] 한쌍이 제거됬으니까 곱해질 값을 /3 해준다.
        }
    }
​
    cout << sum;
​
    return 0;
}

리뷰

맞왜틀 하면서 골머리싸맸다.

초반에는 스택이 비어있을 수 있는데 top을 참조하니까 런타임 에러가 났다.

스택 size()를 확인하면서 처리하자니 조건문이 깊어졌다.

그래서 앞단에서 '틀린 괄호쌍'을 걸러내도록 하는 for문을 두도록 구조를 바꿨다.

일단 틀린 괄호쌍을 걸러내고, 두 번째 for문 에서는 계산만 하도록 했다.

문제

회전하는 큐 백준 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 만 한다.