매일 아침 모닝 루틴처럼 어떤 문제를 풀지 정하고 푸는 연습을 하는중이다. 매일 그래도 두 문제 씩은 풀려고 하는중이지만 아직은 어려운게 더 많은거같다. 오늘의 문제는 Sorting 문제이고 꽤 많은 투표를 받은 좋은 문제인가 싶어서 풀어보았다.
xStart 와 xEnd 로 이루어진 points 벡터에서 가장 최소한의 화살로 모든 풍선을 터트려야하는 문제이다. 풍선은 xStart와 xEnd에 있다는 가정하에 어떤 포인트에서 화살을 쏘면은 여러개의 points 안에있는 벡터도 함께 터질수 있기때문에 어떤 x 지점에서 쏘냐가 가장 중요하다.
이 문제는 Greedy 에 더 속하는거 같고 따로 특별한 알고리즘을 요구하고 있지는 않지만 좀 더 창의적인 생각이 필요한 문제인거같다. Greedy 한 문제일경우 그 시나리오를 생각하면서 푸는게 중요한데 난 이렇게 생각했다.
일단 points 벡터를 xEnd가 증가하는 순서로 정렬을 해주었다. 그 이유중 하나는 xEnd 포인트와 xStart 포인트와의 겹치는 구간을 구해야 했기 때문이다.
만약에 xStart 부분이 내가 초기에 설정한 xEnd 구간보다 크다면은 그 사이는 화살을 쏠수없는 구간이기 떄문에 화살 숫자를 증가시켜줬고 track 변수를 그 구간에 xEnd로 다시 설정해주었다.
for 룹이 끝나느 시점에서는 화살 하나가 안쏘아진 상태여서 하나를 증가시킴으로서 답이 완성됐다. 사실 분명 뭔가가 틀린 테스트케이스가 있지 않을까 했는데 한번에 통과해서 좋았다.
계속 생각하는게 Greedy 문제에서는 중요한 부분인거같다.
배운점:
1. Greedy 문제 생각하는 과정
2. Sorting 함수에 활용 방법
