글 읽기 - (수정) 9935번 100%에서 틀렸다고 나오는데 이유를 잘모르겠어요

cys4439 2년 전 0

아이디어는 이렇습니다

처음줄의 문자를 s1 폭발시킬 문자열 s2라고하면

일단 s1의 문자열 처음부터 하나 하나 char형 벡터에 넣는데

s2에는 중복이 되는 문자가 없으므로

벡터에 넣기전에 그 문자가 s2에 있다면 s2의 몇번째의(맨앞을 0) 문자인자를 함께 넣어주고 그렇지않으면 -1을 넣어줍니다

그러다가 넣을 문자가 s2의 맨끝의 문자와 같은 문자일경우 벡터에 넣는걸 일단 보류하고 넣어도 되는가를 판별하러

1.f()함수를 호출합니다

지금 값을 아직 벡터에 넣지않았으므로 벡터에 맨끝의 문자가 s2의 뒤에서 두번째 값이 같다면 다시 1로 돌아가서

s2의 뒤에서 세번째값과 벡터의 뒤에서 두번째값을 비교합니다 만족하면 다시 1번 이런식으로 반복하다가

s2의 크기만큼 도달했다면 그 문자들을 폭발시킬수 있는 문자열이므로 pop_back해줍니다.

만약 1과 2사이에서 해당 조건을 만족하지 않으면 지울 문자가 아니므로 방금까지 보류했던 문자를 벡터에 넣고 종료합니다

이런 방식으로 짰는데 51퍼에서 막히고 어떤 부분이 문제인지 잘모르겠습니다

맨 처음에 괄호 문제랑 비슷해보여서 스택으로 풀려다가 벡터로도 가능 할거 같아서 이렇게 해봤는데 안되네요

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <vector>
using namespace std;
vector < pair<char,int> > v;
string s1,s2;
bool check[62];
int check2[62]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
void f(int index,int n);
void setting();
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>s1>>s2;
    for(int i=0; i<s2.size(); i++)
    {
        if('0'<=s2[i]&&s2[i]<='9')
        {
            check[(int)s2[i]-(int)'0']=true;
            check2[(int)s2[i]-(int)'0']=i;
        }
        else if('a'<=s2[i]&&s2[i]<='z')
        {
            check[10+(int)s2[i]-(int)'a']=true;
            check2[10+(int)s2[i]-(int)'a']=i;
        }
        else if('A'<=s2[i]&&s2[i]<='Z')
        {
            check[36+(int)s2[i]-(int)'A']=true;
            check2[36+(int)s2[i]-(int)'A']=i;
        }
    }
    setting();
    if(v.size()==0)
    {
        cout<<"FRULA";
    }
    else
    {
        for(int i=0; i<v.size(); i++)
        {
            cout<<v[i].first;
        }
    }

}
void setting(){
    for(int i=0; i<s1.size(); i++)
    {
        if(s1[i]==s2[s2.size()-1])
        {
            f(s2.size()-1,1);
        }
        else
        {
            int z;
            if('0'<=s1[i]&&s1[i]<='9')
            {
                z=int(s1[i])-(int)'0';
            }
            else if('a'<=s1[i]&&s1[i]<='z')
            {
                z=10+int(s1[i])-(int)'a';
            }
            else if('A'<=s1[i]&&s1[i]<='Z')
            {
                z=36+int(s1[i])-(int)'A';
            }
            if(check[z]==false)
            {
                v.push_back({s1[i],-1});
            }
            else
            {
                v.push_back({s1[i],check2[z]});
            }
        }
    }
}
void f(int index,int n){
    if(v.size()==0)
    {
        v.push_back({s2[s2.size()-1],s2.size()-1});
        return;
    }
    if(n==s2.size())
    {
        for(int i=0; i<n-1; i++)
        {
            v.pop_back();
        }
        return;
    }
    if(v.size()-n>=0&&v[v.size()-n].second==index-1)
    {
        f(index-1,n+1);
    }
    else
    {
        v.push_back({s2[s2.size()-1],s2.size()-1});
        return;
    }
}

cys4439 2년 전 0

입력이

999abc

일때 9abc로 나오길래 f()의 84~88줄과 89~96번째 줄을 순서를 바꿔 아래 처럼 바꾸었더니 100퍼센트에서 런타임에러 (OutOfBounds)가 뜨네요 이건 뭔지 ;;

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <vector>
using namespace std;
vector < pair<char,int> > v;
string s1,s2;
bool check[62];
int check2[62]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
void f(int index,int n);
void setting();
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>s1>>s2;
    for(int i=0; i<s2.size(); i++)
    {
        if('0'<=s2[i]&&s2[i]<='9')
        {
            check[(int)s2[i]-(int)'0']=true;
            check2[(int)s2[i]-(int)'0']=i;
        }
        else if('a'<=s2[i]&&s2[i]<='z')
        {
            check[10+(int)s2[i]-(int)'a']=true;
            check2[10+(int)s2[i]-(int)'a']=i;
        }
        else if('A'<=s2[i]&&s2[i]<='Z')
        {
            check[36+(int)s2[i]-(int)'A']=true;
            check2[36+(int)s2[i]-(int)'A']=i;
        }
    }
    setting();
    if(v.size()==0)
    {
        cout<<"FRULA";
    }
    else
    {
        for(int i=0; i<v.size(); i++)
        {
            cout<<v[i].first;
        }
    }

}
void setting(){
    for(int i=0; i<s1.size(); i++)
    {
        if(s1[i]==s2[s2.size()-1])
        {
            f(s2.size()-1,1);
        }
        else
        {
            int z;
            if('0'<=s1[i]&&s1[i]<='9')
            {
                z=int(s1[i])-(int)'0';
            }
            else if('a'<=s1[i]&&s1[i]<='z')
            {
                z=10+int(s1[i])-(int)'a';
            }
            else if('A'<=s1[i]&&s1[i]<='Z')
            {
                z=36+int(s1[i])-(int)'A';
            }
            if(check[z]==false)
            {
                v.push_back({s1[i],-1});
            }
            else
            {
                v.push_back({s1[i],check2[z]});
            }
        }
    }
}
void f(int index,int n){
    if(n==s2.size())
    {
        for(int i=0; i<n-1; i++)
        {
            v.pop_back();
        }
        return;
    }
    if(v.size()==0)
    {
        v.push_back({s2[s2.size()-1],s2.size()-1});
        return;
    }
    if(v.size()-n>=0&&v[v.size()-n].second==index-1)
    {
        f(index-1,n+1);
    }
    else
    {
        v.push_back({s2[s2.size()-1],s2.size()-1});
        return;
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(수정) 9935번 100%에서 틀렸다고 나오는데 이유를 잘모르겠어요

cys4439 2년 전 0

cys4439 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말