안녕히 그리고 물고기는 고마웠어요! 답제출을 하면 오답이라고 나오네요.

  • dookim123
    dookim123

    제알고리즘에 대해서 명확하게 뭐가 틀린지 모르겠네요.

    #알고리즘 내용.

    • 제알고리즘은 트라이로 구성되어있습니다.
    • 각 노드(글자는)는 다음 글자에 대한 최대 추천 우선순위를 갖고 있습니다. (최대 우선순위에 대한 글자도 역시 갖고 있습니다.) 만약 아래와 같은데이터가 있다면 AC 100 AB 10 A다음은 무조건 B가 추천됩니다. 왜냐하면 A노드는 우선순위가 가장 높은 다음글자를 기억하기 때문입니다. 추천 우선순위가C는 100이고 B는 10이기 때문입니다.

    -글자수를 세는 방법
    AB를 트라이에 find한다고 한다면 A노드의 다음 추천글자는 C입니다. 하지만 찾으려고 하는 문자는 AB이므로 B와 C는 다르므로
    해당 인덱스값인 2를 저장합니다. 따라서 모든 글자를 다쳐야하므로AB는 2가 나옵니다.

    AC를 find한다고 가정하면 A노드에서 C를 추천하고있는데 같은 C
    이므로 index를 증가시키지 않습니다. 결과적으로 index는 1이므로
    쳐야하는 글자는 1입니다.

    아래는 추가적으로 테스트해본글자 입니다.
    (주어진 문제와 제가 테스트 해본 글자는 모두 잘나옵니다.)

    1
    6 7
    A 10
    ABABC 1000
    ABABA 9
    AB 8
    ABCD 100
    AAAAAA 100000
    A ABABC ABABA AB ABCD AAAAAA DDDD
    A - 무조건 한글자를 쳐야하므로 1
    ABABC - A를 치면 AAAAAA가 추천될것이고 AB를 치면 됩니다.
    (AB + 탭 -> 3글자)
    ABABA - 모든 글자를 다쳐야 합니다(5글자)
    AB - 두글자를 다쳐야 합니다 (2)
    ABCD - ABC + 탭 -> 4
    AAAAAA -> A + 탭 -> 2
    DDDD -> 사전에 없으므로 4글자

    //
    //  main.cpp
    //  tri
    //
    //  Created by dookim on 3/30/15.
    //  Copyright (c) 2015 dookim. All rights reserved.
    //
    
    #include <iostream>
    #include <string.h>
    using namespace std;
    
    const int ALPHABETS = 26;
    
    int toNumber(const char ch) {
        return ch - 'A';
    }
    
    
    class TrieNode {
    public:
        TrieNode * nodes[ALPHABETS];
        int maxRecomValue;
        int nextRecomValue;
        bool terminal;
        //왜 배열 초기화를 해주는거지?
        //그럴 필요없는데 왜 memset해주는거지?
        TrieNode():terminal(false), maxRecomValue(-100), nextRecomValue(26) {
            memset(nodes, 0, sizeof(nodes));
        }
        ~TrieNode() {
            for(int i = 0; i < ALPHABETS; i++) {
                if(nodes[i] != NULL) {
                    delete nodes[i];
                }
            }
        }
        //root는 아무 문자열도 없다.
        void insert(const char * key, const char * origin, int recomValue) {
            int next = toNumber(*key);
    
            //현재 노드에서 다음 문자열에 대해서 한다.
            //루트는 따라서 배제한다.
            if(origin != key) {
                if(recomValue > maxRecomValue) {
                    nextRecomValue = next;
                    maxRecomValue = recomValue;
                } else if(recomValue == maxRecomValue) {
                    //next가 더작다는 소리이므로 알파벳 상으로.
                    if(nextRecomValue > next) {
                        nextRecomValue = next;
                    }
                }
            }
    
            //base condition
            if(*key == 0) {
                terminal = true;
                return;
            }
    
    
            if(nodes[next] == NULL) {
                nodes[next] = new TrieNode();
            }
    
    
            nodes[next]->insert(key + 1, origin, recomValue);
        }
        /*
    1
    6 6
    A 10
    ABABC 1000
    ABABA 9
    AB 8
    ABC 100
    AAAAAA 100000
    A ABABC ABABA AB ABC AAAAAA
    
         */
    
    
        //내가 생각 하는 input과 output은 해당 글자를 넣으면 해당 숫자가 나오는 것!
        //minIndex는 원래 1이다.
        //treeDepth 역시 0이다.
        TrieNode * find(const char * key, int & minIndex, int treeDepth) {
            //if it is terminal
            if(*key == 0) {
                return this;
            }
            int next=toNumber(*key);
    
            if(treeDepth != 0 && next != nextRecomValue) {
                minIndex = treeDepth + 1;
            }
            //다입력해야하는 경운데 find에서는 찾을 수 없다.
            if(nodes[next] == NULL) {
                minIndex = -1;
                return NULL;
            }
            return nodes[next]->find(key+1, minIndex, ++treeDepth);
        }
    
    
    };
    
    
    int main(int argc, const char * argv[]) {
        // insert code here...
        int testcase;
        scanf("%d", &testcase);
    
        for(int testIndex = 0; testIndex < testcase; testIndex++) {
            TrieNode node;
            int dicNum;
            int wordNum;
            scanf("%d", &dicNum);
            scanf("%d", &wordNum);
            for(int dicIndex = 0; dicIndex < dicNum; dicIndex++) {
                char str[10];
                int recomNum;
                scanf("%s", str);
                scanf("%d", &recomNum);
                node.insert(str, str, recomNum);
            }
            int tipingNum = 0;
            for(int wordIndex = 0; wordIndex < wordNum; wordIndex++) {
                int value = 0;
                char str[10];
                int index = 1;
                scanf("%s", str);
                size_t length = strlen(str);
                node.find(str, index, 0);
                //없거나 다쳐야지 만 추천이 되는경우.
                if(index == -1 || length == index) {
                    value = length;
                    tipingNum += length;
                } else {
                    //+1은 탭을 의미한다.
                    value = index + 1;
                    tipingNum += index + 1;
                }
                //cout<<value<<endl;
            }
            //띄어쓰기 만큼 더해준다.
            tipingNum += wordNum -1;
            cout<<tipingNum<<endl;
        }
    
        return 0;
    }
    
    }
    

    문단을 구분하기 위해 앞과 뒤에 빈 줄 하나씩을 반드시 추가하셔야 합니다.


    마지막으로 자주_하는_실수_모음 페이지를 읽으시면서 혹시 해당되는 사항이 있진 않은지 생각해 보세요.

    위 내용이 지켜지지 않은 질문은 답변이 오래 걸릴 수 있습니다.

    아래 '편집하기' 버튼을 눌러 글을 쓰실 수 있습니다.


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