[C++] 백준(BOJ) - 2529 : 부등호

01 Nov 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 2529 : 부등호(링크)

알고리즘

1. 완전탐색
2. DFS

풀이

1. 최대범위를 기반으로 대략적인 시간복잡도 계산
   • 10자리 정하기 => 10! = 3628800 // 완탐 가능
2. 문자열 대소 비교
   • 자리 수 먼저 체크 (중요!)
   • 문자와 숫자를 비교할 때는 형변환 후 비교하기
3. 연산자 idx와 숫자 idx를 앞에서부터 차례차례 비교해 나가는 로직
4. 숫자 재사용 하지 않기 => 방문처리 배열
5. 최대 최소 값 구하기

코드

// BOJ-2529 : 부등호
#include<bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
int n, max_n = -INF, min_n = INF, visited[10];
char op[10];
vector<string> v;

bool isGood(char x, char y, char oper)
{
	if (x < y && oper == '<') return true;
	else if (x > y && oper == '>') return true;
	else return false;
}

void dfs(int idx, string num)
{
	if (idx == n + 1)
	{
		v.push_back(num);
		return;
	}

	for (int i = 0; i < 10; i++)
	{
		if (visited[i]) continue; // 숫자 재사용 불가
		if (idx == 0 || isGood(num[idx - 1], i + '0', op[idx - 1]))
		{
			visited[i] = 1;
			dfs(idx + 1, num + to_string(i));
			visited[i] = 0;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> op[i];
	}

	dfs(0, "");

	sort(v.begin(), v.end());
	cout << v[v.size() - 1] << '\n' << v[0] << '\n';

	return 0;
}

평가

• 연산자 idx와 숫자 idx를 순차적으로 진행해가며 값 만들어 가기는 자주 등장하는 패턴이므로 연습이 많이 필요
• 문자열 끼리 비교할 때 사이즈 체크 먼저하기
• 완전탐색 시 string, int 다양한 매개변수 활용해서 함수 구현하기