Create a set to contain the full names of the departments already output. Each time you want to output a department, check if the set contains it already. If not, then output the department name and add it to the set.
For example:
Set<String> usedDepartments = new HashSet<String>();
Then in your loop:
if(!usedDepartments.contains(departmentList.get(empName))) {
department += j + ": " + departmentList.get(empName) + "\n";
j++;
usedDepartments.add(departmentList.get(empName));
}