프로그래머스 2024.01.15 (1Lv 문자열 내 마음대로 정렬하기)

문제

---

문제 설명
문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다.

제한 조건
   ◈ strings는 길이 1 이상, 50이하인 배열입니다.
   ◈ strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
   ◈ strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
   ◈ 모든 strings의 원소의 길이는 n보다 큽니다.
   ◈ 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

입출력 예

strings	n	return
["sun", "bed", "car"]	1	["car", "bed", "sun"]
["abce", "abcd", "cdx"]	2	["abcd", "abce", "cdx"]

입출력 예 설명
입출력 예 1
"sun", "bed", "car"의 1번째 인덱스 값은 각각 "u", "e", "a" 입니다. 이를 기준으로 strings를 정렬하면 ["car", "bed", "sun"] 입니다.

입출력 예 2
"abce"와 "abcd", "cdx"의 2번째 인덱스 값은 "c", "c", "x"입니다. 따라서 정렬 후에는 "cdx"가 가장 뒤에 위치합니다. "abce"와 "abcd"는 사전순으로 정렬하면 "abcd"가 우선하므로, 답은 ["abcd", "abce", "cdx"] 입니다.

코딩

---

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(pair<string, char> a1, pair<string, char> a2)
{
    if (a1.second == a2.second)
    {
        int idx = 0;
        while (true)
        {
            if (a1.first[idx] == a2.first[idx])
            {
                if (idx <= a1.first.length()
                    && idx <= a2.first.length())
                {
                    idx++;
                }
            }
            else
            {
                return a1.first[idx] < a2.first[idx];
            }
        }
    }
    else
    {
        return a1.second < a2.second;
    }
}

vector<string> solution(vector<string> strings, int n) {
    vector<string> answer;

    vector<pair<string, char>> answer2 = {};
    for (int i = 0; i < strings.size(); ++i)
    {
        answer2.push_back(make_pair(strings[i], strings[i][n]));
    }
    
    sort(answer2.begin(), answer2.end(), compare);

    for (int i = 0; i < answer2.size(); ++i)
    {
        answer.push_back(answer2[i].first);
    }

    return answer;
}

 

해당 문제를 풀때, 정렬을 편하게 하기 위해 가장 먼저 algorithm에 있는 sort() 함수를 떠올렸다.

하지만, strings의 n번째를 compare 함수에 전달을 해주는 부분에서 잠깐 시간이 걸렸다.

생각해낸 방법은

1. 전역변수를 하나 두어 n을 전달해 compare 함수에서도 인자를 따로 전달 받지 않아도 되도록 하는 것과

2. pair로 묶어 문자열 n번째 문자를 묶어 전달하는 것이었다.

(이러한 이유는 sort()의 compare()함수를 만들때, 컨테이너 자료형 2개만 인자로 받아야하기 때문이다.
예를 들어 vector<int> tempvector를 정렬하고자 하면, compare(int ia1, int ia2)등으로 받아야하는데, n을 전달하고자 compare(int ia1, int ia2, int idx)로 만들면 sort()함수에 전달할때 인자가 부족해 에러가 발생한다. 혹시 이런식으로 만드는게 가능하다면 방법을 알려주셨으면 좋겠습니다.)

 

생각해낸 두가지 방법중 make_pair를 이용해 묶어 전달하는 방법을 택하였다.

 

따라서 인자로 전달받은 strings를 순회하며, n번째 문자를 묶어서 answer2라는 변수에 저장해두었다.

이후 sort()함수에서 호출되는 compare함수에서 second에 위치한 n번째 문자를 비교해 오름차순으로 정렬해 주었다.

 

이렇게만 해도 예제 문제는 충분했지만, 예외 상황이 존재했다.

간혹 "edc", "ed"가 주어지면, 사전순에 따라 "ed", "edc"가 반환 되어야하고,

"ebcc", "abcc"가 주어지고 idx인 n이 2였다면, c, c로 동일하기 때문에 사전순인 "abcc", "ebcc"가 되어야 한다.

두가지 예외 상황이 있는데, 이중 첫번째만 예외처리를 해서 생각해내는데 시간이 좀 걸렸다.

 

처음 경우는 모든 글자가 동일한데, 길이만 다르면 사전순에 따라 길이가 긴쪽이 후순위 이고,

두번째 경우는 주어진 n의 문자가 동일하면, 사전순으로 정렬하기 위해 제일 첫 문자부터 다시 확인해야 했다.

 

이 두가지 예외처리를 위해 compare()에 조건문을 걸어 처리해주었다.

실행 결과

---