글 읽기 - 1966번 프린터 큐, 반례에 대하여..

rjf1138 3년 전 0

1966번 프린터 큐

반례)

38 29
7 1 8 4 7 1 3 4 6 5 7 8 3 2 8 5 9 4 6 8 2 1 8 7 4 8 5 3 7 6 3 4 6 1 5 2 8 5

이것에 대한 답이 15라고 나와있던데,

29번째 숫자가 6이고, 그래서 답이 16 아닌가요?

왜 15인지 모르겠습니다..

사실 제가 짠 코드로 저 케이스 말고 반례들 거의 다 통과하는 것 같은데,

왜 15인지 모르겠어서, 진도를 못나가고 있습니다ㅠㅠㅠㅠ

혹시 왜 15인지 가르쳐주실 분 있으신가요?ㅠㅜ

코드에도 틀린 부분 있거나 다른 반례가 있다면, 지적해주시면 매우 감사하겠습니다.

//큐의 개념이 응용된 문제
#include <iostream>
#include <queue>
using namespace std;

int arr[101] = { 0 };
int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T, N, M, cnt = 0, wantedPriority = 0, answer = 0;
	cin >> T;
	for (int i = 0; i < T; ++i) {
		cin >> N >> M;
		cnt = 0;
		answer = 0;
		wantedPriority = 0;
		queue<pair<int, int>> que;
		arr[101] = { 0 };
		for (int j = 0; j < N; ++j) {
			cin >> arr[j];
			que.push(make_pair(j, arr[j]));// first: index, second: priority
			if (j == M) {
				wantedPriority = arr[j]; //wantedIndex == M
			}
		}
		for (int j = 0; j < N; ++j) {
			if (arr[j] > wantedPriority)
				cnt++;
		}
		while (true) {
			if (que.front().second > wantedPriority) {
				cnt--;
				answer++;
				que.pop();
			}
			else if (que.front().second == wantedPriority) {
				if (cnt == 0 && que.front().first == M) {//index가 같은지 확인
					answer++;
					cout << answer << '\n';
					break;
				}
				else if (cnt != 0) { //wantedPriority와 크기는 같지만 뒤에 더 큰 우선순위가 있는 경우, 맨 뒤로 보낸다.
					que.push(que.front());
					que.pop();
				}
				else {
					answer++;
					que.pop();
				}
			}
			else {
				que.push(que.front());
				que.pop();
			}
		}
	}

	return 0;
}

a99azaz 3년 전 1

4 1

2 1 3 1 이면

2 (1) 3 1 -> (1) 3 1 2 -> 3 1 2 (1) 에서 3 나가고 -> 1 2 (1) -> 2 (1) 1 에서 2 나가고 -> (1) 1 에서 1 나가서 답이 3입니다.

rjf1138 3년 전 0

와... 진짜 간단한 것을 생각 못하고 있었네요ㅠㅠ 정말 감사합니다!! 덕분에 해결했습니다!!

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

문제

문제

출처

ICPC

1966번 프린터 큐, 반례에 대하여..

rjf1138 3년 전 0

a99azaz 3년 전 1

rjf1138 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말