Array Manipulation

생각했던 것

문제가 생각보다 쉽게 느껴졌기 때문에 직관적으로 구현해보았다. 주어지는 각 입력에 맞춰 a부터 b까지 k만큼 더해주었고, 마지막에 정렬을 해서 가장 큰 값을 가져오면 된다. 중간중간 미스가 있었지만 답 자체가 틀리지는 않았다.

문제점

문제는 타임아웃이었다. 주어진 범위에 해당하는 모든 원소에 접근해야하기 때문에 입력값이 100000개가 넘어가면 아무래도 오래걸렸다. 자바가 아니라 C, C++이라면 통과할 수도 있겠다고 생각했지만 꼼수 부리지 말고 알고리즘을 개선해보자.

해결

결과적으로는 스스로 답을 찾아내지는 못했다. 오름차순으로 절반의 값만 계산한다던지 하는 생각이 들긴 했지만 정답은 아닌것 같았다. 좀 더 효율적인 자료구조 활용이 필요해보였다. bfs, dfs 등의 기법이 필요해보이진 않았기 때문에... 그러다 힌트를 보게 되었고 획기적이라는 생각이 들었다.

포인트는 범위를 지정해주는 것이었다. 시작지점에서 k만큼 더해주고, 끝지점+1에서 k만큼 빼주면 배열을 순차적으로 따라갈때 (시작지점, 끝지점)만큼은 k만큼 더해져있는 것이라고 생각할 수 있고, 그 구간을 벗어나면 k만큼 빠지기 때문에 더해지지 않을 것으로 간주할 수 있는 것이다. 같은 위치에 여러 값이 더하고 빠져도 상관이 없는 방법이다. 배열을 이용하는 새로운 방법을 알게 되어서 기분이 좋았다.