백준 #1302

https://www.acmicpc.net/problem/1302

---

입력으로 책의개수와 팔린 책의이름을 받는다.

가장많이 팔린 책의 이름을 사전순으로 가장 앞서는것을 출력한다.

 

 

 

---

문제 접근방법

나는  이 문제를 보고 해쉬테이블을 떠올렸다. 각 셀에 책을 넣고 같은 이름일때  해당 셀의 카운트를 올려주고 비교하면 되겠다고 생각했기때문이다. 

struct cell {
    int count;      //해당 책의 팔린수
    string value;   //책의 이름
    cell() {
        value = " ";
        count = 0;
    }
    cell(string data) {
        this->value = data;
        count = 1;
    }

    void use() {         //같은이름의책이 들어왔을때
        count++;
    }
    int returncount() {  //해당 책의 팔린숫자
        return this->count;
    }
    bool empty() {        //해당셀이 비어있는지
        return this->value == " ";
    }
};

해쉬테이블의 각 셀을 이렇게 구성하였고 나는 각셀의 함수를 만들어주는걸 선호해서 만들어주었다.

 void insert(string data) {//삽입함수
        for (int i = 0; i < capacity; i++) {
            if (arr[i].value == data) {     //이미 책이 등록되어 있을 때
                arr[i].use();      //count를 올려준다.
                return;
            }
            else if (arr[i].empty()) {        //해당 책이 테이블에 없을때
                arr[i].value = data; 		
                arr[i].count = 1;  				//책을 등록해준다.
                size++;
                return;
            }
        }

    }

각 책을 입력받을때마다 insert를 호출해서 처리해주었다.

 a b(n);    //객체생성
    for (int i = 0; i < n; i++) {  //책입력과정
        string cmd;
        cin >> cmd;
        b.insert(cmd);
    }


    int max = -1;      //책의 최대판매량을 저장해줄 임시변수
    string result = " ";     

    for (int i = 0; i < b.size; i++) {
        int num = b.arr[i].returncount();               //도서의 판매량을 받기
        string s = b.arr[i].value;
        if (max < num) {                                 
            max = num;
            result = s;
        }
        else if (max == num) {
            if (result.size() == s.size()) {
                for (int j = 0; j < result.size() && j < s.size(); j++) { 
//만일 최대값이 같은 두 도서가있다면 첫째자리부터 비교해서 사전순으로 앞서는 책을 할당한다
                    if (result[j] > s[j]) {
                        max = num;
                        result = s;
                        break;
                    }
                    else if (result[j] < s[j]) {
                        break;
                    }
                }
            }

처음에 여기까지만 구현을했는데 50몇퍼센트에서 계속 오답처리를 받았었다. 그래서 이것저것 바꾸면서 시도하던 도중에 

한가지가 떠올랐다  만약     ab와 abc가 같은 판매량이면 어떻게 될까?   그러니까 나는 각 이름의 자리수까지는 고려를 하지못했던것이다.  ab와abc같은 경우에는 두번째자리까지 알파벳이 같은데 위에코드 에서는 세번째 자리를 비교해야하는데 처리를 하지 않았으니 오답이 였던 것이다.

 else if (result.size() > s.size()) {     //result의 길이가 더 길때
                for (int j = 0; j < s.size(); j++) {  
                    if (result[j] > s[j]) {
                        max = num;
                        result = s;
                        break;
                    }
                    else if (result[j] < s[j]) {
                        break;
                    }
                    if (j == s.size() - 1) {  //끝까지 비교가안된다면 더짧은 책이 우선이다.
                        max = num;
                        result = s;
                    }
                }
            }
            else if (result.size() < s.size()) {
                for (int j = 0; j < result.size(); j++) {
                    if (result[j] > s[j]) {
                        max = num;
                        result = s;
                        break;
                    }
                    else if (result[j] < s[j]) {
                        break;
                    }
                    if (j == result.size() - 1) {
                        break;
                    }
                }
            }
        }
    }

그래서 각 자리수까지 고려하여 코드를 짰더니 정답을 맞출수있었다.

---

시간복잡도는 최악의경우 천권의 책이 모두 다른이름이고 각 판매량이 같은 책들이 이름의 49번째 알파벳까지 같을 때 O(n^2)시간이 걸린다.

---

느낀점: 거의 처음으로 알고리즘을 접하면서 많이 고민하게 되었던것같다. 더 좋은 방법을 찾아보려고 노력하는것도 재밌는것같다.