Harrix Блог

  • Списки статей
    • Все статьи
    • IT
    • Qt
    • C++
    • Сложение двух чисел
    • Web программированиe
    • FAQ
    • Latex
    • Установка программ
    • Мифы
    • Видео
    • Про фото
  • Проекты
  • Harrix.org
  • RSS
  • Контакты

Задача на Java: Список покупок

Разбор задачи на Java

10.04.2017 6 комментариев 7 730 просмотров

В статье рассматривается решение одной из задач на тему структур данных по курсу Java.

Содержание

  • Задача
  • Считывание входных данных
  • Сохраняем данные в структуре данных
  • Вывод результата на экран
  • Полный код решения задачи

Задача

Вы должны написать полностью программу на Java: необходимые директивы import, один public класс с именем Main в пакете по умолчанию (в коде отсутствует подстрока package) с функцией main()), которая решает задачу.

Ввод осуществляется с консоли, вывод – на консоль.

Программа должна работать точно по протоколу, который показан в примерах.

Например, нельзя выводить ничего лишнего, скажем, фразу “Введите N”.

Дана база данных о продажах некоторого интернет-магазина. Каждая строка входного файла представляет собой запись вида

1
Покупатель товар количество

, где Покупатель — имя покупателя (строка без пробелов), товар — название товара (строка без пробелов), количество — количество приобретенных единиц товара.

Создайте список всех покупателей, а для каждого покупателя подсчитайте количество приобретенных им единиц каждого вида товаров.

Входные данные
Вводятся сведения о покупках в указанном формате.

Выходные данные
Выведите список всех покупателей в лексикографическом порядке, после имени каждого покупателя выведите двоеточие, затем выведите список названий всех приобретенных данным покупателем товаров в лексикографическом порядке, после названия каждого товара выведите количество единиц товара, приобретенных данным покупателем. Информация о каждом товаре выводится в отдельной строке.

Пример входных данных

1
2
3
4
5
6
Ivanov paper 10
Petrov pens 5
Ivanov marker 3
Ivanov paper 7
Petrov envelope 20
Ivanov envelope 5

Пример выходных данных

1
2
3
4
5
6
7
Ivanov:
envelope 5
marker 3
paper 17
Petrov:
envelope 20
pens 5

Пример входных данных

1
2
3
4
5
6
7
8
9
10
11
12
13
Ivanov aaa 1
Petrov aaa 2
Sidorov aaa 3
Ivanov aaa 6
Petrov aaa 7
Sidorov aaa 8
Ivanov bbb 3
Petrov bbb 7
Sidorov aaa 345
Ivanov ccc 45
Petrov ddd 34
Ziborov eee 234
Ivanov aaa 45

Пример выходных данных

1
2
3
4
5
6
7
8
9
10
11
12
Ivanov:
aaa 52
bbb 3
ccc 45
Petrov:
aaa 9
bbb 7
ddd 34
Sidorov:
aaa 356
Ziborov:
eee 234

Считывание входных данных

Создадим консольное пустое приложение в Java.

1
2
3
4
5
6
public class Main {
 
    public static void main(String[] args) {
// write your code here
    }
}

Вначале разберемся с считыванием информации. Как видим из условий, данные нам приходят построчно. И в каждой строчке через пробел располагается три параметра. Логично считывать данные через Scanner с помощью nextLine(), а потом считанную строчку разделить на кусочки по пробелу.

В качестве остановки считывания можно использовать команду hasNext().

Правда возникнет проблема. Если на экземпляр Scanner подавать данные из файла, то с помощью hasNext() дойдем до символа EOF в конце файла и прекратим считывание строк. С консолью такое не прокатит. Поэтому для проверки работы программы в консоли эмулируем завершение цикла через ввод строки exit.

Итак, данный код позволяет считывать строчки до появления символа EOF или до ввода exit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner (System.in);
 
        while(sc.hasNext()) {
            String s = sc.nextLine();
            if(s.equals("exit")) {
                break;
            }
        }
        
    }
}

Теперь с помощью команды split() разобьем строчку на составные части и запишем в три переменные наши значения.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner (System.in);
 
        while(sc.hasNext()) {
            String s = sc.nextLine();
            if(s.equals("exit")) {
                break;
            }
 
            String[] parts = s.split(" ");
 
            String name = parts[0];
            String productName = parts[1];
            Integer count = Integer.parseInt(parts[2]);
        }
 
    }
}

Теперь мы на каждой итерации цикла знаем содержимое нужных нам переменных.

Сохраняем данные в структуре данных

Данная задача относится к курсе про структуры данных, поэтому их и будем использовать. Каждый покупатель имеет уникальное имя. Каждому покупателю соответствует список товаров. Причем и покупатели и товары должны быть отсортированы в алфавитном порядке.

Сюда напрашивается использование множества Set или карты Map. Приведу пример с использованием карты Map. Как мы знаем, в Java карта Map — это всего лишь интерфейс. Поэтому нужно будет либо создавать свой класс, либо использовать уже существующий. Наиболее известны из готовых HashMap (на основе хэш-значений ключей) и TreeMap (внутри строится дерево элементов по ключам).

По условию данные должны быть отсортированы, и этому требованию соответствует TreeMap.

В качестве ключа в карте было бы логично использовать имя покупателя. А что можно выбрать в виде значения в карте? Каждому покупателю соответствует список товаров. Так пусть в качестве значения в нашей карте будет выступать другая карта, которая будет хранить в качестве ключа название товара, а в качестве значения — его количество.

Получим в итоге вот такую карту.

1
TreeMap<String, TreeMap<String, Integer>> clients = new TreeMap<String, TreeMap <String, Integer>>();

Кусок кода с закидыванием информации в данное дерево я опишу в виде комментариев в коде.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//Если клиента с таким именем нет в карте, то мы закинем нового покупателя
//с пустой картой покупок
if (!clients.containsKey(name))
    clients.put(name, new TreeMap <String, Integer>());
 
//Сейчас в карте точно содержится покупатель с именем name
//Для удобства вытащим данного покупателя в отдельную переменную
TreeMap <String, Integer> temp = clients.get(name);
 
//Если у покупателя нет товара с наименованием productName, то закинем такой товар
// с количеством покупок равное 0
if (!temp.containsKey(productName))
    temp.put(productName,0);
 
//Теперь у покупателя точно есть товар с наименованием productName
//Вытащим текущее количество данного товара
Integer oldCount = temp.get(productName);
 
//Заменим значение товара с его количеством на новое значение
temp.put(productName, oldCount + count);

Получим.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.Scanner;
import java.util.TreeMap;
 
public class Main {
 
    public static void main(String[] args) {
        //Карта покупателей с картой покупок покупателя
        TreeMap<String, TreeMap<String, Integer>> clients = new TreeMap<String, TreeMap <String, Integer>>();
 
        Scanner sc = new Scanner (System.in);
 
        //Считываем строчки, пока можем
        while(sc.hasNext()) {
            String s = sc.nextLine();
 
            //Имитация завершения считывания строчек
            if(s.equals("exit")) {
                break;
            }
 
            //Считанную строчку делим на части
            String[] parts = s.split(" ");
 
            //Части строчек раскидываем по переменным
            String name = parts[0];
            String productName = parts[1];
            Integer count = Integer.parseInt(parts[2]);
 
            //Если клиента с таким именем нет в карте, то мы закинем нового покупателя
            //с пустой картой покупок
            if (!clients.containsKey(name))
                clients.put(name, new TreeMap <String, Integer>());
 
            //Сейчас в карте точно содержится покупатель с именем name
            //Для удобства вытащим данного покупателя в отдельную переменную
            TreeMap <String, Integer> temp = clients.get(name);
 
            //Если у покупателя нет товара с наименованием productName, то закинем такой товар
            // с количеством покупок равное 0
            if (!temp.containsKey(productName))
                temp.put(productName,0);
 
            //Теперь у покупателя точно есть товар с наименованием productName
            //Вытащим текущее количество данного товара
            Integer oldCount = temp.get(productName);
 
            //Заменим значение товара с его количеством на новое значение
            temp.put(productName, oldCount + count);
        }
 
    }
}

Проверяем наличие записи по ключу в карте через containsKey().

Помним, что в записи TreeMap <String, Integer> temp = clients.get(name); переменная temp хранит ссылку на элемент карты. И изменения в данной переменной приведут к изменениям в элементе карты. Что нам и надо.

И обратите внимание на строчку temp.put(productName, oldCount + count);. Мы знаем, что в карте товаров точно есть запись с ключем productName. Нам нужно значение элемента с этим ключем поменять на новое. Напрямую это не получится сделать. Но мы помним, что есть в карту добавить элемент с существующим уже ключем, то мы перепишем значение элемента с данным ключем. Чем мы воспользовались в данной строчке.

Вывод результата на экран

Фактически после заполнения карты clients в этой карте мы имеем все наши данные в нужном порядке. Есть клиенты, отсортированные в алфавитном порядке. В каждом клиенте (покупателе) есть отсортированный массив товаров, причем товары не повторяются, а повторы по количеству товаров сложились друг с другом. Остается только вывести результат.

Будем использовать foreach. Обратите внимание, что с картой данный цикл имеет специфический вид.

Например, для TreeMap<String,Integer> получим следующий цикл.

1
2
3
4
5
6
for(Map.Entry<String,Integer> entry : treeMap.entrySet()) {
  String key = entry.getKey();
  Integer value = entry.getValue();
 
  System.out.println(key + " => " + value);
}

По аналогии сделаем цикл для прохода нашей карты.

1
2
3
4
5
6
for(Map.Entry<String, TreeMap <String, Integer>> entry : clients.entrySet()) {
    String key = entry.getKey();
    TreeMap <String, Integer> value = entry.getValue();
 
    System.out.println(key + ":");
}

Этот цикл выведет имена покупателей и знак двоеточия. Теперь нужно внутри каждой итерации цикла вывести список товаров. Там у нас также карта, так что действуем по аналогии.

1
2
3
4
5
6
7
8
9
10
11
12
13
for(Map.Entry<String, TreeMap <String, Integer>> entry : clients.entrySet()) {
    String key = entry.getKey();
    TreeMap <String, Integer> value = entry.getValue();
 
    System.out.println(key + ":");
 
    for(Map.Entry<String,Integer> product : value.entrySet()) {
        String keyProduct = product.getKey();
        Integer valueProduct = product.getValue();
 
        System.out.println(keyProduct + " " + valueProduct);
    }
}

Всё задача решена.

Полный код решения задачи

Приведем теперь окончательный код программы.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package org.harrix;
 
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
 
public class Main {
 
    public static void main(String[] args) {
        //Карта покупателей с картой покупок покупателя
        TreeMap<String, TreeMap<String, Integer>> clients = new TreeMap<String, TreeMap <String, Integer>>();
 
        Scanner sc = new Scanner (System.in);
 
        //Считываем строчки, пока можем
        while(sc.hasNext()) {
            String s = sc.nextLine();
 
            //Имитация завершения считывания строчек
            if(s.equals("exit")) {
                break;
            }
 
            //Считанную строчку делим на части
            String[] parts = s.split(" ");
 
            //Части строчек раскидываем по переменным
            String name = parts[0];
            String productName = parts[1];
            Integer count = Integer.parseInt(parts[2]);
 
            //Если клиента с таким именем нет в карте, то мы закинем нового покупателя
            //с пустой картой покупок
            if (!clients.containsKey(name))
                clients.put(name, new TreeMap <String, Integer>());
 
            //Сейчас в карте точно содержится покупатель с именем name
            //Для удобства вытащим данного покупателя в отдельную переменную
            TreeMap <String, Integer> temp = clients.get(name);
 
            //Если у покупателя нет товара с наименованием productName, то закинем такой товар
            // с количеством покупок равное 0
            if (!temp.containsKey(productName))
                temp.put(productName,0);
 
            //Теперь у покупателя точно есть товар с наименованием productName
            //Вытащим текущее количество данного товара
            Integer oldCount = temp.get(productName);
 
            //Заменим значение товара с его количеством на новое значение
            temp.put(productName, oldCount + count);
        }
 
        //Выведем наши данные из карты в нужном формате
        for(Map.Entry<String, TreeMap <String, Integer>> entry : clients.entrySet()) {
            String key = entry.getKey();
            TreeMap <String, Integer> value = entry.getValue();
 
            //Выводим имя покупателя
            System.out.println(key + ":");
 
            //Выводим вторым циклом список товаров с их количеством
            for(Map.Entry<String,Integer> product : value.entrySet()) {
                String keyProduct = product.getKey();
                Integer valueProduct = product.getValue();
 
                System.out.println(keyProduct + " " + valueProduct);
            }
        }
    }
}

Для тестирующей системы удаляем строчку package и все комментарии (так как содержат кириллицу).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
 
public class Main {
 
    public static void main(String[] args) {
        TreeMap<String, TreeMap<String, Integer>> clients = new TreeMap<String, TreeMap <String, Integer>>();
 
        Scanner sc = new Scanner (System.in);
 
        while(sc.hasNext()) {
            String s = sc.nextLine();
 
            if(s.equals("exit")) {
                break;
            }
 
            String[] parts = s.split(" ");
 
            String name = parts[0];
            String productName = parts[1];
            Integer count = Integer.parseInt(parts[2]);
 
            if (!clients.containsKey(name))
                clients.put(name, new TreeMap <String, Integer>());
 
            TreeMap <String, Integer> temp = clients.get(name);
 
            if (!temp.containsKey(productName))
                temp.put(productName,0);
 
            Integer oldCount = temp.get(productName);
 
            temp.put(productName, oldCount + count);
        }
 
        for(Map.Entry<String, TreeMap <String, Integer>> entry : clients.entrySet()) {
            String key = entry.getKey();
            TreeMap <String, Integer> value = entry.getValue();
 
            System.out.println(key + ":");
 
            for(Map.Entry<String,Integer> product : value.entrySet()) {
                String keyProduct = product.getKey();
                Integer valueProduct = product.getValue();
 
                System.out.println(keyProduct + " " + valueProduct);
            }
        }
    }
}


Статьи по теме:

  1. Создание простейшего приложения в Android Studio
  2. Установка связки Android Studio и Eclipse
  3. Сложение двух чисел в Android Studio на Java (Android приложение)
  4. Подключение существующей БД SQLite в Android Studio

IT Java, TreeMap

© 2014 Harrix