quddnr4096   1년 전

자기 바로 다음 번호가 자신의 뒤에 위치해있다면 카운트를 1 증가시키고 그 다음 숫자에 대해 똑같이 반복,

이 때 카운트가 최대인 경우를 구해서 N - 최대를 해주는 형식으로 답을 구하려고 하였는데 시간초과에서 자꾸 막히네요..

나름 줄인다고 앞쪽에서 사용이 되었는 값은 그냥 넘어가는 형식을 취해줘도 안되네요..

고수님들 시간 줄이는 방법좀 알려주십쇼~

methylene   1년 전

아이들의 번호 k를 하나씩 받을 때마다

받은 번호의 바로 앞번호가 아직 나오지 않았다면 arr[k] = 1을 저장(arr을 0으로 초기화 했다면 arr[k] = arr[k - 1] + 1;을 해도 무방)

이미 있다면 arr[k] = arr[k - 1] + 1;

이런식으로 하면 시간복잡도가 O(n)이 됩니다.

댓글을 작성하려면 로그인해야 합니다.