[코딩도장] 아마존 입사문제

아마존 면접 문제로 알려진 “그 시간 사무실에 몇 명이 있었나?”를 풀어보았습니다.

문제는 아래와 같습니다.

A 사무실에 특정일자의 출퇴근 시간이 기록된 거대한 로그파일이 있다고 한다. 파일의 형식은 다음과 같다.(한 라인에서 앞 부분은 출근시간(HH:MM:SS), 뒷 부분은 퇴근시간이다) 09:12:23 11:14:35 10:34:01 13:23:40 10:34:31 11:20:10 특정 시간을 입력(예: 11:05:20)으로 주었을 때 그 시간에 총 몇 명이 사무실에 있었는지 알려주는 함수를 작성하시오.

기본적으로 두 가지 가정하에 문제를 접근해 보았습니다.

1. 로그 파일에 출근시간은 정렬이 되어 있다.
2. 자정을 넘기지 않고 당일날 퇴근한다.

1번의 경우 가정하지 않더라도 정렬 작업을 수행하면 되지만, 2번의 경우는 가정이 없다면 다소 복잡해집니다.

가장 쉬운 방법은 출근시간을먼저 비교하고 퇴근시간을 비교하는 방법입니다. 현재 사무실에 있으려면 출근시간 < 특정 시간(입력값) < 퇴근시간이 되어야 합니다.

로그 파일에 존재하는 모든 출/퇴근 시간을 비교할 수도 있지만 이는 다소 비효율적인 방법입니다. 하지만 1번 가정에서 출근시간이 정렬되어 있다면, 특정 시간(입력값) < 출근시간이 되면 더 이상 찾지 않아도 됩니다.

알고리즘을 정리해 보면 아래와 같습니다.

1. 로그 파일에서 한 줄씩(한 명의 출퇴근 정보)를 가져온다.
2. 특정 시간과 비교하여 출근시간이 늦다면 비교를 멈춘다.
3. 특정 시간과 비교하여 퇴근시간이 늦다면 사무실에 일하는 직원 수를 한 명 더한다.
4. 1 ~ 3번을 계속 반복한다.

이를 구현한 코드는 아래와 같습니다.(java 8로 구현)

public class EmployeeCounter {     public long countWorkingEmployees(Stream<String> commutingTimes, String now) {         Stream<String> workingEmployees = commutingTimes.filter((commutingTime) -> isEmployeeWorking(commutingTime, now));         return workingEmployees.count();     }     /**      * 시간값은 HH:MM:SS 형식으로 전달된다고 가정한다.      * @param commutingTime 출퇴근 시간      * @param now 현재 시간      * @return 근무여부      */     private boolean isEmployeeWorking(String commutingTime, String now) {         String[] comTime = StringUtils.split(commutingTime, " ");         if (now.compareTo(comTime[0]) < 0) { //출근시간 > now             return false;         } else if (now.compareTo(comTime[1]) > 0) {    //퇴근시간 < now             return false;         } else {             return true;         }     } }

public class EmployeeCounterTest {     private List<String> commutingTime = new ArrayList<String>() {         {             add("09:12:23 11:14:35");             add("10:34:01 13:23:40");             add("10:34:31 11:20:10");         }     };     private EmployeeCounter counter = new EmployeeCounter();     @Test     public void compareTest() {         long count = counter.countWorkingEmployees(commutingTime.stream(), "11:05:20");         assertEquals(3, count);     } }

출근 시간 기준으로 정렬이 되어 있다는 가정을 하였으나, 만약 정렬이 되어 있지 않다면 1번 작업 전에 로그파일을 정렬하는 작업이 필요합니다.

다른 방법은 없을까요?

만약 출근 시간과 퇴근 시간 정보를 나눠서 정렬할 수 있다면… 즉, 출근시간으로 정렬하고, 퇴근시간으로도 정렬한다면 아래와 같이 체크할 수 도 있을 것 같습니다.

현재 사무실에서 일하고 있는 사원수 = 특정 시간 이전에 출근한 사람 - 특정 시간 이전에 퇴근한 사람

이 경우 모든 정보를 읽지 않아도 되어 경우에 따라 처음 구현한 케이스보다 좀 더 적은 양의 로그 정보를 읽고도 확인할 수 있다는 장점이 있을 것 같습니다.

다만 퇴근 시간으로 정렬하는 작업의 소요시간이 성능에 문제가 될 수 있을 것 같습니다.

github: https://github.com/tomining/AlgorithmStudy/blob/master/src/main/java/com/algorithm/coding/dojang/EmployeeCounter.java

TC: https://github.com/tomining/AlgorithmStudy/blob/master/src/test/java/com/algorithm/coding/dojang/EmployeeCounterTest.java