참조표준 라이브러리 컨테이너이분 탐색P0125

참조로 고치고 lower_bound로 찾기

물건 n개의 이름·가격·재고를 구조체(struct)의 std::vector에 담고, 명령 m개로 고친 뒤, 질의 q개에 답하라. 물건을 이름으로 찾는 함수는 vector 안의 원소를 참조(Item&)로 돌려주고, 고치는 함수는 그 참조를 받아 원소를 그 자리에서 바꾼다. 명령을 모두 처리한 뒤, 람다 비교 함수를 준 std::sort로 가격이 낮은 순, 가격이 같으면 이름의 사전 순으로 늘어놓는다.
질의에는 std::lower_bound로 답한다. 첫 줄에 n이, 다음 n줄에 "이름 가격 재고"가 주어진다. 그다음 줄에 m이, 다음 m줄에 명령이 "sell 이름 k", "restock 이름 k", "price 이름 p" 가운데 하나로 주어진다. sell은 재고가 k개 이상이면 k개를 빼고, 모자라면 아무것도 바꾸지 않는다.
restock은 재고에 k를 더한다.
price는 가격을 p로 바꾼다. 그다음 줄에 q가, 다음 q줄에 정수 x가 하나씩 주어진다. 질의마다, 늘어놓은 목록에서 가격이 x보다 낮은 물건의 수 c와 가격이 x 이상인 첫 물건을 "c 이름 가격 재고"로 출력한다.
그런 물건이 없으면 "c none"을 출력한다.

입력: 1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000, 1 ≤ q ≤ 1000.
이름은 영어 소문자 1 ~ 8글자이고 서로 다르며, 명령에는 있는 이름만 나온다.
1 ≤ 가격, p ≤ 1,000,000,000.
처음 재고는 0 ~ 1000, 1 ≤ k ≤ 1,000,000.
1 ≤ x ≤ 1,000,000,001(모두 정수)
출력: 질의마다 한 줄

예시 1 · stdin

4
pear 7 1
fig 7 2
apple 9 3
kiwi 2 4
3
sell fig 2
sell kiwi 5
price apple 7
4
7
3
1
8

stdout

1 apple 7 3
1 apple 7 3
0 kiwi 2 4
4 none

예시 2 · stdin

2
tea 10 5
jam 20 5
2
restock tea 3
price tea 30
3
20
21
31

stdout

0 jam 20 5
1 tea 30 8
2 none

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 1개 언어 풀이

이 문제는 vector 안의 원소를 참조(Item&)로 돌려주고 받는 방식과, 람다를 받는 std::sort·std::lower_bound를 연습하는 문제라 C++만 받아요(Java·Python·JS는 객체를 늘 참조로 다뤄서 고를 일이 없고, C#은 ref 반환이 있지만 클래스 객체는 늘 참조라 보통 쓰지 않아요.
C에는 참조가 없어 포인터를 써요).
크레이콘이라면 목록에 사전을 담아 정렬(비교함수)로 늘어놓고 이진 탐색을 직접 써요.
함정 넷: ① findItem이 Item&를 돌려줘도 auto item = findItem(...)으로 받으면 auto가 참조를 떼어 내서 복사본이 생겨요.
판 것도 바꾼 가격도 vector에 남지 않아요.
auto&나 Item&로 받아요.
② for (auto item : shelf) std::cin >> item.name ...도 복사본에 읽어 넣어서 vector는 빈 물건 그대로예요.
원소를 바꾸는 range-for는 auto&예요.
③ std::sort는 안정 정렬이 아니라서 같은 가격끼리의 차례가 정해져 있지 않아요.
비교 람다에 이름까지 적어야 해요(std::stable_sort를 써도 입력 차례가 될 뿐 이름 순은 아니에요).
④ lower_bound는 x 이상인 첫 원소, upper_bound는 x보다 큰 첫 원소라서, upper_bound를 쓰면 가격이 꼭 x인 물건을 건너뛰어요.
비교 람다의 매개변수 차례도 달라서 lower_bound는 (원소, 값), upper_bound는 (값, 원소)로 받아요.
찾은 반복자에서 shelf.begin()을 빼면 그 앞에 있는 물건 수 c가 돼요.
정렬은 명령을 모두 처리한 뒤에 해요.
가격이 바뀌면 자리도 바뀌니까요.

C++main.cpp · 66 줄

#include <algorithm>#include <iostream>#include <string>#include <vector> struct Item {    std::string name;    int price;    int stock;}; // 이름으로 찾아 vector 안의 원소 그 자체(참조)를 돌려준다. 이름은 반드시 있다Item& findItem(std::vector<Item>& shelf, const std::string& name) {    auto it = std::find_if(shelf.begin(), shelf.end(), [&](const Item& x) { return x.name == name; });    return *it;} // 바꾸는 함수는 Item&를 받는다: 복사본이 아니라 shelf 안의 원소를 바꾼다void update(Item& item, const std::string& op, int k) {    if (op == "sell") {        if (item.stock >= k) item.stock -= k;    } else if (op == "restock") {        item.stock += k;    } else {        item.price = k;    }} int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);     int n;    std::cin >> n;    std::vector<Item> shelf(n);    for (auto& item : shelf) std::cin >> item.name >> item.price >> item.stock;  // auto&: 원소에 바로 읽어 넣는다     int m;    std::cin >> m;    for (int i = 0; i < m; i++) {        std::string op, name;        int k;        std::cin >> op >> name >> k;        Item& item = findItem(shelf, name);  // auto&도 된다. auto만 쓰면 참조를 돌려받아도 복사한다        update(item, op, k);    }     // 가격 순, 같으면 이름 순. std::sort는 같은 것끼리의 차례를 지키지 않으니 이름까지 적는다    std::sort(shelf.begin(), shelf.end(), [](const Item& a, const Item& b) {        if (a.price != b.price) return a.price < b.price;        return a.name < b.name;    });     int q;    std::cin >> q;    for (int i = 0; i < q; i++) {        int x;        std::cin >> x;        // 가격이 x 이상인 첫 물건: lower_bound의 비교 함수는 (원소, 찾는 값) 차례로 받는다        auto it = std::lower_bound(shelf.begin(), shelf.end(), x,                                   [](const Item& item, int value) { return item.price < value; });        std::cout << (it - shelf.begin());        if (it == shelf.end()) std::cout << " none\n";        else std::cout << ' ' << it->name << ' ' << it->price << ' ' << it->stock << '\n';    }}