백준 1181번 단어 정렬 C++ 문제 풀이

알파벳 소문자로 단어들이 주어지고,

1. 길이가 짧은 순, 2. 길이가 같다면 사전 순으로 정렬하는 문제입니다.

하지만 이어서 단, 중복된 단어는 하나만 남기고 제거해야 한다 라고 별로 안중요한 사소한 조건인것 처럼 세번째 조건을 달아둔게 열받네요.

 

처음 읽어보고는 파이썬 친화적인 문제라고 느껴졌고, C나 C++로 풀면 어렵지 않으려나 싶었습니다. 

그래서 더욱 C++로 풀어봤습니다. 

링크드리스트나 벡터 등등 고급스러운 자료구조들을 다룰 줄 알면 더욱 쉽게 풀 수 있을 것 같습니다.

다만 아직 잘 다루지 못해서 그냥 배열로 구현했습니다.

 

제가 접근한 방식은, 주어진 단어들을 알파벳 갯수별로 묶어서 짱박아두고, 

전부 입력받으면 나중에 사전 순 정렬해서 출력하기로 했습니다.

 

입력받을 단어들이 들어갈 arr[51][20000] 을 선언해주고,

(51인 이유는 배열이 0부터 시작하는데 단어수는 1부터 시작하니 통일시키기 귀찮아서입니다)

 

pivot[51]도 동시에 선언해줍니다. 이건 만들다가 막혀서 나중에 추가했습니다. 

(참고로 전역변수로 선언하는 이유는 C로 공부할때 전역변수로 선언하면 자동으로 0으로 초기화되는게 편해서 C++은 엄밀하게는 모르지만 초기화해줘야 한다면 귀찮을거같아서 입니다. 예전에 몇 번 찾아봤던거같은데 여러 언어들을 다루다보니까 까먹었습니다)

 

그뒤로 n개의 단어들을 입력받는데, arr 배열의 인덱스가 기괴해졌습니다.

풀어서 설명하자면,

1. 입력받은 단어의 글자수를 세서 세로 인덱스(row)로 설정합니다.

2. 하지만 해당 row에 이미 단어들이 존재할지도 모르니 다른 똑똑한 언어들의 append나 insert처럼 대충 알아서 C++의 배열에도 넣어주는 기능을 써야 하는데, 벡터나 링크드리스트 해시테이블 뭐 이런것들 잘 쓰면 될거같지만 이 문제는 그정도로 복잡하지는 않은 것 같아서 새로운 배열 pivot[51]을 만들었습니다.

3. pivot 배열의 인덱스는 row값과 같고, 원소는 단어의 등장 횟수와 같습니다.  = 글자수가 4인 단어가 2번 입력되었다면 pivot[4] = 2 가 됩니다.

4. 이를 이용해서 입력받은 단어가 위치할 column을 결정할 수 있는데, arr[row] + pivot[row] 가 해당 단어의 자리입니다.

5. 추가적으로 단어가 해당 row에 입력되었으므로 pivot[row] 의 원소값을 1 추가해줬습니다.

 

(요약하자면, 글자수를 기준으로(키값으로) 하는 50가지 배열에 글자수가 동일한 단어들끼리 묶어서 입력해줬습니다)

 

위의 과정으로 알파벳 갯수별로 단어들을 분류해서 전부 입력받았습니다.

 

이후에 pivot 배열에서 값이 0이 아닌 인덱스 ( 단어가 들어가 있는 arr 배열의 row )

를 for문으로 순환하며 단어가 들어가 있는 arr 배열의 row를 pivot[row]의 크기만큼 정렬해줍니다. (들어있는 단어들 정렬)

 

또한 정렬된 해당 row의 column들을 출력도 시켜줬습니다.

(물론 구상과 구현 모두 그렇게까지 시간복잡도가 늘어나지 않게끔 염두하긴 했습니다..)

 

그러나 맨위에 언급한 중복된 단어는 하나만 남겨야 하는 조건이 있어서 추가적으로 정렬된 row를 출력할때 

이전의 column 원소와 동일한 원소를 출력하려고 하면 스킵하는 구문을 넣어줬습니다. 결과적으로 동일하니 ok입니다.

 

 

 

 

 

 

 

 

 

#https://itre.tistory.com/
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

//모든 단어를 저장할 배열, row는 알파벳 갯수, col은 해당 알파벳 갯수로 구성된 단어들
string arr[51][20000];

//pivot배열로 각 row 별 몇 개의 단어가 들어가 있는지 확인
int pivot[51];

int main(void)
{

    int n;
    string word;

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> word;
        //단어가 입력되면, 먼저 알파벳 갯수를 세어 해당하는 arr 배열에서의 row를 배정하고, pivot 배열을 이용해서 몇 번째 col로 입력되어야 하는지 결정된다.
        //현재는 사전순은 고려하지 않고 입력된 순서로 자리를 할당해줌
        arr[word.length()][pivot[word.length()]++] = word;
    }

    for (int i = 1; i < 51; i++)
    {
        //col이 존재하는 row를 선택해서 수행
        if(pivot[i] != 0)
        {
            // 해당 row의 col 갯수만큼 정렬함
            sort(arr[i], arr[i] + pivot[i]);

            for (int j = 0; j < pivot[i]; j++)
            {
                //중복된 원소는 출력하지 않는다.
                if(j >= 1)
                {
                    if (arr[i][j] == arr[i][j-1])
                        continue;
                }

                cout << arr[i][j] << endl;
            }
        }
    }

}

 

댓글로 잘못된부분이나 개선할부분, 잘 이해안가는 부분 남겨주시면 감사하겠습니다.