[2018 KAKAO BLIND RECRUITMENT] [3차] 파일명 정렬

https://programmers.co.kr/learn/courses/30/lessons/17686#qna

코딩테스트 연습 - [3차] 파일명 정렬 | 프로그래머스

 

 

이 문제는 우선순위 큐를 이용해서 쉽게 풀 수 있었다. 하지만, 35% 정답률에서 1시간 이상 소모했다. 이 이유는 아래에서 설명한다.

 

 

---

 

 

우선, 파일명와 숫자에 대해서 찾는 것은 쉽다. 숫자가 등장하는 인덱스를 활용하면 파일명과 숫자를 쉽게 구할 수 있다. 이 부분은 간단하지만, 정확하게 구현하지 않으면 1시간 이상 소모할 수 있다.

 

 

 

내가 실수한 부분은 다음과 같다.

 

// Make Number

        int temp = idx;

        for (; idx < files[i].size(); idx++) {

            if (!(files[i].at(idx) >= '0' && files[i].at(idx) <= '9')

                number = files[i].substr(temp, idx - temp);

                break;

            }

        }

 

 

위의 부분에서, 숫자가 아닌 문자가 등장할 때 number에 값을 넣도록 지정했다. 하지만, 이것은 fo001과 같은 파일명이 나올 때는 값이 들어가지 못한다. 

 

 

 

항상 문자열을 처리할 때는, 신중해야 하고 아닌 경우에 어떻게 되는지도 생각해야 한다.

 

 

 

실수한 코드를 정정하면, 아래와 같다.

 

 

// Make Number

        int temp = idx;

        for (; idx < files[i].size(); idx++) {

            if (!(files[i].at(idx) >= '0' && files[i].at(idx) <= '9') ||

                idx == files[i].size() - 1) {

                if (idx == files[i].size() - 1)

                    idx++;

                number = files[i].substr(temp, idx - temp);

                break;

            }

        }

 

 

 

 

---

 

 

해설코드(C++).

 

 

 

#include <string>

#include <vector>

#include <iostream>

#include <queue>

 

using namespace std;

 

typedef struct item {

    string pre;

    int number;

    int idx;

    item(string p, int n, int i) : pre(p), number(n), idx(i) {};

}item;

 

struct cmp {

    bool operator()(item i1, item i2) {

        if (i1.pre.compare(i2.pre) == 0) {

            if (i1.number == i2.number) 

                return i1.idx > i2.idx;

            else

                return i1.number > i2.number;

        }

        else

            return i1.pre.compare(i2.pre) > 0;

    }

};

 

string make_lowercase(string str) {

    for (int i = 0; i < str.size(); i++) {

        if (str[i] >= 'A' && str[i] <= 'Z')

            str[i] += 32;

    }

 

    return str;

}

 

int zero_delete(string str) {

    int i;

    string temp;

    for (i = 0; i < str.size(); i++) {

        if (str[i] != '0')

            break;

    }

    temp = str.substr(i, str.size() - i);

    i = atoi(temp.c_str());

    return i;

}

 

vector<string> solution(vector<string> files) {

    vector<string> answer;

    priority_queue<item, vector<item>, cmp> p_q;

    //

    string pre;

    string number;

    for (int i = 0; i < files.size(); i++) {

        // Make Pre

        int idx;

        for (idx = 0; idx < files[i].size(); idx++) {

            if (files[i].at(idx) >= '0' && files[i].at(idx) <= '9') {

                pre = make_lowercase(files[i].substr(0, idx));

                break;

            }

        }

 

        // Make Number

        int temp = idx;

        for (; idx < files[i].size(); idx++) {

            if (!(files[i].at(idx) >= '0' && files[i].at(idx) <= '9') ||

                idx == files[i].size() - 1) {

                if (idx == files[i].size() - 1)

                    idx++;

                number = files[i].substr(temp, idx - temp);

                break;

            }

        }

        cout << pre << " : " << number << endl;

        p_q.push(item(pre, zero_delete(number), i));

    }

 

    // Make Answer

    while (!p_q.empty()) {

        answer.push_back(files[p_q.top().idx]);

        p_q.pop();

    }

    return answer;

}