알고리즘/백준
BOJ) 부등호
Zin0_0
2020. 7. 3. 16:27
반응형
부등호
2529번: 부등호
두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제��
www.acmicpc.net
풀이
답은 바로 구했지만, 메모리를 너무 많이 잡고 속도가 느려서 몇 번을 다시 풀었다.
처음에는 모든 경우의 수를 다 구해서, 부등호의 갯수 n개 +1 만큼의 숫자를 뽑은 경우를 답 리스트에 넣어주었다.
이후, 정렬을 통해 양 끝에 있는 수를 출력해주었다.
정말 별로인 코드다...
그래서 조금 고쳐보기로 했다.
String으로 다 저장해서 정렬을 하는것이 아니라, Long 타입 변수를 통해 MAX와 MIN 값을 저장해주었다.
로직 자체가 문제라서 메모리와 속도에 큰 효과를 보지 못할 것이라고 생각했지만, 더 나은 코드를 생각하는 과정이라고 생각하고 진행했다.
최대 최솟값이 앞자리가 0인 경우는 LONG 타입이기 때문에 0이 저장되지 않는다.
그래서 자릿수에 맞게 0까지 print를 해주는 메소드를 만들어서 제출했다.
속도 측면에서는 꽤나 성능이 좋아졌다.
하지만, 여전히 메모리를 많이 잡아먹고 속도도 좋지 못하다고 생각이 들었다.
그래서 list를 빼고 생각하기로 했다.
하지만, 잘 떠오르지 않아서 질문 게시판을 참고했다.
list로 숫자를 추가하는 과정을, Long타입의 숫자에 이전 숫자를 10씩 증가시키면서 해당 숫자를 더해 하나의 숫자로 그냥 구해주었다.
또한, 0~9를 다 도는 것이 아니라, 부등호에 따라서 0~n , n~9 까지만 for문을 돌게 해주었다.
Long 타입으로 최대 최소를 구해줬기 때문에, 여기서도 0을 포함하는 print를 해야했다.
C언어에서 %0nd가 생각나서 찾아봤는데, 자바에도 String.format으로 쓸 수 있었다. ( 잘 쓰지 않아서 까먹고 있었는데, 다시 생각났다. )
메모리와 속도가 현저히 좋아졌다.
답답한 마음이 확 풀리는 순간이었다.
brute-force 문제는 어떻게 가지치기를 하느냐가, 그리고 어떤 식으로 값을 도출하는가에 따라 정말 천차만별인것 같다.
물론 다른 알고리즘들도 마찬가지지만, brute-force는 완전 탐색을 전제로 하기 때문에, 더욱 조심할 필요가 있는 것 같다.
코드 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
public class Main {
final static int NUMMAX = 10;
final static String LEFT = ">";
static String[] ineqArr;
static LinkedList<String> ansList;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ineqArr = br.readLine().split(" ");
solution(n);
br.close();
}
private static void solution(int n) {
ansList = new LinkedList<>();
getAns(new boolean[NUMMAX], 0, n, new LinkedList<>());
Collections.sort(ansList, (o1, o2) -> o1.compareTo(o2) < o2.compareTo(o1) ? 1 : -1);
System.out.println(ansList.poll());
System.out.println(ansList.pollLast());
}
private static void getAns(boolean[] visit, int cnt, int n, LinkedList<Integer> list) {
if(n <cnt) {
if(list.size()>n) {
LinkedList<Integer> newList = copyList(list);
StringBuffer sb = new StringBuffer();
for (String ineq : ineqArr) {
int leftNum = newList.poll();
int rightNum = newList.peek();
if (ineq.equals(LEFT)) { // >
if (leftNum < rightNum) {
return;
}
} else { // <
if (leftNum > rightNum) {
return;
}
}
sb.append(leftNum);
}
sb.append(newList.poll());
ansList.offer(sb.toString());
}
return;
}
for(int i=0; i<NUMMAX; i++) {
if(!visit[i]) {
visit[i] = true;
list.offer(i);
getAns(visit,cnt+1,n,list);
visit[i] = false;
list.pollLast();
}
}
}
private static LinkedList<Integer> copyList(LinkedList<Integer> list) {
LinkedList<Integer> result = new LinkedList<>();
for(int num : list) {
result.offer(num);
}
return result;
}
}
코드 2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
public class Main {
final static int NUMMAX = 10;
final static String LEFT = ">";
static String[] ineqArr;
static long minAns, maxAns;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ineqArr = br.readLine().split(" ");
solution(n);
br.close();
}
private static void solution(int n) {
minAns = Long.MAX_VALUE;
maxAns = 0;
getAns(new boolean[NUMMAX], 0, n, new LinkedList<>());
printNum(maxAns,n);
printNum(minAns,n);
}
private static void printNum(long num, int n) {
long div = (long) Math.pow(10,n);
StringBuffer sb = new StringBuffer();
for(int i=0 ;i<=n; i++) {
sb.append(num/div);
num%=div;
div/=10;
}
System.out.println(sb.toString());
}
private static void getAns(boolean[] visit, int cnt, int n, LinkedList<Integer> list) {
if(n <cnt) {
if(list.size()>n) {
StringBuffer sb = new StringBuffer();
int leftIdx =0;
int rightIdx =1;
for(int i=0; i<n; i++) {
int leftNum = list.get(leftIdx++);
int rightNum = list.get(rightIdx++);
if (ineqArr[i].equals(LEFT)) { // >
if (leftNum < rightNum) {
return;
}
} else { // <
if (leftNum > rightNum) {
return;
}
}
sb.append(leftNum);
}
sb.append(list.get(leftIdx));
maxAns = Math.max(Long.parseLong(sb.toString()),maxAns);
minAns = Math.min(Long.parseLong(sb.toString()), minAns);
}
return;
}
for(int i=0; i<NUMMAX; i++) {
if(!visit[i]) {
visit[i] = true;
list.offer(i);
getAns(visit,cnt+1,n,list);
visit[i] = false;
list.pollLast();
}
}
}
}
코드 3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
final static int NUMMAX = 10;
final static String LEFT = ">";
static String[] ineqArr;
static long minAns, maxAns;
static boolean[] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ineqArr = br.readLine().split(" ");
solution(n);
br.close();
}
private static void solution(int n) {
minAns = Long.MAX_VALUE;
maxAns = 0;
visit = new boolean[NUMMAX];
for(int i=0; i<NUMMAX; i++) {
visit[i] = true;
getAns(i, 0, n, i);
visit[i] = false;
}
System.out.println(maxAns);
StringBuffer sb = new StringBuffer("%0").append(n+1).append("d");
System.out.println(String.format(sb.toString(),minAns));
}
private static void getAns(int now, int idx, int n, long num) {
if(idx == n) {
maxAns = Math.max(maxAns, num);
minAns = Math.min(minAns, num);
return;
}
if(ineqArr[idx].equals(LEFT)) { // >
for(int i=0; i<now; i++) {
if(!visit[i]) {
visit[i] = true;
getAns(i, idx + 1, n, num * 10 + i);
visit[i] = false;
}
}
} else { // <
for(int i=NUMMAX-1; i>now; i--) {
if(!visit[i]) {
visit[i] = true;
getAns(i, idx + 1, n, num * 10 + i);
visit[i] = false;
}
}
}
}
}
반응형