[99클럽 코테 스터디 31일차 TIL] #정렬6

31일 차입니다. 후,, 오늘 알바를 도와달라고 해서 지원 갔는데 오늘 예약인원이 합쳐서 무려 80명 단체손님이더라고요. 힘들어 죽는 줄 알았어요. (이 정도면 시급 더블해줘야 해,,) 그래도 집에 와서 눕지 않고 지친 몸을 이끌고 노트북 앞에 앉았습니다 ㅎㅎ,, 오늘도 파이팅 해볼게욧^^

 

 

문제 설명

---

우선 두 숫자를 줌으로써 범위가 주어집니다. 범위 사이에 있는 수를 문자로 표현하고, 사전순으로 배열하여 사전순대로 원래숫자 배열해 출력하라는 단순해 보이는 문제였습니다.

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

 

 

생각 흐름

---

문제를 보자마자 적은 정보량에 좋아하면서 읽기 시작했습니다.

 

하지만 은근 생각을 해야 하는 문제더라고요.

숫자 2개가 주어지면 그 사이에 있는 수들을 문자로 표현해 사전순으로 배열한 후, 이들의 원래 수를 사전순으로 출력하는 문제였습니다.

 

음,, 문자로 표현하는 것, 이를 사전순으로 정렬하는 게 키포인트다라고 생각을 한 후 천천히 코드를 짜보았습니다.

 

우선순위 큐 찬양론자로써, 우선순위 큐를 사용하기로 맘을 먹고 우선 숫자문자를 담은 string vector와 우선순위큐 pq를 선언해 주었습니다.

 

깊게 생각해 보니 i를 m부터 n까지 반복문을 돌리는데 두 자릿수의 경우 십의 자릿수와 일의 자릿수를 구분해서 또 문자를 넣어줘야 한다는 생각에 이를 따로 변수를 두어 이를 일일이 우선순위 큐에 저장해 주었습니다.

 

이렇게 저장을 하고 출력을 하려고 하는데 그러고 보니 원형 숫자는 어떻게 출력하지...라는 고민에 빠졌습니다.

문자열 우선순위 큐속 문자열들을 다시 숫자로 바꿔야 하는데 어떻게 일일이 바꿀 것이며 이를 바꾸는 행위가 너무 비효율적이라는 생각을 하였습니다.

 

#include <iostream>
#include <string>
using namespace std;

int main () {
    ios_base::sync_with_stdio();
    cin.tie(); cout.tie();

    int m, n;
    cin >> m >> n;

    string alphabet [10]= {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    priority_queue <string, vector<int>, greater<int>> pq; // 사전순으로 오름차순 정렬하게 만들어야 함

    for (int i = m; i <= n; i++) {
        int ten = i / 10;
        int one = i % 10;

        if (ten == 0) {
            pq.push(alphabet[i]); // 일의 자리수에 해당하는 문자 넣기
        }
        else {
            pq.push(alphabet[ten]+alphabet[one]); // 십의 자리수, 일의 자리수에 해당하는 문자 넣기
        }
    }

    // 그렇다면 오름차순으로 정리됐을 거임

    while (!pq.empty()) {
        string top = pq.top(); // 사전순으로 가장 낮은 문자를 top으로 선언
        int index = alphabet.find(top);

        int ten2 = num / 10;
        int one2 = num % 10;




    }

    return 0;
}

 

그래서 때려치우고 빠르게 다시 코드를 작성하기로 다짐했습니다.

 

결국 원형의 숫자를 같이 담아두는 게 맞는구나 라는 생각으로 두 개의 자료를 담을 수 있는 pair vector를 써야겠다는 생각을 하였고

 

vector <pair <string, int>> v; // 숫자를 문자열로 바꾼 것과 그 숫자를 나란히 저장할 벡터를 선언해 주었습니다.

 

그 뒤는 위의 코드에서 적용한 개념을 적용해 십의 자릿수와 일의 자릿수를 각각 문자열로 저장해 주었고 그 뒤에 원형 숫자를 같이 저장해 주었습니다.

 

그리고 sort() 함수를 통해 사전순으로 정렬해 준 뒤 출력은 각 v [i]. second를 출력하며 마무리하였습니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main () {
    ios_base::sync_with_stdio();
    cin.tie(); cout.tie();

    int m, n;
    cin >> m >> n;

    string alphabet [10]= {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    vector <pair <string, int>> v; // 수를 문자로 표현한 것과 그 숫자를 저장할 pair vector v 선언

    for (int i = m; i <= n; i++) {
        if (i >= 10) {
            v.push_back({alphabet[i/10]+ " " + alphabet[i%10], i});
        }
        else {
            v.push_back({alphabet[i%10], i});
        }
    }

    sort (v.begin(), v.end()); // 오름차순으로 저장

    for (int i = 0; i < v.size(); i++) {
        cout << v[i].second << " ";  
    }

    return 0;
}

 

 

완벽하게 문제풀이가 끝났다고 생각했는데 출력형식이 잘못됐다는 오류가 뜬 겁니다.

 

뭐지,, 뭐지 고민하다가 출력값이 10개 단위로 줄 바꿈이 되어 있다는 것을 그때 돼서야 깨달아버렸습니다.

바로 조건문 한 줄 추가하여 풀이를 마무리하였습니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main () {
    ios_base::sync_with_stdio();
    cin.tie(); cout.tie();

    int m, n;
    cin >> m >> n;

    string alphabet [10]= {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    vector <pair <string, int>> v; // 수를 문자로 표현한 것과 그 숫자를 저장할 pair vector v 선언

    for (int i = m; i <= n; i++) {
        if (i >= 10) {
            v.push_back({alphabet[i/10]+ " " + alphabet[i%10], i});
        }
        else {
            v.push_back({alphabet[i%10], i});
        }
    }

    sort (v.begin(), v.end()); // 오름차순으로 저장

    for (int i = 0; i < v.size(); i++) {
        cout << v[i].second << " ";
        if (i % 10 == 9) cout << '\n';    
    }

    return 0;
}

 

 

공부한 내용 정리

---

오늘 코드를 짜면서 뭔가 공부할 만 게 안 보인다~ 싶을 땐 뭐,, 정답은 구글링을 통해 다른 사람 코드보기죠.

 

우선 구글링을 해보았습니다. 많은 코드들이 뜨더라고요.

보니까 제일 첫 번째로 뜨는 코드가 제 코드랑 거의 똑같더라고요. 여기서 또 뿌듯함을 느꼈습니다.

 

다른 분들의 코드도 찾아보는데 결국은 비슷한 방법으로 푸시더라고요. 근데 제 코드가 더 간결하고 좋아 보였었습니다.

 

정렬관련된 문제는 이제 어느 정도 익숙해진 것 같아요. 다음에도 잘 풀어보겠습니다.