백준 - 2529번 부등호

문제

부등호가 주어질 때 그 부등호 관계를 만족하는 최대, 최소 정수를 구하세요

생각

맨 왼쪽부터 보면서 최대값은 가능한 큰 수를,
최소값은 가능한 작은 수를 넣어주면 될거라고 생각함

가능한 큰 수?

근데 가능한 큰 수? 중복 안 되게 가장 큰 수..를 찾아야하는데
내가 어느 수를 썼었는지 어떻게 알지?

사용 가능한 수들을 배열에 저장하고, 돌면서 최대 값 정하고, 사용하면 표시하고?

근데 그냥 수 정할때마다 배열 돌면서 뭐가 좋을까 정하는 것 보단,
바로 전에 정한 수 즉 앞 수만 보고, 부등호를 만족하는 값을 넣어주는 게
좋을 것 같다는 생각을 했다
이게 좀 더 그리디 같다 라는 마음

최대값 구하는 거 기준으로 구현 방법 및 예시

앞에서 부터 가능한 제일 큰 수를 넣으면서
부등호 상관없이 최대값(9876543210)을 만들려고 해보자!

만들다가, 모순이 생기면
현재 보고 있는 자리에는 바로 앞 값을 넣어주고,
(바로 앞의 값 - 원래 넣으려는 값) 만큼 앞 수들을 -1 해주면 된다

ex)
부등호가 > > < < 로 주어질 때

9>><<
맨 처음에 넣을 수 있는 가능한 제일 큰 수는 9!
9>8><<
'>'이므로 그 다음 큰 수 8 넣구
9>8>7<<
그 다음 큰 수 7 넣구
9>8>7<6< (x)
원래 그 다음 큰 수인 6이 올 차례인데, '<'이므로 6를 넣어주면 모순이 생기니까
9>8>6<7< (o)
현재 보고 있는 자리에는 7을 넣어주고, 앞의 7은 -1 해서 6으로 바꿔준다!
9>8>6<7<5 (x)
5가 올 차례인데 바로 앞 7보다 크기 위해선
9>8>5<6<7 (o)
현재 자리엔 7을 넣어주고, 7을 -1 하고, 6도 -1 해준다!

왼쪽 값이 클 수록 좋으니까 최소한 적은 개수의 앞 수에만 -1을 하는 느낌~~

++ 구현은 아래에 코드에서 확인해주세요!

++ 다른 사람들이 푼거도 확인해봤는데
만들 수 있는 모든 순열 만들어보면서 모순이 있는지 없는지 확인하고 최대 최소를 구하는 방법,
부등호가 몇 개 나오는 지 보면서 가능한 가장 큰 수로 값 넣기 등의 방법을 사용하더라

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
	int k;
	char temp;
	int maxResult[15];
	int minResult[15];

	cin >> k;

	maxResult[0] = 9;
	minResult[0] = 0;
	//맨 처음에 가능한 제일 큰 수, 제일 작은 수를 넣어줌

	//for문 돌면서 앞에서 부터 값을 넣어간다
	for (int i = 1; i <= k; i++) {
		cin >> temp;
		if (temp == '<') {
			//최대값 구하는 도중에 모순생김
			int beforeResult = maxResult[i - 1];
			maxResult[i] = beforeResult; //현재 보는 자리에 바로 앞 수 넣어				 
			//바로 앞의 값 - 원래 넣으려는 값 (beforeResult - (9 - i)) 만큼 앞 수들을 보면서
			for (int j = 1; j <= beforeResult - (9 - i); j++) {
				maxResult[i - j]--; //-1 씩 해줘
			}

			//모순 없이 가능한 제일 작은 수 넣어줌
			minResult[i] = i;
		}
		else { //'>'일 때
			//모순 없이 가능한 제일 큰 수 넣어줌
			maxResult[i] = 9 - i;

			//최소값 구하는 도중에 모순생김
			int beforeResult = minResult[i - 1];
			minResult[i] = beforeResult;
			//바로 원래 넣으려는 값 - 앞의 값 (i - beforeResult) 만큼 앞 수들을 보면서
			for (int j = 1; j <= i - beforeResult; j++) {
				minResult[i - j]++; //+1 씩 해줘
			}
		}
	}

	for (int i = 0; i < k + 1; i++) {
		cout << maxResult[i];
	}

	printf("\n");

	for (int i = 0; i < k + 1; i++) {
		cout << minResult[i];
	}

	return 0;
}