문제
[1, 2, 3 .. , n] 의 원래 줄서기 배열이 있으나
뇌물을 주고 새치기를 하면서 배열이 엉망이 되었다.
1사람당 최대 2명까지 뇌물을 줘서 새치기를 할 수 있다.
(1사람이 3명 이상 새치기 한 경우는 "Too chaotic" 출력)
몇 번 새치기해서 완성된 결과인지 출력하는 문제
접근 방법
처음에 기존 인덱스와 다르면 뺄셈을 해서
3이상이면 "Too chaotic" 출력하고
아니면 result에 더하는 방식으로 했으나 아래와 같이
새치기를 했음에도 인덱스가 변하지 않은 테스트케이스는 잡지 못했다.1 2 3 4 5 6 7 1 3 5 2 7 6 4
- 원래 위치보다 세 칸 이상 앞으로 오면 "Too chaotic"을 출력한다.
- 원래 q[i]는 i+1이 있어야 한다. ex. 1 2 3 4 5
- 뇌물을 받아 뒷 번호가 앞으로 오게 되는 경우 아래와 같이 증가한다.
q[i] = i+2 (한 칸 앞으로 땡겨짐)
q[i] = i+3 (두 칸 앞으로 땡겨짐)
q[i] = i+4 (세 칸 앞으로 땡겨짐)[1, 2, 3, 4, 5] -> q : [2, 1, 5, 4, 3] 일 때
ex. i = 0
q[0] = 2 = 0+2 (한 칸 앞으로 땡겨짐)
ex. i = 2
q[2] = 5 = 2+3 (두 칸 앞으로 땡겨짐)따라서
q[i] > i+3인 경우 "Too chaotic"을 출력한다.
- q[i]에게 뇌물을 준 사람을 찾아서 다 더하기
q[i]에게 뇌물을 먹인 사람은 q[i]보다 앞 인덱스에 있으면서 q[i]보다 큰 번호를 가진 것이다.[1, 2, 3, 4, 5] -> q : [2, 1, 5, 4, 3] 일 때
1에게 뇌물을 준 사람은
q[1]보다 앞에 있고 q[1] = 1보다 큰 번호를 가진 2밖에 없다.마찬가지로 3(q[4])에게 뇌물을 준 사람은 5, 4가 있다.
이를 코드로 풀면 아래와 같다.
for(int j=0; j<i; j++) { if (q[j] > q[i]) result++; }다만 j의 범위를 줄일 수 있다.
2명까지 최대 앞설 수 있으므로, q[i]-2, 0 중 더 큰 인덱스부터 탐색하면 된다.
[1, 2, 3, 4, 5] -> q : [2, 1, 5, 4, 3] 일 때
i = 4인 경우 3(q[4])에게 뇌물을 준 사람을
0부터 탐색하는것보다는 q[4]-2 = 1부터 탐색하는 것이 효율적이다. ?
for(int j=max(q[i]-2, 0); j<i; j++)
{
if (q[j] > q[i]) result++;
}풀이
void minimumBribes(vector<int> q) {
int result = 0;
for(int i=0; i<q.size(); i++)
{
int idx = i+1;
if (q[i] > idx+2)
{
cout << "Too chaotic\n";
return;
}
for(int j=max(0, q[i]-2); j<i; j++)
{
if (q[j] > q[i]) result++;
}
}
cout << result << '\n';
return;
}
정리
도저히 모르겠어서 구글링을 했다. 풀이를 봐도 이해하는데 시간이 좀 걸렸던 문제..
