220103 TIL

Donghun Ha·2022년 1월 3일

목록 보기

4/6

PS(Problem solving) 8문제

문제	문제 제목
1259	팰린드롬수
2751	수 정렬하기 2
4153	직각삼각형
10250	ACM 호텔
10814	나이순 정렬
10816	숫자 카드 2
11650	좌표 정렬하기
11866	요세푸스 문제 0

새로 배운 점

정렬 함수인 sort의 세 번째 인자

sort 함수를 사용할 때, 일반적으로 sort(arr.begin(), arr.end()); 와 같이만 사용했는데, 세 번째 인자로 bool 형을 반환하는 함수를 주면 해당 함수를 기준으로 정렬된다.

// 10814 나이 순 정렬
#include <bits/stdc++.h>
using namespace std;;

vector<tuple<int, int, string> > v;
int n, age;
string name;

bool compare(tuple<int, int, string> a, tuple<int, int, string> b) {
    if (get<1>(a) == get<1>(b))
        return get<0>(a) < get<0>(b);
    return get<1>(a) < get<1>(b);
    // 문제의 조건이 나이 같은 경우, 들어온 순서(인덱스)
    // 아니면, 나이 순 오름차순으로 정렬한다.
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> age >> name;
        v.push_back({i, age, name});
	// 인덱스, 나이, 이름 순으로 넣어준다.
    }
    sort(v.begin(), v.end(), compare);
    // compare 함수 조건에 맞게 정렬된다.
    for (auto i: v) {
        cout << get<1>(i) << ' ' << get<2>(i) << '\n';
    }
}

upper_bound, lower_bound

upper_bound 함수를 통해 특정 값을 가진 마지막 iterator을 찾을 수 있고,
lower_bound 함수를 통해 특정 값을 가진 첫 iterator을 찾을 수 있다.

// 10816 숫자 카드 2

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

int n, m, c;
int b[500001];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> b[i];
	// n개 만큼의 숫자 카드를 입력 받아 배열에 넣어준다.
    sort(b, b + n);
    // 배열을 정렬하고,
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> c;
	// 앞에 배열에서, 새로 입력받은 케이스가 몇 개 인지 확인한다.
        auto upper = upper_bound(b, b + n, c);
        auto lower = lower_bound(b, b + n, c);
        cout << upper - lower << ' ';
	// 정렬된 배열에서 특정 값 마지막 - 처음 = 갯수
    }
}