[Inflearn] 기차운행

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - B도시로 1,2,3 순으로 도착

     - 모든 기차는 교차로에 들어가야만 B도시로 갈 수 있음

     - 도착 불가능하면 impossile 출력

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 아래와 같이 입력되었다면

     3

     2 1 3 

     idx = 1,

     push() stack[2] => P

     stack의 top이 idx 와 같은지 확인

     다르다면 다시 push

     push() stack[2, 1] => P

     stack의 top()이 idx 와 같은지 확인

     같으므로 O를 출력하고 pop() => O

     idx++

     stack[2]

     

     다시 stack의 top()이 idx 와 같은지 확인

     idx가 같으므로 out(), stack[2] => O

     idx++

     stack[]

     stack 이 비어있거나 idx 와 다르다면 다음 기차를 push

     push() stack[3] => P

     stack의 top이 idx 와 같은지 확인

     같으므로 O를 출력하고 pop() => O

     idx++

     마지막에 idx 가 n보다 크다면 반복문이 종료되면 되겠다.

    

     --

    

     만일 순서대로 도착이 불가능할 경우

     impossible 로 출력해야하므로

     P 와 O 를 바로 출력할 수 없고 char 배열에 저장해둔 후 마지막에 출력해주어야 할 것 같다.

     그리고 순서대로 도착이 불가능한지 확인하는 방법은

     모든 기차가 다 교차로에 들어왔지만 나갈 수 없는 상황일 것이다.     

     이 과정을 컴퓽이가 이해할 수 있게 코드로 옮겨보자!

#. Code

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, i, idx = 1, seq = 1;
 
    scanf("%d", &n);
    vector<int> train(n+1);
    vector<char> rst;
    stack<int> t;
 
    for (i = 1; i < n+1; i++)
        scanf("%d", &train[i]);
 
    while (seq <= n)
    {
        if (idx <= n)
        {
            t.push(train[idx]);
            rst.push_back('P');
            idx++;
        }
 
        while (!t.empty() && t.top() == seq)
        {
            t.pop();
            rst.push_back('O');
            seq++;
        }
 
        if (idx > n && !t.empty())
            break;
    }
 
    if (!t.empty())
        printf("impossible");
    else
    {
        for (i = 0; i < rst.size(); i++)
        {
            printf("%c", rst[i]);
        }
    }
 
    return 0;
}

디버깅하면서 뜯어 고치다보니까 생각했던거와 좀 다른 부분도 있을 것 같은데..

거의 유사하다.

--

강사님 코드를 보고 좀 더 깔끔하게 다시 짜보았다.

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, i, tmp, seq = 1;
    vector<char> rst;
    stack<int> t;
 
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &tmp);
 
        t.push(tmp);
        rst.push_back('P');
 
        while (!t.empty() && t.top() == seq)
        {
            t.pop();
            rst.push_back('O');
            seq++;
        }
    }
 
    if (!t.empty())
        printf("impossible");
    else
    {
        for (i = 0; i < rst.size(); i++)
        {
            printf("%c", rst[i]);
        }
    }
 
    return 0;
}

#. Other code

#include<stdio.h>
#include<stack>
#include<vector>
 
using namespace std;            
 
int main(){
    stack<int> s;
    int i, j=1, n, m;
    vector<char> str;
 
    scanf("%d", &n);
 
    for(i=1; i<=n; i++){
        scanf("%d", &m);
 
        s.push(m);
        str.push_back('P');
 
        while(1){
            if(s.empty()) break;
            if(j==s.top()){
                s.pop();
                j++;
                str.push_back('O');
            }
            else break;
        }
    }
 
    if(!s.empty()) printf("impossible\n");
    else{
        for(i=0; i<str.size(); i++) printf("%c", str[i]);
    }
 
    return 0;
}
 
 

역시나.. 로직은 같은데 이렇게나 차이날수가..

line 15) 입력과 동시에 처리를 해주었기때문에 들어오는 기차의 정보를 담는 배열은 필요가 없어지겠다.

line 17) 기차가 들어오자마자 교차로에 넣어준다. 계속 들어올 수 없게 당연 밑에서 처리를 해주기 때문에

line 20~28) 교차로가 비어있거나 교차로의 top 이 j 와 다른 경우를 제외하고 계속 반복해준다. 

     교차로의 top 이 j 와 같을 경우 해당 top 을 빼주고 j++

#. Result

  - Input --------------------------------------------------------

3

2 1 3

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

  - Output --------------------------------------------------------

PPOOPO

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