내가 생각한 원리가 맞나 질문.
예를들어 a, b!=0이고 a..b..0이 있다면 0을 채워야 할텐데, a에서 출발해서 b를 건너뛰어서 0을 채우는 것보다 b에서 출발해서 0을 채우는게 항상 이득임. 즉, 0을 채우려고 1을 가지고 오른쪽으로 가되, 0이 아닌 숫자를 만나면 그 숫자를 넘어서 가는건 손해라는거지.
그래서 0아닌 모든 숫자들에 대해 서로 상대적인 순서는 바뀌지 않도록하면서(왼쪽 숫자는 오른쪽 숫자를 넘어가지 않도록) 0을 채워주면 될거같음.
이렇게 이해했고, 구현은 아이디어랑 별개로 골치아팠다.. 맞는 이해일까? 고수님들아
잘못됐거나 부족한 생각이면 조언좀 해주세요 ㅜㅜ. 이거 고민하는데 하루 걸림.
- dc official App
아이디어는 맞는데 구현이 문제인듯. 소들이 시계방향으로 돌다가 앞 칸에있는 소를 만나면 그 칸을 건너 뛰는 것보다 앞에 소들을 밀고 가는게 더 이득이기 때문에 적당한 칸에서 출발해서 소들을 밀고 나가면서 각 소들이 몇칸을 가게 되는지를 계산해서 답을 구하면 O(n^2)에 풀 수 있음.
대충 뒤에 있는 소가 앞에 있는 소를 밀지 않는 칸이 있음. 거기서 출발하면 됨.
내가 설명을 못해서 도움이 될진 모르겠다.
고마워요. ㅜㅜ 바로 이해됐습니다. - dc App