[정렬2] ABC, 수열 정렬, 전화번호부 목록,거북이

ABC

< 문제 >

오름차순 내림차순이 아니라

ABC를 통해 임의적으로 정렬하는 방식이다.

미리 배열을 정렬해두고

입력 받은 string 값을 charAt으로 접근하는 방식으로 문제를 해결 할 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
using namespace std;
 
int main(void)
{
    vector<int> numVector(3);
    for(int i=0; i<3; i++) {
        cin >> numVector[i];
    }
 
    sort(numVector.begin(), numVector.end());
 
    string abc;
    cin >> abc ;
    
    for(int i =0; i<3; i++) {
        cout << numVector[abc.at(i) - 'A'] << " "; //0, 1, 2의 결과를 얻는다.
    }
    
    return 0;
 
}

< 코드 >

수열 정렬

< 문제 >

문제는 다음과 같다.

< 그림 >

A 를 기준으로 Index를 정렬 시킨다.

정렬 시킨 인덱스는 P가 된다.

인덱스 순으로 P는 B가 된다.

 

알아둬야 하는 점은

pair를 품은 vector를 정렬 시에는

KEY 순으로 정렬된다.

 

이외에 페어의 입력이나, first, second와 같은 값에 주목하자.

 

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, b[51];
vector<pair<int,int> > v;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for(int i=0; i<n; i++) {
        int a;
        cin >> a;
        v.push_back(make_pair(a,i)); //pair 입력
    }
    sort(v.begin(),v.end()); //Key 순으로 정렬
    for(int i=0; i<n; i++) {
        b[v[i].second] = i; // second 속성
    }
    for(int i=0; i<n; i++) {
        cout << b[i] << " ";
    }
}
 

< 코드 >

전화번호 목록

< 문제 >

접두사에 중복을 확인하기 위해 정렬을 사용한 경우이다.

이외에도 꽤 중복을 처리하기 위해 정렬을 사용 하는 것 같다.

나 같은 경우에는 find메소드를 이용해서 구했는데,

컴파일러에 따라 리턴하는 값이 천치 만별인거 같다.

프로그래머스에서는 int형으로 반환 했지만

똑같은 코드를 다른 컴파일러에서 돌리면 메모리 주소가 반환되는 경우도 있다.

그래서 사실은 마지막 조건문은 다음과 같이 string::npos 처리하는 게 더 정확하다고 생각한다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(),phone_book.end());
    for(int i=0; i<phone_book.size(); i++){
        for(int j=i+1; j<phone_book.size(); j++) {
            int idx = phone_book[j].find(phone_book[i]);
            if(idx==0) { //if(phone_book[j].find(phone_book[i]) != string::npos) 이게 더 정확
                return false;
            }
        }
    }
    return answer;
}

이러한 문제를 아예 겪고 싶지 않다면 다음과 같은 좋은 코드도 있더라.

substr(시작인덱스,마지막인덱스)

메소드를 이용하여서 정확히 잘라 비교하였다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
bool solution(vector<string> phoneBook) {
    bool answer = true;
    sort(phoneBook.begin(), phoneBook.end());
    for ( int i = 0 ; i < phoneBook.size() - 1 ; i++ )
    {
        if ( phoneBook[i] == phoneBook[i+1].substr(0, phoneBook[i].size()) )
        {
            answer = false;
            break;
        }
    }
    return answer;
}

거북이

< 문제 >

네 수 중 버려도 되는 값도 있으니 직사각형을 만들라는 문제

직사각형은 가로 두개와 세로 두개로 이루어져 있고

두개의 가로와 세로는 같다.

여기서는 값을 일부 버려도 되니 각각의 작은 값이 가로 세로가 될 것이다.

그렇기 때문에 각각의 짝들이 차이가 많이 나지 않는 경우가 가장 큰 값이 될 것이다.

고로 정렬 후

첫번째 두번째

세번째 네번째가 짝이고

그 중 첫번째와 세번째의 곱이 넓이가 된다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int arr[4];
    cin >> arr[0] >> arr[1] >> arr[2] >> arr[3];
    sort(arr, arr + 4);
    cout << arr[0] * arr[2] << endl;
 
    return 0;
}

완주하지 못한 선수

< 문제 >

해시로 문제가 분류 되어 있지만,

무조건 하나만 다를 때는 정렬로도 문제를 해결 할 수 있다.

두 개의 배열을 정렬하고 비교하게 되면 다른 값을 찾을 수 있다.

만약 하나 짧은 배열의 사이즈 만큼 모두 돌아서 모두 같다면

긴 배열의 사이즈의 마지막이 값이다.

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    for(int i=0;i<completion.size();i++)
    {
        if(participant[i] != completion[i])
            return participant[i];
    }
    return participant[participant.size() - 1];
    //return answer;
}

< 코드 >

 

 

정렬 문제는 이만하면 됬지 않나... 싶다.

여튼 정렬 문제는 다음과 같은 특성들이 있다.

1. 중복을 체크할 수 있다.

2. 숫자를 문자로 바꾸어 정렬하여 특수한 정렬이 필요할 때가 있다.

(10의 자리 수를 일단 다 비교한 후 1의 자리 수를 비교 하는 등...)

3. 때론 정렬을 실제로 하지 않고 인덱스를 이미 정렬된 수열로 사용하여 문제를 해결하는 경우가 있다.