[HackerRank] New Year Chaos

두 가지 방법을 생각했다.

1. array를 보고 뇌물 먹인 횟수 계산하기

2. 직접 elements 위치를 바꿔가며 몇 번 뇌물을 먹였는지 세기

 

첫번째 방법을 하다가 포기했다. 고려할 상황이 너무 많았음

1. index 와 index에 현재 위치한 값을 비교한다.

2. index == 현재값 은 넘어간다

3. index < 현재값 : 뇌물을 준 사람이다.

  3.1. 현재값 - index 가 2보다 크면 : Too chaotic

4. index > 현재값 : 뇌물을 받은 사람이다.

  4.1.  4. 인 사람 중에서도 뇌물을 준 사람이 있다. q[i] > q[i+1] 인 경우 

 

 

두번째 방법은 직접 원소를 옮겨가며 횟수를 카운트했다. 인터넷의 도움을 받았다.

1. index 와 메모 dic 을 준비한다.

2. index(i) 가 len(q) -2 보다 작을 때까지 반복한다 .

  2.1. index == 현재값 은 넘어간다

  2.2. q[i] > q[i+1] 일 경우 뇌물을 준 상황이므로 q[i]가 몇 번 이동했는지 메모해둔다.

    2.2.1. 메모 횟수가 2번임에도 여전히 순서가 뒤바뀌어있다면 Too chaotic

    2.2.2.  메모 테이블에 +1 하고 순서를 바꾼 뒤 index 를 2 앞으로 이동한다.

             (이유: 바뀐 값과 바로 앞 값도 비교해야함)

3. 메모에 적은 값을 모두 더해서 반환한다.

 

직접 옮길 생각을 하다니.... 대단하다.

코드 링크 (link )