알고리즘 풀이 - 자료구조

달리기 시합 알고리즘

오늘은 알고리즘을 풀면서 자료구조에 대한 여러가지 생각을 했다.
기본적으로 사용하는 List를 바탕으로 set, map을 이용하여 문제풀이를 시도하였다.

- 처음 시도

최초로 시도한 방식은 주어진 배열을 List<>를 사용하여 .remove를 통해 삭제하고 .add를 통해서 값을 추가하는 방식을 통해서 결과를 도출하려 하였다. 이를 통해 주어진 예시와 같은 결과를 얻을 수 있었다.

• 실패 이유
  하지만 결과를 해보니 케이스 9~13애서 시간초과로 오류가 발생했다. 이 근본적인 원인은 처음 순서를 알기위해서 indexOf를 사용하여 순회를 하였기 때문에 자료가 길고, 후순위에 있을 수록 오래걸리기 때문에 성공에서도 6000ms 이상의 사싱이 걸리는 케이스가 있었다. 즉, 이를 개선하여야 할 필요가 있었다.

- 이후 시도

이후에는 중복을 지워 횟수를 줄인다는 초점에서 set을 이용하여 calling의 횟수를 계산하여 하는 방식으로 구현하였다. 그러나 이런 방식으로 하면 예시중에서 못받아들이는 경우가 많아 예시에만 맞출수 있었다. 그래서 최종적으로 map자료구조를 통해 순위를 잡아놓고 하는 방법을 시도해 보았다.결국 map을 통해서 순위를 정하는 것으로 indexOf를 대체하는 방법을 통하여 문제를 해결하였다.

• 배운점
  결과만 놓고 보자면 이번 알고리즘을 통해서 사용한 것은 map 단일이다. 그러나 여러가지 시도를 통해 List의 장점과 한계를 알았으며 set을 활용하여 보려는 발상, map을 사용하는 방식 등 여러가지를 알게 되었다. 이를 통하여 문제를 해결하는 것을 자료구조를 활용하여 시도하면 어러가지 방식을 통해 이용가능한 것을 느꼈다.