kkb910711   4년 전

제가 구현한 방법이 '시간 초과'가 되기에 더 좋은 방법이 있나 질문드립니다.

제가 구현한 방법은 다음과 같습니다. (제가 구현한 방법이 테스트 케이스로는 정답을 출력하지만 틀릴 수도 있습니다..)

1. 입력 혹은 수정된 수열을 오름차순 정렬을 합니다.

2. 오름차순 된 수열을 arr이라고 한다면, 제일 큰 수부터 차례대로 arr[index]와 (index+1)를 숫자비교를 합니다.

3. 비교를 하는 도중 (index+1)이 arr[index]보다 더 큰 경우가 있다면, 만들 수 있는 순열이 없다고 판단합니다.


ex 1) 3 4 3 2 5 라는 배열을 오름차순하면 2 3 3 4 5가 되고, 1 2 3 4 5와 숫자비교를 합니다.

2 3 3 4 5

1 2 3 4 5

이 부분에서 (5,5) -> (4,4) -> (3,3) -> (3,2) -> (2,1) 비교를 하게됩니다.

(index+1)이 arr[index]보다 큰 경우가 없기에 만들 수 있는 순열이 있다고 판단합니다.


ex 2) 3 3 3 2 5 라는 배열을 오름차순하면 2 3 3 3 5가 되고, 1 2 3 4 5와 숫자비교를 합니다.

2 3 3 3 5

1 2 3 4 5

이 부분에서 (5,5) -> (3,4) -> (3,3) -> (3,2) -> (2,1) 비교를 하게됩니다.

두번째 부분에서 (index+1)(4)이 arr[index](3)보다 크므로 만들 수 있는 순열이 없다고 판단합니다.


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