백준 5430 - AC(C++)

문제 https://www.acmicpc.net/problem/5430

5430번: AC

 

풀이

R이 입력되었을 때, 매번 배열을 뒤집으면 시간 초과가 발생할 것이다. R이 입력될 때마다 flag를 설정해서 처리해줬다.

뒤집힌 상황 -> D가 입력됨 -> 뒤에서 노드를 제거

뒤집히지 않은 상황 -> D가 입력됨 -> 앞에서 노드를 제거

즉, 앞 뒤에서 노드를 제거할 수 있어야 하므로 더블리 링크드 리스트를 사용했다.

더블리 링크드 리스트로 구현하면 값을 출력할 때도 맨 뒤 노드부터 prev로 접근하면서 역순으로 출력하거나, head부터 next로 접근하면서 순차적으로 출력할 수 있게 된다.

 

DLL 구현에 대한 포스팅은 -> https://qqs-diary.tistory.com/88

 

그리고 뒤집힌 상태를 확인하기 위한 flag의 값을 반전시키기 위해 아래와 같이 코드를 작성했다.

revflag = revflag ? false : true;

항상 짧은 코드가 좋은 것은 아니라지만, 값만 반전시키는 건데 너무 길어도 가독성을 해칠 것 같아서 한 줄로 작성했다.

flag가 true였다면 false로, false였다면 true로 값을 반전시킨다.

 

코드

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

typedef struct node
{
    int i;
    struct node*next;
    struct node*prev;
}node;

node*head;
node*cur;
bool revflag = false;
bool errflag = false;

void init()
{
    head=0;
    cur=0;
    revflag=false;
    errflag=false;
}


void addToAC(int num)
{
    node*newnode = (node*)malloc(sizeof(node));
    newnode->i = num;
    newnode->prev = newnode->next=0;

    if(head==0)
    {
        head=newnode;
        cur=head;
        return;
    }
    cur->next=newnode;
    newnode->prev=cur;
    cur=newnode;
}

int removeNum()
{
    if(head==0) return -1;
    if(revflag) //뒤집힌 상태
    {
        node*del = cur;
        if(del->prev==0) head=0;
        else
        {
            cur=cur->prev;
            cur->next=0;
        }
        free(del);
    }
    else
    {
        node*del = head;
        head=head->next;
        if(head!=0) head->prev=0;
        free(del);
    }
    return 0;
}

void printAC()
{
    if(errflag) 
    {
        cout<<"error"<<endl;
        errflag = false;
        return;
    }
    if(head==0) 
    {
        cout<<"[]"<<endl;
        return;
    }

    cout<<'[';
    if(revflag) //뒤집힌 상태
    {
        while(cur->prev!=0)
        {
            cout<<cur->i<<",";
            cur=cur->prev;
        }
        cout<<cur->i;
    }
    else
    {
        node*tmp = head;
        while(tmp->next!=0)
        {
            cout<<tmp->i<<",";
            tmp=tmp->next;
        }
        cout<<tmp->i;
    }
    cout<<']'<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    int T;
    cin>>T;
    for(int i=0; i<T; i++)
    {
        init();
        string p; // 수행할 함수
        cin>>p;
        int n; // 배열에 들어있는 수의 개수
        cin>>n;
        string tx; // 배열
        cin>>tx;
        string x = tx.substr(1,tx.length()-2);
        stringstream ss(x);
        string num;
        while(getline(ss,num,','))
        {
            int in=0;
            stringstream ssInt(num);
            ssInt>>in;
            addToAC(in);
        }
        ss.clear();
        int len = p.length();
        for(int j=0; j<len; j++)
        {
            if(p[j]=='R') revflag = revflag ? false : true;
            else if(p[j]=='D') 
            {
                int res = removeNum();
                if(res==-1) 
                {
                    errflag=true;
                    break;
                }
            }
        }
        printAC();
    }
    return 0;
}

---

 

+ 나에게 도움이 됐던 TC

1

RDRDR

5

[1,2,3,4,5]

 

답 - [4,3,2]

head를 지운 후에 head의 prev 포인터가 0을 가리키도록 해야 출력할 때 쓰레기값이 나오지 않는다. 이때 또 주의할 점은 head가 0인 경우라면 널포인터에 접근하는 것이 되므로, head가 0이 아닌 경우에만 head의 prev가 0을 가리키도록 해준다.