트리 성공

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 중 하나를 제거할 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 제거한다고 하면, 다음과 같이 된다.

이제 리프 노드의 개수는 1개이다.

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

예제 입력

5

-1 0 0 1 1

2

예제 출력

2

코드

#include 
#include 
#include 

int numberof_leaf = 0;

struct Node
{
	int numberof_child = 0;
	std::vector parent_list;
	std::vector child_list;
};

void Search(Node* node)
{
	if (node->numberof_child == 0)
		numberof_leaf++;

	for (int ii = 0; ii < node->child_list.size(); ii++)
	{
		if(node->child_list[ii] != nullptr)
			Search(node->child_list[ii]);	
	}
}


int main()
{
	Node* arr[50];

	int N = 0;
	int parent = 0;
	
	std::cin >> N;

	for (int ii = 0; ii < N; ii++)
		arr[ii] = new Node();

	Node** root_node = nullptr;

	for (int ii = 0; ii < N; ii++)
	{
		std::cin >> parent;

		if (parent != -1)
		{
			arr[parent]->child_list.push_back(arr[ii]);
			arr[parent]->numberof_child++;
			arr[ii]->parent_list.push_back(arr[parent]);
		}
		else
			root_node = &arr[ii];
	}
	
	int delete_node;
	std::cin >> delete_node;

	for (int ii = 0; ii < arr[delete_node]->parent_list.size(); ii++)
	{
		if (arr[delete_node]->parent_list[ii] != nullptr)
		{
			for (int jj = 0; jj < arr[delete_node]->parent_list[ii]->child_list.size(); jj++)
			{
				if (arr[delete_node]->parent_list[ii]->child_list[jj] == arr[delete_node])
				{
					arr[delete_node]->parent_list[ii]->numberof_child--;
					arr[delete_node]->parent_list[ii]->child_list[jj] = nullptr;
				}
			}
		}
	}

	delete arr[delete_node];
	arr[delete_node] = nullptr;

	if(*root_node != nullptr)
		Search(*root_node);

	std::cout << numberof_leaf;
}

문자 그대로의 풀이였다.

대신 부모 노드가 지워질 때, 자식 노드가 부모랑 연결되어있는지를 체크하는게 좀 번거로웠다.

그래서 그냥 자식노드도 부모노드가 누군지 알 수 있게 부모 리스트를 만드는 것으로 해결.

짧은 사람들의 코드를 봤더니, parent_list를 쓴다던가 해서 트리 대신 배열로만 구현하는 방법도 있더라.

나같이 동적할당이 필수로 들어가는것보단 훨씬 세련된 방법인것 같지만, 트리스럽지는 않더라.

간과했던점은, 루트가 항상 처음에 들어오진 않는다는 것(ex. 0 0 1 2 -1)

또한, 자식이 부모보다 먼저 들어올 수 있다는 점(미리 전부 할당을 해 놓아야 한다)

그리고 child_list노드를 지우지 않고 nullptr로 만들기 때문에 .size()로는 개수를 정확히 알 수 없어서 따로 카운트를 했어야 한다는 점

토마토 성공

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력 

6 4

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 1

예제 출력

8

코드

#include 
#include 
#include 

int map[1001][1001];
int col = 0, row = 0;
std::queue<std::pair<int, int>> que;
int time = 0;
int ripen_tomato = 0;
int empty_tomato = 0;
int numberof_tomatoes = 0;

void BFS()
{
	while (que.size() > 0)
	{
		int size = que.size();
		bool is_connected = false;
		for (int ii = 0; ii < size; ii++)
		{
			std::pair<int, int> pos = que.front(); // first: row, second : col
			que.pop();

			if (pos.second - 1 != 0)
			{
				if (map[pos.first][pos.second - 1] == 0)
				{
					ripen_tomato++;
					map[pos.first][pos.second - 1] = 1;
					que.push(std::pair<int, int>(pos.first, pos.second - 1));
					is_connected = true;
				}
			}
			if (pos.second + 1 <= col)
			{
				if (map[pos.first][pos.second + 1] == 0)
				{
					ripen_tomato++;
					map[pos.first][pos.second + 1] = 1;
					que.push(std::pair<int, int>(pos.first, pos.second + 1));
					is_connected = true;
				}
			}
			if (pos.first - 1 != 0)
			{
				if (map[pos.first - 1][pos.second] == 0)
				{
					ripen_tomato++;
					map[pos.first - 1][pos.second] = 1;
					que.push(std::pair<int, int>(pos.first - 1, pos.second));
					is_connected = true;
				}
			}
			if (pos.first + 1 <= row)
			{
				if (map[pos.first + 1][pos.second] == 0)
				{
					ripen_tomato++;
					map[pos.first + 1][pos.second] = 1;
					que.push(std::pair<int, int>(pos.first + 1, pos.second));
					is_connected = true;
				}
			}
		}

		if(is_connected) //4방향 중 하나라도 숙성 과정 진행(다 막혀있거나 하면 숙성이 진행되지 않았으므로 time 증가하면 안됨)
			time++;

		is_connected = false;

		if (ripen_tomato >= numberof_tomatoes) //토마토가 모두 숙성
		{
			std::cout << time;
			return;
		}
	}
	std::cout << -1; //진행불가 상황. 큐가 비었는데도 토마토 갯수가 모자람

}


int main()
{
	std::cin >> col >> row;

	for (int ii = 1; ii <= row; ii++)
	{
		for (int jj = 1; jj <= col; jj++)
		{
			std::cin >> map[ii][jj];

			if (map[ii][jj] == 1)
			{
				que.push(std::pair<int, int>(ii, jj));
				ripen_tomato++;
			}
			else if (map[ii][jj] == -1)
				empty_tomato++;
		}
	}

	numberof_tomatoes = row * col - empty_tomato;
	
	BFS();
}

예외사항이 너무 많아져서 좀 까다로웠던 문제. 토마토가 숙성이 불가능한 상황을 어떻게 알아낼 것인가?

처음 생각한 방법은

1. 이전의 숙성 토마수 개수를 저장해놓고,  탐색을 진행해서 숙성수치가 이전타임과 변하지 않으면 진행불가로 판정. 을 생각해보았으나

서로가 토마토를 숙성시키는 과정에서 다른 큐 멤버의 숙성때문에 자신의 숙성(1로변환)이 막히는 경우에도 숙성수치가 변하지 않으므로 진행불가가 되는 문제가 있었다.

2. 그래서 숙성비교를 두 턴으로 늘릴까? --> 너무 예외가 생길 가능성이 높은 방법이며 부정확

3. 시작할 때 모든 노드의 전후좌우(자식들)을 비교해서 -1로 막혀있으면 진행불가? -> 정확한 방법이지만 전체를 한번 쭉 탐색해야함. 진행불가 상황이 아니라면 시간적 손해

등의 방법을 생각해보았고, 결론은 그냥 큐에 노드가 모두 비었는데도 숙성 토마토 갯수가 전체 숙성되어야하는 토마토 갯수보다 작으면 -1를 출력하는 간단한 방법이었다...

미로 탐색 성공

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력

4 6

101111

101010

101011

111011

예제 출력

15

코드

#include 
#include 
#include 

int map[101][101];
std::queue<std::pair<int,int>> que;
int n = 0, m = 0;
int dist = 0;


void BFS()
{
	que.push(std::pair<int, int>(1, 1));
	dist++;
	while (!que.empty())
	{		
		int size = que.size();

		for (int ii = 0; ii < size; ii++)
		{
			std::pair<int, int> pair = que.front();
			que.pop();
			int row = pair.first;
			int col = pair.second;
			map[row][col] = 0;

			if (row == n && col == m)
				std::cout << dist << std::endl;

			if (map[row - 1][col] == 1) //up
			{
				map[row - 1][col] = 0;
				que.emplace(std::pair<int, int>(row - 1, col));
			}
			if (map[row + 1][col] == 1) //down
			{
				map[row + 1][col] = 0;
				que.emplace(std::pair<int, int>(row + 1, col));
			}
			if (map[row][col - 1] == 1) //left
			{
				map[row][col - 1] = 0;
				que.emplace(std::pair<int, int>(row, col - 1));
			}
			if (map[row][col + 1] == 1) //right
			{
				map[row][col + 1] = 0;
				que.emplace(std::pair<int, int>(row, col + 1));
			}
		}

		dist++;
		
	}
}

int main()
{
	
	std::cin >> n >> m;

	for (int ii = 1; ii <= n; ii++)
	{
		std::string str;
		std::cin >> str;
		for (int j = 1; j <= m; j++)
		{
			map[ii][j] = str[j - 1] - '0';
		}
	}

	BFS();

}

숨바꼭질 성공 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 

5 17

예제 출력

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

코드

#include 
#include 
#include 

//int* visit;
//int* road;
int visit[100001];
std::queue que;
int sec = 0;

void BFS(int SuzinPos, int DestPos)
{
	que.push(SuzinPos);

	while (!que.empty())
	{
		int size = que.size();
		for (int ii = 0; ii < size; ii++)
		{
			int pos = que.front();
			que.pop();

			if (pos == DestPos)
			{
				std::cout << sec;
				return;
			}

			if (pos - 1 >= 0 && visit[pos - 1] == 0)
			{
				visit[pos - 1] = 1;
				que.push(pos - 1);
			}
			if (pos + 1 <= 100001 && visit[pos + 1] == 0)
			{
				visit[pos + 1] = 1;
				que.push(pos + 1);
			}
			if (pos * 2 <= 100001 && visit[pos * 2] == 0)
			{
				visit[pos * 2] = 1;
				que.push(pos * 2);
			}
		}

		sec++;
	}


}


int main()
{
	int N, K;
	std::cin >> N >> K;
	BFS(N, K);
}

간단한 DFS 두문제에 이어 간단한 BFS 두 문제

간단한 문제인데도 한달동안 까먹어서 많이 버벅였다.

DFS/BFS는 패턴이 비슷해서 자주자주 봐둬서 체화하면 잊어버리지 않을 것 같다.

단지번호붙이기

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1

7

0110100

0110101

1110101

0000111

0100000

0111110

0111000

예제 출력 1

3 7 8 9

출처

Olympiad > 한국정보올림피아드 > KOI 1996 > 초등부 1번

• 잘못된 데이터를 찾은 사람: djm03178
• 데이터를 추가한 사람: djm03178 jh05013
• 문제의 오타를 찾은 사람: metadata

풀이

#include 
#include 
#include 
#include 
#include 

int map[26][26] = { 0 };
std::vector count_list;
int count = 0;

void DFS(int ii, int jj)
{
	if (map[ii][jj] == 0)
		return;

	count++;
	map[ii][jj] = 0;

	if (map[ii][jj - 1] == 1)
		DFS(ii, jj - 1);
	if (map[ii][jj + 1] == 1)
		DFS(ii, jj + 1);
	if (map[ii + 1][jj] == 1)
		DFS(ii + 1, jj);
	if (map[ii - 1][jj] == 1)
		DFS(ii - 1, jj);
}

int main()
{

	int n = 0, k = 0;
	std::cin >> n;
	
	for (int ii = 1; ii <= n; ii++)
	{
		std::string str;
		std::cin >> str;
		for (int j = 1; j <= n; j++)
		{
			map[ii][j] = str[j - 1] - '0';
		}
	}

	for (int ii = 1; ii <= n; ii++)
	{
		for (int j = 1; j <= n; j++)
		{
			count = 0;
			DFS(ii, j);
			
			if (count > 0)
				count_list.push_back(count);
		}
	}

	std::cout << count_list.size() << std::endl;
	std::sort(count_list.begin(), count_list.end());
	for (int ii = 0; ii < count_list.size(); ii++)
		std::cout << count_list[ii] << std::endl;

	//system("pause");
}

DFS와 BFS 성공

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1 복사

4 5 1

1 2

1 3

1 4

2 4

3 4

예제 출력 1 복사

1 2 4 3

1 2 3 4

풀이

#include 
#include 
#include 

int map[1001][1001] = { 0 };
int vert_count = 0;

int count = 0;
int visit[1001] = { 0 };
int bfs_visit[1001] = { 0 };
std::queue bfs;


void DFS(int ii)
{
	visit[ii] = 1;
	std::cout << ii << " ";

	for (int j = 1; j <= vert_count; j++)
	{
		if (map[ii][j] == 1 && visit[j] == 0)
			DFS(j);
	}
}

void BFS(int ii)
{
	bfs_visit[ii] = 1;

	for (int j = 1; j <= vert_count; j++)
	{
		if (map[ii][j] == 1 && bfs_visit[j] == 0)
		{
			bfs.push(j);
			bfs_visit[j] = 1;
		}
	}
	std::cout << bfs.front() << " ";
	bfs.pop();

	if (bfs.size() == 0)
		return;


	BFS(bfs.front());
}


int main()
{
	int edge_count = 0;
	int start_vert = 0;

	std::cin >> vert_count >> edge_count >> start_vert;

	for (int ii = 1; ii <= edge_count; ii++)
	{
		int m = 0, n = 0;
		std::cin >> m >> n;
		map[m][n] = 1;
		map[n][m] = 1;
	}

	DFS(start_vert);

	std::cout << std::endl;

	bfs.push(start_vert);
	BFS(start_vert);
}

언리얼 팀프로젝트 5주 간 거의 놨던 알고리즘 공부를 다시 시작

기억이 잘 안 나서 간단한 DFS 문제를 두 개 정도 풀어보았다.

다시 하기 막막하다;

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms) - B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms) - C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms) - C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms) - B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예

입출력 예 설명

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

내 풀이

int solution(vector<vector> jobs) {
    int answer = 0;

    int cur_time = 0;
    int sum_time = 0;

    //pair의 경우 first비교, 같으면 second 비교
    //first : 걸리는 시간     second : 들어오는 시점
    std::queue<pair<int, int>> wating_queue;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> time_q;

    for (int ii = 0; ii < jobs.size(); ii++)
    {
        pair<int, int> p = make_pair(jobs[ii][1], jobs[ii][0]);
        time_q.push(p);
    }

    while (time_q.empty() == false)
    {
        while (time_q.empty() == false)
        {
            pair<int, int> p = time_q.top();
            if (p.second > cur_time)
            {
                wating_queue.push(p);
                time_q.pop();
            }
            else
            {
                sum_time += (cur_time - p.second) + p.first;
                cur_time += p.first;
                time_q.pop();

                int prev_size = wating_queue.size();
               
                //하나 들어갔으므로 관계 재생성
                for (int ii = 0; ii < prev_size; ii++)
                {
                    time_q.push(wating_queue.front());
                    wating_queue.pop();
                }
            }

        }
        if (time_q.empty() == true && wating_queue.size() > 0) //유휴 상태
        {
            int min = 501;
            pair<int, int> minnode = make_pair(-999, -999);

            int prev_size = wating_queue.size();

            for (int ii = 0; ii < prev_size; ii++)
            {
                if (wating_queue.front().second < min)
                {
                    min = wating_queue.front().second;
                    if(minnode.first != -999)
                        wating_queue.push(minnode);
                    
                    minnode = make_pair(wating_queue.front().first, wating_queue.front().second);
                    wating_queue.pop();
                }
                else
                {
                    //최소가 아닐경우 큐의 맨 뒤로 이동
                    wating_queue.push(wating_queue.front());
                    wating_queue.pop();
                }
            }

            time_q.push(minnode);
            cur_time = minnode.second;

            pair<int, int> p = time_q.top();
            //MIN NOde 작업(유휴상태일때)
            sum_time += (cur_time - p.second) + p.first;
            cur_time += p.first;
            time_q.pop();
        }

        while (wating_queue.empty() == false)
        {
            time_q.push(wating_queue.front());
            wating_queue.pop();
        }

    }

    answer = sum_time / jobs.size();
    answer = std::floor(answer);
    return answer;
}

내 코드의 기본적 원리는 우선순위 큐와 대기 큐를 사용하는 것이다. 먼저 모든 잡을 우선순위 큐에 삽입한다. 그리고 p.second(요청 시간, InputTime)를 current_time과 비교한다. 만약 현재 시간보다 나중에 요청되는 노드라면 이를 대기 큐에 집어넣고, 다음 요청을 검증한다. 현재 시간보다 작거나 같은 노드를 사용하여(즉 요청이 수행 될 노드) cur_time을 업데이트한다(요청이 수행되고 난 뒤의 시간으로)

이후에, time_q(우선 순위 큐)가 비고 대기 큐만 남았다면, 디스크가 유휴 상태에 들어간 것으로 간주하여 wating_queue에 있는 잡들 중 가장 요청 시간이 작은 잡을 가져와서 적용하고, 나머지 잡을 다시 time_q에 집어 넣는다.

이 작업에서 주의할 점은, 한 번 잡이 수행되고 나면 남은 작업들을 모두 time_q에 집어넣어서, 다시 우선순위 관계를 재정립해야 한다는 것이다. 

만약 0,5 :: 1,2 :: 5,5의 잡이 있을 때, 0,5가 수행되고 나면 1,2와 5,5는 모두 수행될 자격을 갖춘다(요청 시간을 볼 때)

문제에서 요구하는 바를 따르면 다음 잡은 1,2가 들어가는게 맞으나, 이미 잡들이 PriorityQueue에 들어갔었기 때문에, ProcessTime이 제일 짧은 1,2잡은 이미 wating_queue에 들어가 있다. 그렇게 되면 세 번째 5,5 잡이 수행되어, 0.5 ->5,5 -> 1,2순서대로 잡이 수행되게 되므로 문제가 생긴다.

다른 사람의 풀이

int solution(vector<vector > jobs) {
    int answer = 0;

    std::priority_queue<vector, vector<vector >, CompareProcessTime> PQ;

    std::sort(jobs.begin(), jobs.end(), CompareInputTime());
    int time = jobs[0][0];
    auto iter = jobs.begin();
    while (iter != jobs.end() || !PQ.empty()) {
        while (iter != jobs.end() && (*iter)[0] <= time) {//작업이 이미 도착해있다면
            PQ.push(*iter++); //도착해 있는 작업들을 모두 Priority Queue에 넣음
        }

        if (!PQ.empty()) {
            time += PQ.top()[1]; //작업을 수행한다.
            answer += (time - PQ.top()[0]); //처음 들어온 시간부터 수행 된 시간 까지의 차이를 뺀다.
            PQ.pop();
        }
        else {
            time = (*iter)[0];
        }
    }

    answer /= jobs.size();
    return answer;
}

아래 코드의 기본적 원리는, 일단 InputTime(요청시간) 순으로 job들을 정렬한 뒤, time(현재 시간)을 기준으로 그보다 작은 요청시간을 가진(큐에 들어올 수 있는) 노드들을 모두 Priority Queue에 넣는 것이다. 그렇게 되면 현재 시간에서 그보다 작거나 같은 시간대의 요청들은 모두 PQ에 순서대로 들어가기 때문에, 프로세스 타임 순서대로(즉, SJF에 맞는 순서대로) 정렬이 가능하게 된다.

또한 iter++는 무조건 PQ의 push작업 이후 진행되게 만들어서 만약 PQ에 아무것도 없다면 time(현재시간) = iterator가 가리키는 시간   으로 만들어 준다.  즉 유휴가 발생했을 때 inputtime이 가장 빠른 노드들을 기준으로 다시 PQ에 넣는 작업을 진행하는 것이다.

한 가지 구현으로 여러 기능을 할 수 있고, 쓸데없는 예외등을 만들 필요가 없으며 간결한 코드이다.

죽었다 깨도 이런 생각은 못 할것 같아서 회의감이 든다.