백준 2529 - 부등호
Updated:
C++
2529번 - 부등호
문제
여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 문제 출처
접근 방법
0부터 9까지의 수 중에서 (k+1)개 수를 뽑는다.
즉 k가 3이어 부등호가 3개이면 수는 4개이므로, [0, 1, 2, 3] / [0, 1, 2, 4] / [0, 1, 2, 5] … 등등 10개 수 중에서 (k+1)개의 수를 뽑는다.
그 뽑은 수를 가지고 부등호를 비교하여, 만약 모든 수가 주어진 부등호의 조건에 맞으면 그 수들을 연결해 가장 큰 수를 찾는다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std;
int k, n;
int sel[10];
char sign[9];
bool visited[10];
vector<long long> result;
void DFS(int lv);
void chkSign();
void makeInt();
void print();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> k;
n = k + 1;
for (int i = 0; i < k; i++)
cin >> sign[i];
DFS(0); //k + 1개의 수를 뽑으며, 이 수를 가지고 부등호를 만족하는 모든 숫자들의 연결을 구한다.
sort(result.begin(), result.end()); //모든 연결된 숫자들을 정렬한다.
string max_num, min_num;
max_num = to_string(result.at(result.size() - 1)); // 정렬 된 수 중, 가장 뒤에 있는 값을 가져온다. 이는 가장 큰 수다.
if (result.at(0) < pow(10, k)) // 가장 작은 수를 가져오는데, 이때 이 수는 제일 앞 자리의 수가 0이므로 제일 앞자리에 0을 붙혀준다.
min_num = "0" + to_string(result.at(0));
else {
min_num = to_string(result.at(0));
}
cout << max_num << "\n";
cout << min_num;
}
void DFS(int lv) {
if (lv == n) { //k + 1개의 수를 뽑는다.
chkSign();
return;
}
for (int i = 0; i < 10; i++) {
if (!visited[i]) {
sel[lv] = i;
visited[i] = true;
DFS(lv + 1);
visited[i] = false;
}
}
}
void print() { //k + 1개의 수가 제대로 뽑혔는지 확인하기 위한 함수.
for (int i = 0; i < n; i++) {
cout << sel[i] << " ";
}
cout << "\n";
}
void chkSign() { //뽑은 수를 가지고 부등호를 비교한다.
bool success = true;
for (int i = 0; i < k; i++) { //부등호의 개수 만큼 반복한다.
char curS = sign[i];
if (curS == '<') { //조건문은 부등호를 적용하였을 때, 틀렸는 지를 확인한다. 만약 '<' 인데 6 < 5 가 되면 틀린 부등호라고 인식한다.
if (sel[i] > sel[i + 1]) {
success = false;
break;
}
}
else {
if (sel[i] < sel[i + 1]) {
success = false;
break;
}
}
}
if (success) { //위의 모든 조건이 통과 되면 올바를 수 조합이므로, 이 수들을 가지고 하나의 수로 만든다.
makeInt();
}
return;
}
void makeInt() { // 각 수들을 10의 자리수에 맞추면서 하나의 큰 수로 만들어준다.
long long num = 0;
num += sel[n-1];
for (int i = 0; i < n - 1; i++) {
num += sel[i] * pow(10 ,(n - i - 1));
}
result.push_back(num);
}
코드 - Java
2021/03/01에 한번 더 풀었다.
이전 코드와 다른 부분은 뽑은 수를 Math.min / Math.max를 통하여 바로바로 갱신해주었다.
import java.util.*;
import java.io.*;
public class Main {
static int n;
static long biggest = 0, smallest = Long.MAX_VALUE; //최대 수인 9876543210은 int로 담을 수 없다.
static char[] sign;
static int[] sel, vis;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = stoi(br.readLine());
sign = new char[n];
sel = new int[n + 1];
vis = new int[10];
StringTokenizer stk = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++)
sign[i] = stk.nextToken().charAt(0);
DFS(0);
String str;
str = String.valueOf(biggest);
System.out.println(str);
str = String.valueOf(smallest);
if(String.valueOf(smallest).length() == n) {
str = "0" + str;
}
System.out.println(str);
br.close();
return;
}
public static void DFS(int lv) {
if(lv == n + 1) {
if(!Chk())
return;
long comp = 0;
int idx = 0;
for(int i = n; i >= 0; i--) {
comp += sel[idx++] * Math.pow(10, i);
}
biggest = Math.max(comp, biggest);
smallest = Math.min(comp, smallest);
return;
}
for(int i = 0; i < 10; i++) {
if(vis[i] == 0) {
vis[i] = 1;
sel[lv] = i;
DFS(lv + 1);
vis[i] = 0;
}
}
}
public static boolean Chk() {
for(int i = 0; i < n; i++) {
if(sign[i] == '<') {
if(sel[i] > sel[i + 1])
return false;
}
else {
if(sel[i] < sel[i + 1])
return false;
}
}
return true;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
후기 및 개선할 점
아마도, 4개월 전에 풀었을 때에도 long 형 타입이 발목을 잡은 것 같다.
항상 문제를 풀때 경계 값 테스트를 해야한다는 것을 한번 더 상기시켜준 문제이다.
내가 보통 설정하는 int의 최대 값은 987654321이라는 것을 생각하자.
