문제 해결 전략

• 뒤에서부터 진행하기로 함. 타겟값이 있고, 바로 왼쪽 값보다 값이 작으면 top으로 이동하는 식으로 생각함.

• -> 그런데 이렇게 하면 예제 입력1번과 같이 2를 출력할 수 없다.

: 뒤에서부터 하면 엉망이다.

• 3 2 1
• 1 3 2
• 2 1 3
• 엉망이다.

해설

해설을 보면, 1부터 n까지의 수가 있고, 오름차순으로 정렬하는 것이므로, n부터 1까지 내림차순으로 오른쪽에서 왼쪽으로 비교하면서 카운팅하면 된다고 한다.
그런데 내 생각에는 top에다가 타겟값을 올리면 , 어쨋든 모든 원소를 모두 오른쪽으로 이동해야 하는 거 아닌가???? 생각을 했는데 , 굳이 그럴 필요는 없다고 한다.

• 생각해보기
  : 백준 사이트 해설에 감사하게도 이해 잘되게 작성하신 분이 있다.

---

생각해보기.

• 예를 들어 3 2 1과 같은 경우이다.

• 1. 뭔가를 빼서 top에다가 위치를 해야 한다.
• 2. 그런데 다른 값도 top에다가 위치해야 하는데 , top 위치했을 때 이미 top으로 위치한 친구가 다시 또 top으로 위치하지 않을 조건에 대해서 생각해보자.

//

• 일단은 자리한 순서 상관없이 생각해보자.

• 그럴려면 가장 큰값을 먼저 찾아 그 친구를 top에다가 위치하고,

• 그 다음 n-1 값을 찾아서 top에다가 위치하고,

• 그 다음 n-2값을 찾아서 top에다가 위치하게 되면,
  => 뒤로 밀려나는 형태는 알아서 n-2, n-1, n 과 같은 오름차순으로 형성이 된다!!

=> 유레카!!

라이브로 아이디어 주석으로

• 1번 : 오른쪽에서부터? 진행 ??

• 2번 : 왼쪽에서부터 진행.

• 3번 : 가장 높은것부터 꺼내기?

  // 가장 큰것과 가장 작은 거를 가지고 생각해보자. 

  // 가장 큰것부터 꺼내서 앞으로 이동하기???

  // 1 3 4 2 
      // 4 1 3 2 
      // 3 4 1 2 
      
  // 문제에서 최소 카운팅 2이므로 아니다.

• 4번 : 아이디어 없이 예제 숫자를 가지고 생각해보자.

 // 1 3 4 2 에서 생각해보면 
     // 솔직히   3 과 4는 가만히 내비두면 된다. 

 // 2를 꺼내고 1을 꺼내면 된다. 

 // n부터 1까지 감산하는 거는 확실하다.
     // 타겟값이 아닌 2를 카운팅하고
     // 타겟값이 아닌 1을 카운팅하면 
     // 될려나? 

• 테스트 1번.

// 5 1 3 4 2

// 위의 예시에서는 5뒤에 있는 4개를 적절히 꺼내면 된다.

// 4 5 1 3 2

// 3 4 5 1 2

// 2 3 4 5 1

// 1 2 3 4 5 
// => 완료 
// 이렇게 하면 굳이 오른쪽으로 시프트 하는 연산 필요 없다. 

• 테스트 2번.
  -> 굳이 오른쪽으로 시프트할 필요가 없다.

 // 2 1 3 5 4
 
 // 4개 꺼내야 하나?

 // 4 2 1 3 5

 // 3 4 2 1 5

 // 2 3 4 1 5
 // 1 2 3 4 5

결론
: 가장 높은값을 타겟으로 하고 1씩 감산하면서 앞으로 가면서 비교하면서 일치하지 않으면 카운팅 함.

코드

int cnt = 0;
int target = n;

for (int i = n - 1; i >= 0; i--)
{
    if (v[i] == target)
    {
        target--;
    }
    else
    {
        cnt++;
    }
}