글 읽기 - 1062 - 가르침 에 대해서 가르침을 주세요....

vjerksen 7년 전 0

N<=50, K<15이므로

모든 문자열들을 하나씩, 비교하려는 문장(A)으로 놓고, 나머지 문장들을 비교 대상 문장(B)으로 놓는다. A를 구성하는 알파벳들을 중복되지 않게 저장한다음 B(최대 N개)들에 대해 하나씩 확인한다.

50 x 50 x 15 x 15 이므로 bruteforce로 구현할 수 있다고 생각했습니다.

근데 로직이 틀린 것인지, 제 구현이 잘못된 것인지 답이 나오질 않습니다. 오류찾는 데 도움 부탁드립니다!

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<cmath>
#include<climits>
#include<set>
#include<map>
#include<deque>
#include<bitset>
#include<time.h>
#include<tuple>
using namespace std;

int N,K;
vector<string> str;
int ans =-1;
int cnt;
bool flag;
int main(){
    cin >> N >> K;

    // K가 5보다 작으면, 'a','n','t','i','c' 를 무조건 포함해야함을 어긴다.
    if(K<5){
        puts("0");
        return 0;
    }
    str.resize(N);
    for(int i=0;i<N;i++){
        cin >> str[i];
    }
    for(int i=0;i<N;i++){
        set<char> st;
        vector<char> comp_char;
        cnt =1; flag = false;

        // set으로 한 문장을 구성하는 알파벳을 찾는다.
        for(int j=0;j<str[i].size();j++){
            if(st.count(str[i][j])==0){
                st.insert(str[i][j]);
                comp_char.push_back(str[i][j]);
            }
        }

        // 한 문장을 구성하는 알파벳의 수가 K를 넘어가면 문장 자체가 성립불가.
        if(comp_char.size() > K)
            continue;
        for(int j=0;j<N;j++){
            if(i==j)
                continue;
            bool comp_flag = false; // true면 미리 저장해놓은 알파벳들중 하나와 같다.
            for(int k=0;k<str[j].size();k++){
                for(int l=0;l<comp_char.size();l++){
                    if(comp_char[l] == str[j][k]){
                        comp_flag = true;
                        break;
                    }
                }
                if(comp_flag){
                    comp_flag = false;
                }

                // 만약 비교하려는 문장이 하나라도 저장해놓은 알파벳들과 겹치지 않는다면
                else{
                    flag = true;
                    break;
                }
            }
            if(flag){
                flag = false;
                continue;
            }
            else{
                cnt++;
            }
        }
        ans = max(ans,cnt);
    }
    printf("%d",ans);
    return 0;
}

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

문제

문제

출처

ICPC

1062 - 가르침 에 대해서 가르침을 주세요....

vjerksen 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말