알고스팟 2주년 기념문제 : 가장 흔한 접두어. 도움 요청합니다. ㅜㅜ

  • 로제폰
    로제폰

    문제를 보고 요구대로 짠거 같은데 계속 WA 나와서 질문 올립니다.

    제가 어떻게 짰냐면 계속 단어읽으면서 STL map 에 prefix들을 저장하고 빈도수를 세고,
    vector에 prefix들을 저장해서 그걸
    길이순, 빈도순, 사전순으로 sort 함수로 정렬해서 각 길이당 제일 앞에 있는 prefix를 출력했습니다.

    뭐가 문젠지 아무리 봐도 모르겠습니다 ㅜㅜ;
    다음은 소스입니다.

    //////////////////////////////////////////////////////////////////////////////////////////////////
#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<fstream>
#include<algorithm>
#include<stdio.h>

using namespace std;
FILE *fp;
map<string, int> pre;
map<string, int> order;

struct compare {
  bool operator ()(string a, string b) const {
    if(a.length() == b.length()) {
      if(pre[a] == pre[b])
    //    return a < b;
        return order[a] < order[b];
      return pre[a] > pre[b];
    }
    return a.length() < b.length();
  }
};

int main() {
  fp = fopen("input.in", "r");
//  fp = stdin;
  int c, n, m;

  fscanf(fp, "%d", &c);
  while(c--) {
    fscanf(fp, "%d%d", &n, &m);
    order.clear();
    pre.clear();
    vector<string> data;
    getc(fp);
    for(int i = 0;i<n;i++) {
      string pf;
      pf.clear();
      char ch;
      while(fscanf(fp,"%c", &ch) == 1 && ch != '\n') {
        pf += ch;
        if(pre.find(pf) == pre.end()) {
          pre[pf] = 1;
          data.push_back(pf);
          order[pf] = i;
        } 
        else
          pre[pf]++;
      }
    }
    sort(data.begin(), data.end(), compare());

    int j = 1;
    for(int i = 0;i<data.size();i++) {
      if(data[i].length() == j) {
        cout << data[i] << endl; 
        j++;
        if(j == m+1)
          break;
      }
    }
  }

  return 0;
}

//////////////////////////////////////////////////////////////////////////////////////////////////

    14년 전
9개의 댓글이 있습니다.
  • Taeyoon_Lee
    Taeyoon_Lee

    우선 입력을 파일에서 읽으면 절대 안 됩니다. stdin 표준 입출력을 사용하셔야 하구요, getc(fp)는 어떤 의미인지 잘 모르겠네요.. 입력이 제대로 안 받아질 것 같습니다. (fgetc도 아니고..;;) 그리고 줄바꿈 문자가 \r\n일지 \n일지 모르기 때문에 fgetc로는 위험할 것 같고, 단지 화이트 스페이스(엔터 탭 스페이스 등)를 제거할 목적이라면 scanf에 빈칸을 넣어주면 됩니다. fscanf(fp, "%d%d ", &n, &m); 이런 식으로 말이죠. 근데 이런 자잘한 문제를 고치더라도 알고리즘적 자체가 시간 제한에 걸리진 않을지 모르겠습니다.. 'ㅅ' 푸신 분들의 답변을 기다려 보죠..


    14년 전 link
  • 바나나용
    바나나용

    저도 이문제를 풀다가 거의 포기 상태인데;; 혹시 이문제 DP가 아닐까요..


    14년 전 link
  • 로제폰
    로제폰

    이태윤// 입력을 매번 쓰기 귀찮아서 fp를 파일로 읽고 제출할땐 fp=stdin 으로 하여 제출하면 표준 입출력과 같습니다. getc(fp)는 줄바꿈 문자가 \r\n일수도 있는건 생각 못했네요.
    getc(fp) 없애고 위에 fscanf(fp, "%d%d", &n, &m); 을 fscanf(fp, "%d%d ", &n, &m); 으로 바꿨더니 WA가 안 나오고 TLE가 나오네요. 역시 알고리즘을 잘못 생각했나봅니다.;;


    14년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    방금 문제를 풀어 보았는데요, 이런 식으로 모든 문자열을 저장해선 안 됩니다. 메모리를 너무 많이 먹고, map은 메모리가 늘어날수록 느려지기 때문에 TLE가 날 수 밖에 없죠.

    힌트를 드릴게요. 예제 입력을 예로 들었을 때, 시간복잡도 O(n*m)만에 아래 테이블을 만들려고 노력해보세요. 예제 입력을 보셨으면 이게 뭘 의미하시는지 아시겠죠 'ㅅ'?

    1111
    2211
    3311
    4110
    5220
    6331

    110
    220
    310
    421
    110
    100
    211

    이렇게 테이블을 만들어서 푸는 방식이 있고, 또 재귀적으로 분할정복해가는 방법도 있습니다. 분할정복해가는 방법은 다른 분들이 써주실 듯..?

    그리고 사실 while(fscanf(fp,"%c", &ch) == 1 && ch != '\n') 요것도 \r\n이면 죽는 코드입니다만, 잘 넘어간다면 입력은 \r\n이 아닌 \n라고 추측해볼 수 있겠군요..


    14년 전 link
  • okioki007
    okioki007

    윗님말씀대로 재귀적 분할정복으로 풀수있는데
    모든 문자열에 대해서 한 문자씩 확인하면서 문자가 같은 그룹끼리 나눕니다. 또 그 그룹내에서 다음 문자에 대해 같은 그룹끼리 나눕니다. 매번 그룹을 나눌때마다 그룹의 크기 중 최대값을 저장해 나가면 이문제를 시간내에 풀 수있습니다.

    depth = 1
    dark
    date
    dave
    doc
    doc
    dock

    • 1st문자를 기준으로 그룹을 나누는데 이건 뭐 다 같으니 하나의 그룹이네요 (state : len=1, Max = 6, "d")

    depth = 2
    dark
    date
    dave

    doc
    doc
    dock

    • 2nd문자를 기준으로 그룹을 나눕니다. 3개씩 쪼개지네요 (Max = 3) 여기서부터 문자열 그룹이 둘로 쪼개지고 그 그룹 둘을 다른문제 풀듯이 나눠서 생각하시면 됩니다 (state : len=2,Max = 3, "da")

    depth = 3
    dark

    date

    dave

    • 3rd문자기준으로 그룹을 나눕니다. (state : len = 3, Max = 1, "dark")

    depth = 3
    doc
    doc
    dock

    • 위쪽과 다른 그룹인 이부분도 똑같이 3rd문자기준으로 그룹을 나눕니다. (state : len = 3, Max = 3, "doc") <= state가 더 좋은 값으로 갱신됩니다

    ....

    이런방식으로 그룹을 나누면서 그룹의 크기가 최대인것을 매번 저장하면 됩니다.
    n개의 문자열에 대해서 m depth까지 중복없이 한번씩만 확인하므로 O(n*m) 으로 풀수있습니다

    글재주가없어서ㅠ 이해가 되셨는지 모르겠네요ㅠ


    14년 전 link
  • 바나나용
    바나나용

    방금 문제 AC받았습니다 ㅜ.ㅜ 저때문에 rate가 엉망인거 같아서;
    저도 이태윤님 방법으로 풀었는데, TLE때문에 고생했습니다.
    혹시 cin, cout으로 스트링 처리 하셨다면
    scanf, printf를 사용해보시기 바랍니다.
    알고리즘은 한참전에 생각했는데, 이것때문에 엄청 고생했습니다


    14년 전 link
  • 로제폰
    로제폰

    이태윤\ 위 댓글대로 O(n*m)에 테이블을 만들어서 각 길이당 최고 길이 접두어를 출력하게 했는데도 TLE가 뜨네요;; 제가 컴퓨터에서 돌릴 땐 잘 입력받는데 제출 서버에서 입력을 제대로 못 읽어서 그런거 같은데 어떻게 입력 처리하시나요? 아래는 현재의 소스입니다. 

    #include<string>
#include<stdio.h>
#include<string.h>

using namespace std;
FILE *fp;

int d[3000][200];
char strs[3000][202];

int main() {
  int c, n, m;
  char buf[300];
//  fp = fopen("input.in", "r");
        fp = stdin;
  fscanf(fp, "%d", &c);
  while(c--) {
    fscanf(fp, "%d%d ", &n, &m);

    for(int i = 0;i<n;i++)
      for(int j = 0;j<m;j++)
        d[i][j] = 0;

    char ch;
    int len = 0;

    while(fscanf(fp, "%c", &ch) == 1 && ch >= 'a' && ch <= 'z') {
      d[0][len] = 1;
      strs[0][len++] = ch;
    }
    strs[0][len] = 0;

    for(int i = 1;i<n;i++) {
      len = 0;
      while(fscanf(fp, "%c", &ch) == 1 && (ch < 'a' || ch > 'z'));

      bool check = true;
      while(ch >= 'a' && ch <= 'z') {
        strs[i][len] = ch;

        if(strlen(strs[i-1]) < len)
          d[i][len] = 1;
        else {
          if(ch != strs[i-1][len])
            check = false;

          if(check)
            d[i][len] = d[i-1][len]+1;
          else
            d[i][len] = 1;
        }

        len++;
        if(fscanf(fp, "%c", &ch) != 1)
          break;
      }
      strs[i][len] = 0;
    }

    for(int i = 0;i<m;i++) {
      int max = d[0][i], idx = 0;
      for(int j =1;j<n;j++) {
        if(d[j][i] > max) {
          max = d[j][i];
          idx = j;
        }
      }
      string ans(strs[idx], i+1);
      printf("%s\n", ans.c_str());
    }
  }

  return 0;
}

    14년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    정확한 TLE의 원인은 잘 모르겠습니다만, 저는 scanf("%s") 로 처리했습니다... 굳이 위험부담(?)을 안고 %c로 처리할 필요가 있을지 모르겠네요..


    14년 전 link
  • 로제폰
    로제폰

    겨우 AC 받았네요. -_-;;
    결국 원인은 테이블 만들 때 strlen(strs[i-1])을 매번 실행한게 문제였네요..ㅜㅜ
    암튼 조언들 감사했습니다. 나중에 재귀적으로도 짜봐야겠네요.


    14년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.