C++ ] leetCode 1418 - Display Table of Food Orders in a Restaurant

 

 

리트코드 1418 문제

 

Given the array orders, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerNamei,tableNumberi,foodItemi] where customerNamei is the name of the customer, tableNumberi is the table customer sit at, and foodItemi is the item customer orders. 

Return the restaurant's “display table”. The “display table” is a table whose row entries denote how many of each food item each table ordered. The first column is the table number and the remaining columns correspond to each food item in alphabetical order. The first row should be a header whose first column is “Table”, followed by the names of the food items. Note that the customer names are not part of the table. Additionally, the rows should be sorted in numerically increasing order. 

 

 

Example 1: 

Input: orders = 

[["David","3","Ceviche"],

["Corina","10","Beef Burrito"],

["David","3","Fried Chicken"],

["Carla","5","Water"],

["Carla","5","Ceviche"],

["Rous","3","Ceviche"]] 

Output: 

[["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],

["3","0","2","1","0"],

["5","0","1","0","1"],

["10","1","0","0","0"]] 

Explanation: The displaying table looks like: 

Table	Beef Burrito	Ceviche	Fried Chicken	Water
3	0	2	1	0
5	0	1	0	1
10	1	0	0	0

 

For the table 3: David orders "Ceviche" and "Fried Chicken", and Rous orders "Ceviche". 

For the table 5: Carla orders "Water" and "Ceviche". 

For the table 10: Corina orders "Beef Burrito". 

 

 

Example 2: 

Input: orders = 

[["James","12","Fried Chicken"],

["Ratesh","12","Fried Chicken"],

["Amadeus","12","Fried Chicken"],

["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]] 

Output: 

[["Table","Canadian Waffles","Fried Chicken"],

["1","2","0"],["12","0","3"]] 

Explanation: 

For the table 1: Adam and Brianna order "Canadian Waffles". 

For the table 12: James, Ratesh and Amadeus order "Fried Chicken". 

 

 

Example 3: 

Input: orders = 

[["Laura","2","Bean Burrito"],

["Jhon","2","Beef Burrito"],

["Melissa","2","Soda"]] 

Output: 

[["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]] 

 

 

Constraints: 

• 1 <= orders.length <= 5 * 10^4 
• orders[i].length == 3 
• 1 <= customerNamei.length, foodItemi.length <= 20 
• customerNamei and foodItemi consist of lowercase and uppercase English letters and the space character. 
• tableNumberi is a valid integer between 1 and 500.

 

 

 

 

먼저 리턴할 displayTable 벡터의 행의 개수는 등장하는 테이블 개수 + 1이고, 열의 개수는 등장하는 요리 개수 + 1이다. 그리고 [0]열의 tabelNumber와 [0]행의 foodItem은 오름차순 정렬되어있어야 한다.

 

이걸 고려했을 때 가장 먼저 떠오른 자료구조는 map이 었다. map은 key에 따라 오름차순으로 자동정렬되기 때문이다. 이는 중복을 허용하지 않는 자료구조인 std::set도 마찬가지이다.

 

따라서 map<string, map<int, int>> tableOrder를 선언하고 <요리이름, <테이블넘버, 주문개수>를 저장한다. 그리고 set<int> tables로 등장하는 테이블넘버를 기억해 둔다. 테이블넘버를 int로 바꿔 저장하는 것은 자동으로 오름차순 정렬되도록 하기 위함이다.

 

orders.size()만큼 반복하면서 자료구조에 저장시키는데 map.insert() 대신 [key]로 접근해 값을 ++로 업데이트하는 방식을 사용하면 map에 중복된 키를 삽입하지 않으면서 값을 업데이트할 수 있다. 한편 set은 insert로 삽입하는데 중복요소를 삽입 시도하더라도 추가되지 않는다.

 

다음은 displayTable을 만들고 셀의 default값은 "0"으로 지정해둔다.

 

그리고 등장 테이블 개수인 tables.size() 만큼 행단위로 반복하는데, 그안에서 다시 등장 요리 개수인 tableOrder.size()만큼 반복하면서 해당 요리 map의 key에서 해당 테이블 넘버를 찾을 수 있는 경우 찾은 요소의 second인 주문개수를 해당 셀에 업데이트 하는 식으로 반복한다.

 

 

 

class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        map<string, map<int, int>> tableOrder;
        set<int> tables;

        for(int i = 0; i < orders.size(); i++) {
            tableOrder[orders[i][2]][stoi(orders[i][1])]++;
            tables.insert(stoi(orders[i][1]));
        }

        vector<vector<string>> displayTable(tables.size() + 1, vector<string>(tableOrder.size() + 1, "0"));
        displayTable[0][0] = "Table";
                        
        int i = 1;
        for(auto &t : tables) {
            displayTable[i][0] = to_string(t);
            int j = 1;
            for(auto &foodPair : tableOrder) {
                if(i == 1) displayTable[0][j] = foodPair.first;
                auto it = foodPair.second.find(t);
                if(it != foodPair.second.end()) displayTable[i][j] = to_string(it->second);
                j++;
            }           

            i++;
        }

        return displayTable;
    }
};