Boj 2529) 부등호

문제

백준 2529

설명

n 이 작아서 브루트포스로 풀어도 되긴하는데, 정석은 위상정렬로 푸는 것임.

9
> < < < > > > < <

위 예시는 위처럼 그림으로 나타낼 수 있다.

• 이때 부등호를 Directed Edge 로 간주하면 위 그래프는 항상 DAG 가 된다는 점이 중요하다.
• 부등호를 받아드리는 방향에 따라 두가지 버전의 DAG 가 만들진다.

가장 큰 숫자를 만들기 위해선 높은 자리에서 가장 큰 숫자부터 줘야함

• 이를 위해선 위상정렬로 큰 값을 줘야하는 Idx 부터 구하고
• 우선순위 큐를 통해서 낮은 Idx 부터 큰숫자를 부여해야함

가장 작은 숫자를 만들기 위해선 가장 작은 숫자부터 줘야함

• 이를 위해선 위상정렬로 작은 값을 줘야하는 Idx 부터 구하고
• 우선순위 큐는 똑같이 진행함.

시간 복잡도

O(\(N\log{N}\))

코드

struct TopologyData
{
	int n_targets[11]; 
	vector<int> srcs[11];
};

TopologyData min_data, max_data;
int arr[11], idx2var[11];
int n;

void Solve(TopologyData& data, int start, int offset)
{
	priority_queue<int, vector<int>, greater<int>> q;
	auto& n_targets = data.n_targets;
	auto& srcs = data.srcs;

	for (int i = 0; i <= n; i++)
		if (n_targets[i] == 0)
			q.push(i);
	
	for (int i = 0, j = start; i <= n; i++, j += offset)
	{
		int cur = q.top();
		q.pop();
	
		idx2var[cur] = j;
	
		for (int src : srcs[cur])
			if (--n_targets[src] == 0)
				q.push(src);
	}
	
	for (int i = 0; i <= n; i++)
		cout << idx2var[i];
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
    	char ch; int src, dst;
        cin >> ch;
    
    	src = ch == '<' ? i     : i + 1;
    	dst = ch == '<' ? i + 1 : i;
    
    	max_data.srcs[dst].push_back(src);
    	max_data.n_targets[src]++;
    	min_data.srcs[src].push_back(dst);
    	min_data.n_targets[dst]++;
    }
    
    Solve(max_data, 9, -1);
    cout << endl;
    Solve(min_data, 0, +1);
}