2529.부등호

(*)이번에 풀어볼 문제는 백준의 2529번 부등호이다. 꽤 오랜시간이 걸린 문제이다..ㅠㅠ

역시나 풀이 전 침착하게 분석으로 규칙을 찾아야한다..

분석을 조지거나 안하고 구현을 시작하면 예외처리를 빼먹을 시, 다시 구현해도 시작이 부족할 것이다..

-> 조짐의 지름길..

2529번: 부등호

문제의 내용은 간단하다. k개의 부등호를 입력받아 부등호에 맞게

 0~9까지의 숫자로 만들 수 있는 최소값과 최대값을 구하는 것이다.

생각보다문제가 어려웠다.. 규칙을 발견했는데 조금 침착하게 구현할 필요가 있을 것 같다.

 

* 문제를 푸는 포인트는 다음과 같다.

최대값이나 최소값이 가장크고 가장작은 것을 이용한 비교, 그리디를 사용하자

최대값일 경우에는 시작값은 9일 것이고  '>'를 만나기 전까지는 값이 순차적으로 커진다. 

예를 들어 부등호가 < < > < 이면 '>'를 만나기전까지는 수는 그대로 증가하며 '<' 의 수만큼의 시작값에서 뺀 숫자부터 증가한다.

즉, 9 - 2 ( '<'의 갯수 ) = 7부터 증가한다. 그러므로 7 < 8 < 9 > 가 된다.

그 다음부터는 최대 시작값이 9가 아닌 9 - 2 ( '<'의 갯수 ) - 1 ( 7은 사용함 ) = 6으로 다시 위의 과정을 진행하면 된다.

그리고 위의 과정 이후에 '>' 가 더 이상 나오지 않아 숫자는 남았는데 출력을 못하는 경우가 있기 때문에 한 번 더 진행한다.

 

< Code 설명 >

#include <iostream>

using namespace std;

char bu[10];

int main() {
	int k;
	cin >> k;
	for (int i = 0; i < k; i++)
		cin >> bu[i];

	int n = 0;
	int ans = 9;  // 시작 최대값
	for (int i = 0; i < k; i++){
		if (bu[i] == '>'){ // '>'전까지 else에서 n을 증감
       		//n을 뺀곳부터 시작값까지 출력
			for (int j = ans - n; j <= ans; j++) 
				cout << j;  
			ans = ans - n - 1; // 출력 후 최대 시작값 조정
			n = 0;             // 카운트할 값 초기화
		}
		else
			n++;  // '>'가 아닐 경우 증감
	}
    
// 숫자는 남았는데 '>' 부등호가 없어서 출력 과정이 진행이 안되므로 아래와 같이 진행하여 나머지 출력 
	for (int j = ans - n; j <= ans; j++) 
		cout << j;
	cout << "\n";


	ans = 0; 	// 최소값을 위한 초기화
	n = 0;      // 최소값을 위한 초기화
    
	for (int i = 0; i < k; i++){
		if (bu[i] == '<'){ // 위와 같지만 최소이므로 부등호를 반대로 한다.
			for (int j = ans - n; j <= ans; j++)
				cout << -1*j; 
                // 출력 값이 -1을 곱해주면 최소값 그대로 유지가능하다.
                
			ans = ans - n - 1;
			n = 0;
		}
		else
			n++;
	}
    
// 숫자는 남았는데 '>' 부등호가 없어서 출력 과정이 진행이 안되므로 아래와 같이 진행하여 나머지 출력 
	for (int j = ans - n; j <= ans; j++)
		cout << -1*j;
	cout << "\n";
	return 0;
}

 

 

* 참고

-> 최소값의 경우 위와같이 하기 싫다면 for문을 반대로 구현하면 된다.

{
    ans = 0;
	n = 0;
	for (int i = 0; i < k; i++){
		if (bu[i] == '<'){
			for (int j = ans + n; j >= ans; j--)
				cout << j;
			ans = ans + n + 1;
			n = 0;
		}
		else
			n++;
	}
	for (int j = ans + n; j >= ans; j--)
		cout << j;
	cout << "\n";
}