[HackerRank] New Year Chaos

1. Problem

• https://www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs[]=interview-preparation-kit&playlist_slugs[]=arrays

2. Feedback

• 못풀음. 힌트 보고 풀음.
• 규칙
  • bribe 는 한 사람이 최대 2번 까지 가능
  • 앞에 있는 얘는 뒤에 있는 얘한테 bribe 를 못 줌.
• Brute force 로 풀어볼려는데, Swap 해서 규칙을 찾아서 프로그래밍화 하는 방법을 못찾음.
• 입력 받은 상태를 초기 상태로 변환하는 방법으로 풀음.
• 최대 2번 바꿀 수 있으며, 초기상태는 오름차순이기에, 끝에서부터 최대 index 2 이내의 값이, 앞의 값이 뒤에 값보다 작다. 또한, 앞의 값이 뒤에 값보다 크다는 것은 swap 한다는 의미이며, ans++ 를 해준다.
• 여기서 내가 잘못 생각한 것은 최소 값을 구하라는 것에서 여러 조합이 나올 수 있다 생각한 것. 여러 조합이 나올 수 없음. 2번 이내로 변경해야하니.
• 이런 문제를 풀 때, 반드시 for 문을 통해 어떻게 규칙화할 것인지 생각해야 함.

3. Source

public static void main(String [] args)
 {
  Scanner in = new Scanner(System.in);
  int t = in.nextInt();
  
  for (int i = 0 ; i < t ; i++)
  {
   int n = in.nextInt();
   int arr[] = new int[n];
   for (int j = 0 ; j < n ; j++)
   {
    arr[j] = in.nextInt();
   }
   int ans = solve(arr);
   if (ans == 0)
    System.out.println("Too chaotic");
   else
    System.out.println(ans);
  }
 }
 
 public static int solve(int arr[])
 {
  int ans = 0;
  for (int i = arr.length - 1 ; i >= 0 ; i--)
  {
   if (arr[i] - (i + 1) > 2)
   {
    return 0;
   }
   for (int j = Math.max(0, arr[i] - 2) ; j < i ; j++)
   {
    if (arr[j] > arr[i]) ans++;
   }
  }
  return ans;
 }