글 읽기 - 큐없이 단순 브루트 포스로 구현해봤습니다.

tjehdgns0925 4년 전 1

물론 큐로해야 시간복잡도나 이것저것 편하겟지만

혹시 저와같이 큐없이 구현하는사람들에게 참고용으로 올려봅니다.

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int t;
int n, m;
int docu[101];

int howtimes(int before,int numbering) { //before = before idx , numbering=출력된 수
	int max = 0; //docu[i]의값이 항상 1보다크니 가장작은수도 찾을수있는 0으로 설정
	int nowprint;
	int cnt = 0;
	
	for (int i = 0; i < n; i++) {
		if (max < docu[i]) {  //우선순위 가장 큰것을 찾음
			max = docu[i];
			nowprint = i;
			
		}
	}

	for (int i = 0; i < n; i++) {
		if (max ==docu[i]) {  //중복된 수를 찾음
			cnt = cnt + 1;

		}
	}
	if (cnt > 1) {
	//	printf("cnt=%d가 1보다 크면 같은 크기의 우선순위가 존재함\n", cnt);
		int is_exists = 0; //선출기준우측방향이 존재하면
		for (int i = before ; i < n; i++) {
			if (max == docu[i]) {
				nowprint = i;  //선출한것의 우측방향 먼저 출력
				is_exists = 1;
				break;
			}
		}
		if (is_exists == 1) {
			docu[nowprint] = -1; //출력된것은 -1로 제외시켜줌

			if (nowprint == m) {
				return numbering; //m번째니 출력
			}
			
			return	howtimes(nowprint, numbering + 1);
												     //이번거 미리 프린트하고 다음확인
		}
		else {
	
			for (int i = 0; i < before; i++) {
				if (max == docu[i]) {
					nowprint = i;
	
					break;
				}

			}	
			docu[nowprint] = -1;

			if (nowprint == m) {
				return numbering;
			}
	
			return	howtimes(nowprint, numbering + 1);
			


		}
	}
	
	else {  //현재프린트는 출력햇으므로 제외시킴
		docu[nowprint] = -1;

		if (nowprint==m) {
			return numbering;
		}
		else { 
			
			return	howtimes(nowprint, numbering + 1);
		}
	}


}
int main(void) {

	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n >> m; // n개의 문서중 m번째는 몇번째로 인쇄되느냐
		for (int j = 0; j < n; j++) {
			int a;
			cin >> a;
			docu[j] = a;
		}
		
		cout<<howtimes(0,1)<<endl;
		memset(docu, -1, sizeof(docu));

	}
}

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

문제

문제

출처

ICPC

큐없이 단순 브루트 포스로 구현해봤습니다.

tjehdgns0925 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말