들어가며
요즘 1차 면접을 보게 되면, 기술면접인데 기술면접에서 많은 알고리즘문제를 요구하기도 합니다. 이 문제는 MS에서 면접으로 냈던 문제라고 하는 도화선으로 시간을 맞추는 방법 입니다. 제목만 보고 어떤 문제일까? 라는 생각이 쉽게 와닿지 않는데요. 일단 문제 확인을 하고 해결 방법에 대해서 설명하겠습니다.
1분동안 타들어가는 도화선이 있습니다. 이때 도화선의 두께는 고르지 않기때문에 일정한 속도로 타지 않습니다. 즉, 늦게타는 부분과 빨리타는 부분이 있습니다. 절반이 탔다고 해서, 30초가 되는 것은 아닙니다. 예를 들어서 도화선에 불을 붙인 이후에 1/4가 불에타 없어진다고 해도, 60초에 1/4인 15초가 아닙니다.
문제를 풀기 앞서 간단한 예제를 통해서 이해를 하면 더 쉽게 해결이 가능합니다. 위와 같은 도화선이 있다고 가정을 했을때 30초를 측정하는 방법은 어떻게 하면 될까요? 양쪽에 불을 동시에 붙이게 되면, 중간에서 불이 붙은 지점이 만나게 되고, 그럼 30초를 측정 할 수 있습니다.
문제
위와 같은 도화선이 2개 있다고 가정을 했을때 45초를 측정하는 방법은 어떻게 될가요?
해결방법
45초 듣자마자 생각이 드는 점이, 30초와 15초를 세면 되겠구나! 라는 생각이 들면 이미 끝난 문제입니다. 두개의 도화선에 불을 붙이는데 한개의 도화선에는 양쪽에 다른 한 도화선에는 한쪽에 불을 붙이게 됩니다. 그럼 양쪽에 붙인 도화선이 다 타는 시간은 30초입니다. (위에서 30초를 세는 방법을 알았으니...) 그렇다면 다른 한개의 도화선에서는 양쪽에 붙인 도화선이 다 타 들어갔을때 불을 끄면 30초의 시간이 흘렀고, 나머지 한 도화선에는 30초를 측정 가능한 도화선이 남게 됩니다. 그럼 마지막으로 30초를 측정 가능한 도화선의 양쪽에 불을 붙이고 다 타게 되면 15초의 시간을 계산할 수 있습니다. 이렇게 30초와 15초를 각각 계산하면 45초를 계산할 수 있습니다.