BOJ 20977 - JOI ソート (JOI Sort) 링크
(2023.07.05 기준 B2)

문제

N개의 문자로 이루어진 문자열 S가 있다. 모든 문자는 'J', 'O', 'I' 중 하나이며, 'J'가 'O'보다 앞으로, 'O'가 'I'보다 앞으로 오게끔 정렬하고자 한다. 정렬된 문자열 출력

알고리즘

간단한 문자열 정렬

풀이

내장된 기본 sort로는 정렬 조건을 충족시키지 못한다. 'I', 'J', 'O' 순이기 때문.
그러므로 우리가 직접 정렬 기준이 되는 compare 함수를 만들어야 한다.

'J'는 우선순위가 가장 높으므로 숫자 0, 'I'는 그 다음 우선순위이므로 숫자 1, 'O'는 마지막 우선순위이므로 숫자 2로 생각하자. 그리고 정렬하게끔 하면 된다. 이는 설명보다 코드를 직접 보는 것이 이해가 빠를 것이다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int priority(char c){
    if (c == 'J') return 0; // J는 첫번째 우선순위
    if (c == 'O') return 1; // O는 두번째 우선순위
    return 2; // I는 세번째 우선순위
}

bool comp(char a, char b){
    return priority(a) < priority(b);
}

int main(){
    int N; string S;
    cin >> N >> S;

    sort(S.begin(), S.end(), comp); // 정렬 기준을 comp 함수로 정하여 정렬
    cout << S;
}

• Python

def comp(c):
    if c == 'J': # J는 첫번째 우선순위
        return 0
    if c == 'O': # O는 두번째 우선순위
        return 1
    return 2 # I는 세번째 우선순위

N = int(input())
S = input().strip()

for c in sorted(S, key = lambda x: comp(x)): # 정렬 기준인 key를 comp 함수로 정하여 정렬
    print(c, end = '')

여담

문자열 개수를 세어 순서대로 개수만큼 출력하는 방법도 있다. 참고하자.

그리고 Python에서

print(''.join(sorted(S, key = lambda x: comp(x))))

join을 이용하여 for문을 쓰지않고 한번에 출력할 수 있지만, 이 방법은 문자 하나하나를 합친 하나의 문자열로 만든 후 출력하기 때문에 느리다는 것을 알고 있자.