프로그래밍

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

[난이도] Gold5
[유형] 정렬

[풀이]
각 열 문자로 만든 문자열을 뒤집고 vector에 넣고 정렬해줍니다.
정렬을 해주면 다음과 같은 입력이 주어졌을 때,

mrvica
mrvica
marica
mateja

아래와 같이 정렬이 됩니다.
0:aaaa
1:aarr
2:eiii
3:jccc
4:mmmm

문제의 조건은 결국 위 vector에서 인접한 문자열 두 문자열을 앞에서부터 비교했을 때,
같은 부분이 가장 긴 문자열의 길이를 찾으면 됩니다.

위의 예에서 0번과 1번을 비교했을 때, aa 이므로 이 값을 행의 길이에서 빼주고 1을 빼주면 됩니다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int r,c,k,mv;
string s[1000];
int main(){
    cin >> r >> c;
    for(int i=0;i<r;i++) cin >> s[i];
    vector<string> st(c);
    for(int j=0;j<c;j++)
        for(int i=r-1;i>=0;i--) st[j].push_back(s[i][j]);

    sort(st.begin(),st.end());
    for(int i=0;i<c-1;i++){
        int k=0;
        for(int j=0;j<r;j++){
            if(st[i][j]==st[i+1][j]) k++;
            else break;
        }
        mv=max(k,mv);
    }
    cout << r-mv-1;
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2866.cpp

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=395

[난이도] level2
[유형] 정렬

[풀이]
무게당 가격이 높은것부터 배낭에 넣으면 됩니다.
pair 배열에 {무게당 가격(Pi),금속의 무게(Mi)} 로 저장한 뒤 정렬하면
무게당 가격의 내림차순으로 정렬이 됩니다.
N-1번 금속부터 거꾸로 금속을 넣을 수 있을만큼 넣어으면서 금속의 가격을 계산해서 더해주면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int N,W,ans;
pair<int,int> v[1000000];
int main(){
    scanf("%d%d",&W,&N);
    for(int i=0;i<N;i++){
        int m,p;
        scanf("%d%d",&m,&p);
        v[i]={p,m};
    }
    sort(v,v+N);
    for(int i=N-1;i>=0,W>0;i--){
        int k = min(v[i].second,W);
        W-=k;
        ans+=k*v[i].first;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level2/금고털이.cpp

https://programmers.co.kr/learn/courses/30/lessons/85002

[난이도] level1
[유형] 정렬

[풀이]
정렬시 필요한 변수들을 저장하는 구조체를 선언한 뒤 그곳에 필요한 값들을 저장하고
comparator를 정의하여 정렬해주면 됩니다.

코틀린으로 구현시 sortedBy 함수를 이용하면 comparator를 따로 정의하지 않고도 쉽게 정렬이 가능합니다.

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int N;
struct P{
    int w,wl,b,c,idx;
};
P arr[1001];
bool cmp(const P& l,const P& r){
    if(l.w*r.wl > r.w*l.wl) return 1;
    else if(l.w*r.wl == r.w*l.wl) {
        if(l.b > r.b) return 1;
        else if(l.b==r.b) {
            if(l.c>r.c) return 1;
            else if(l.c==r.c){
                return l.idx < r.idx;
            }
        }
    }
    return 0;
}
vector<int> solution(vector<int> weights, vector<string> head2head) {
    vector<int> answer;
    N=weights.size();
    for(int i=0;i<N;i++){
        int w=0,l=0,ww=0;
        for(int j=0;j<N;j++){
            if(head2head[i][j]=='W') {
                w++;
                if(weights[j]>weights[i]) ww++;
            }
            else if(head2head[i][j]=='L') l++;
        }
        arr[i]={w,w+l,ww,weights[i],i};
    }
    sort(arr,arr+N,cmp);
    for(int i=0;i<N;i++) answer.push_back(arr[i].idx+1);
    return answer;
}

Kotlin

data class P(val w:Double,val ww:Int,val weight:Int,val idx:Int)
class Solution {
    fun solution(weights: IntArray, head2head: Array<String>): IntArray {
        val N=weights.size
        var arr = Array<P>(N){P(0.0,0,0,0)}
        for(i in 0..N-1){
            var w=0;
            var l=0;
            var ww=0
            for(j in 0..N-1) {
                if(head2head[i][j]=='W'){
                    w++
                    if(weights[j]>weights[i]) ww++
                }
                else if(head2head[i][j]=='L') l++
            }
            var wl = 0.0
            if(w+l!=0) wl = w.toDouble()/(w+l)
            arr[i] = P(wl,ww,weights[i],i)
        }
        return arr.sortedBy { it.idx }.sortedBy { -it.weight }.sortedBy { -it.ww }.sortedBy{-it.w}.map{it.idx+1}// .toIntArray()
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level1/위클리_챌린지.cpp

sortWith + 사용자정의 comparator

    var arr1 = mutableListOf(5,4,2,7,1)
    arr1.sortWith{a,b-> b.compareTo(a)} // [7, 5, 4, 2, 1]


    var arr2 = mutableListOf<Pair<Int,Int>>(Pair(1,3),Pair(2,5),Pair(2,4),Pair(6,2))
    arr2.sortWith{ a, b ->
        var k:Int = a.first.compareTo(b.first)
        when(k){
            0 -> a.second.compareTo(b.second)
            else -> k
        }
    } // [(1, 3), (2, 4), (2, 5), (6, 2)]
   
    println(arr1.toString())
    println(arr2.toString())

알고리즘 문제를 풀 때 문제에 따라 사용자 정의 comparator를 전달해서 정렬을 해야하는 경우가 종종 있습니다.

C++에서와 비슷하게 코틀린에서도 컬렉션 sortWith 메소드에 Comparator 구현체를 전달하면 사용자가 원하는 방식으로 정렬을 할 수 있습니다.

Pair도 역시 C++과 비슷한 방식으로 정렬이 가능합니다.

sortWith + compareBy / sortedBy

fun main(){

    var arr1 = mutableListOf<Pair<Int,Int>>(Pair(6,2),Pair(2,5),Pair(2,4),Pair(1,3))
    arr1.sortWith(compareBy({it.first},{it.second}))

    var arr2 = mutableListOf<Pair<Int,Int>>(Pair(6,2),Pair(2,5),Pair(2,4),Pair(1,3))
    var parr2 = arr2.sortedBy{it.second}.sortedBy{it.first}

    println(arr1.toString())  // [(1, 3), (2, 4), (2, 5), (6, 2)]
    println(parr2.toString()) // [(1, 3), (2, 4), (2, 5), (6, 2)]
}

우와 같이 sortWith에 comparator를 return해주는 compareBy를 전달하는 방법도 있습니다.

compareBy({1순위로 비교할 프로퍼티},{2순위로 비교할 프로퍼티}....) 처럼 넣어주면 됩니다.

위 예제에서는 it.frst, it.second를 순서로 전달함으로써 first를 우선으로 비교하고, 같으면 second로 비교해서 오름차순으로 정렬하라는 의미입니다.

sortedBy를 이용하는 방법도 있습니다.

sortedBy{비교할 프로퍼티} 으로 써주면 적어준 프로퍼티 기준으로 오름차순 정렬합니다.

arr2에서 해주는 것과 같이 pair의 second부터 정렬해주고, first를 정렬하면 first를 1순위, second를 2순위로 비교해서 정렬하는 것과 같은 효과입니다.