[CodeKata] 프로그래머스 : 4.28(수), 추석 트래픽

🥋 Oooth More!! (Level 3)

* 해설 보러가기 링크 : tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

 

레벨3 첫 문제부터 카카오라서 적잖이 당황했다.. ㅎㅎ

배열의 각 값은 종료시점과 트래픽 시간을 묶은 string 이다. 이를 먼저 시작, 종료시간으로 변환해서 트래픽 구간을 알수 있게끔 해야겠다.

그리하여, 이 트래픽 구간들이 가장 많이 포함되는 1000ms의 구간을 찾아 해당 갯수를 반환하면 된다.

 

 

 🧮 풀이

function solution(lines) {
  lines = lines.map((line) => {
    const [, time, gap] = line.split(" ")
    const [h, m, s] = time.split(":");
    const end = (h*3600 + m*60 + s*1)*1000;
    const gapTime = 1000 * Number(gap.slice(0,-1));
    return [end-gapTime+1, end]
  })
  
  let count = 1;
  
  for (let idx in lines) {
    const standard = lines[idx][1]
    const traffic = lines.filter(line => line[1] >= standard && line[0] <= standard+999).length;
    count = Math.max(count, traffic);
  }
  
  return count;
}

- lines 배열을 트래픽 [시작, 종료] 시간 변환

1. 우선, ["입력 문자열"] 을 [시작시간(ms), 종료시간(ms)] 로 map() 맵핑하려고 한다.
2. 각 요소(line)을 공백(" ")으로 split한다. 날짜가 모두 같기 때문에, 구조분해 할당에서 제외하고 time, gap만 가져와준다.
3. time은 다시 ":"로 split 해준다. 각각의 값이 시, 분, 초가 되며 이를 ms 기준으로 계산해주면 end(종료시간) 값을 구할 수 있다.
4. gap 역시 초(s) 단위와 문자열로 되있으므로 ms 변환해준다. slice(0,-1)을 하면 끝값("s")만 자를 수 있다.
5. 이렇게 구해진 gapTime을 end에서 빼주고 1을 더하면 시작시간이 된다. 이를, 1번에서 언급한 튜플 형태로 반환시키면 된다.

- 최대 트래픽 구하기

1. 내가 고안한 방법은, lines의 모든 종료시간부터 1000ms의 구간을 잡아 트래픽 수를 구하는 것이다.
2. 그러면 해당 트래픽은 무조건 포함되기에 count(최대값 누적)는 1로 시작한다. 이는, 1개 이상을 포함하는 가장 효율적인 구간이다.
3. lines를 순회하며, 각 종료시간을 1000ms 구간을 잡는 기준점(standard) 로 활용한다.
4. traffic은 lines 요소들 중, standard ~ (standard+999) 내 포함되는 트래픽 수이다. 이를 filter() 와 length() 길이값으로 구한다.
5. 이를, count 와 traffic 수 중 최대값으로 최신화해준다. 마지막으로, 이 count를 최종적으로 반환하면 된다.

처음에는 lines에서 시작시간의 최소값, 종료시간의 최대값(-999ms) 사이의 시간을 1ms 씩 순회하며 최대값을 찾았다.

당연히 이것이 정확한 방법이지만, 당연히 시간복잡도가 급증하고 불필요한 비교가 ms마다 반복되므로 위 방법을 고안한 것이다. 

 

🖇 리뷰

많은 방법들이 있었다. 우선, 각 요소를 ms 단위로 변환하는 것은 대동소이했다. 날짜가 같기 때문에 다들 시간만 고려했다.

 

또한, 1000ms 구간을 잡아야 하는데, 마찬가지로 모든 ms을 탐색할 순 없기 때문에 시작점을 바꾸는 기준이 다달랐다.

위 방법은 각 요소의 시작, 종료시간마다 구간을 바꿔주고, 이외에도 다양한 방법이 있었다. (나는 사실 이해를 거의 하지 못함...)

 

내 생각엔 시작시간보단 종료시간만 비교하는게 더 유의미하기 때문에, 내 풀이가 상대적으로 장점이 있을 수 있다고 생각된다.

---

🤯 Level 3에 입성한 기분이요?

확실히 첫 문제부터, 더욱이 카카오 코딩테스트인 만큼 쉽지가 않았다. 그나마, 날짜가 같아 new Date() 를 적용하지 않음에 감사했다.

 

매 ms를 탐색하지 않아도 되는 적절한 구간선정에 대한 방법을 많은 사람들이 정말 다양하게 고민했었다.

나 역시도 어제까지 방법만 구현해놓고, 오늘 효율성 고민을 하다 떠오른 방법으로 수정해보니 통과를 할 수 있었다.

 

이러한, 발상의 전환이 즉각적으로 이루어질 수 있어야 실제 코딩테스트에서 당황하지 않고 각 문제를 해결해나갈 수 있겠다는 생각이 들었다. (그만큼, 현재 코드에 대한 집착을 버리려고 해야겠다)