JArchive 프로그래밍 일기

목차

0x00 수식의 괄호 쌍이란?

0x01 문제 해결을 위한 관찰

0x02 문제 해결 방법

0x03 연습문제

0x00 수식의 괄호 쌍이란? 

수식의 괄호 쌍이 짝이 맞는지 확인해보자. 

( 이 있으면 ) 으로 닫아야 짝이 맞다. { 이 있으면 } 이 있어야한다. 

두 번째 식에서 (12+4} 여기가 틀렸다. 이와 같이 수식의 괄호 쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제다. 

0x01 문제 해결을 위한 관찰 

아래의 3개 수식 중에 올바른 괄호 쌍은 무엇 무엇이 있을까? 

결론부터 말하면 첫 번째 식만 올바른 괄호 쌍이다. 

판단 방법 중에 가장 보편적인 방법은 바로 안쪽부터 짝 맞추기를 해서 지워나가는 방법이다. 

그리고 관찰력이 뛰어나다면,  ')' 의 개수가 '(' 의 갯수를 넘지 않으면 된다는 사실도 있다. 

괄호의 종류가 () 말고도 {}, [] 이 있다면, 여는 괄호의 갯수와 닫는 괄호의 갯수 비교만으로 해결되지 않는다. 

우리는 머릿속으로 어떤 로직을 거쳐서 판단한 걸까? 생각의 과정을 관찰하여 코드로 구현해보자. 

스택을 이용하여 구현해보자. 

아래의 관찰을 인지해야 한다. 

"닫는 괄호는 남아있는 괄호 중에서
가장 최근에 읽은 여는 괄호와 짝을 지어 없애버리는 명령이다. " 

1. 스택을 하나 두고, 문자열을 읽어 나가다가 여는 괄호를 만나면 모두 스택에 넣는다. 

2. 문자열을 읽어 나가다가 닫는 괄호를 만나면 스택의 top을 확인한다. 

3. 지금 읽은 것이 닫는 괄호이고 스택의 top이 여는괄호라면?  쌍이 올바른 것이다.

4. 따라서 스택의 top인 여는 괄호를 스택에서 지운다. pop() 

올바르지 않은 괄호 쌍 

올바르지 않은 괄호 쌍의 경우, 과정을 살펴보자. 

1. 문자열을 읽다가 만난 여는 괄호 2개는 모두 스택에 넣는다. 

2. 닫는 괄호 ) 를 만나면, 스택의 top을 확인한다. 

현재 스택의 top은 { 이다. 

3. 스택의 top인 {와 닫는괄호 ) 는 짝이 안맞는다. 

올바르지 않은 괄호 쌍의 예시 2가지 

1. 문자열을 끝까지 읽었는데, 스택에 여는 괄호가 남아있다. 

2. 문자열을 끝까지 읽고 스택도 비었는데, 닫는 괄호가 남아있다. 

0x02 문제 해결 방법 

올바른 괄호 쌍 판단을 위해 문제 해결 방법을 정리해본다. 

1. 여는 괄호가 나오면 스택에 추가.

2. 닫는 괄호가 나왔을 경우, 스택의 top이 짝이 맞는 괄호라면 pop 

3. 스택에 괄호가 남아있지 않으면 올바른 괄호 쌍. 

스택이 비었을 때 top을 참조하면 런타임에러!

0x03 연습문제 

수식의 괄호쌍이 코딩테스트에서 무조건 나온다고 할 정도로 중요하진 않지만,

stack을 이용한 문제가 많기 때문에 연습문제를 꼭 풀어보자. 

다음 시간에는 BFS를 배운다. 

공부 자료 출처 : 바킹독 알고리즘 수식의 괄호 쌍

문제

그림 백준 1926

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
​
int n, m; // 세로, 가로
int board[502][502];
int v[502][502]; // 방문했으면 1로 표시
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
​
int cnt, answer; // 그림 개수와 넓이.
​
int bfs(int a, int b){
​
    queue<pair<int,int> > q;
    int num = 0;
​
    // 방문표시 후, 큐에 넣기.
    v[a][b] = 1;
    q.push({a,b});
​
    while(!q.empty()){
​
        int x = q.front().X;
        int y = q.front().Y;
        q.pop();
        num++;
        for(int i = 0; i < 4; i++){
            int tempX = x + dx[i];
            int tempY = y + dy[i];
​
            if(tempX < 0 || tempX >= n || tempY < 0 || tempY >= m) continue; // 범위 초과는 탈출
            if(v[tempX][tempY] == 1) continue; // 이미 방문한거면 지나감
​
            if(board[tempX][tempY] == 1){ // 그림영역이라면 방문표시 후 큐에 넣기.
                board[tempX][tempY] = 2;
                v[tempX][tempY] = 1;
                q.push({tempX, tempY});
            }
        }
    }
​
    return num;
}
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    cin >> n >> m;
​
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
            cin >> board[a][b];
        }
    }
​
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
​
            if(board[a][b] == 0 || v[a][b] == 1) continue;
            cnt++; //그림 개수 카운트
            answer = max(answer, bfs(a,b)); // 최대 넓이 찾기 
​
        }
    }
​
    cout << cnt << '\n' << answer;
    return 0;
}

리뷰

BFS 기본 형태의 문제다.

인덱스 확인 후 그림영역에 방문 표시를 한다음에 방문한 좌표를 push()를 해줘야하는데.

그거 하나 틀려서 시간을 많이 잡아먹었다.

문제

괄호의 값 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 만 한다.