백준 알고리즘 2529번: 부등호

문제 정보

---

 

2529번: 부등호

 

핵심

---

백트래킹으로도 문제를 풀이할 수 있는데, 나는 조금은 다른 방식으로 문제를 풀이했다

일단 문제의 경우 부등호 관계를 만족시키는 최소/최대 정수를 구하는 문제이다

 

중복된 정수는 사용할 수 없으며, 첫 자리에 0이 가능한 것이 특징이다

당연하게도, 최소가 되려면 앞자리의 수가 작아야 하고 최대가 되려면 앞자리의 수가 커야 한다

 

다만 생각해야 할 것은 무작정 앞자리의 수를 최소/최대 수로 집어넣는 것이 아니라, 뒤에 부등호를 잘 보아야 한다는 점이다

첫번째 케이스를 생각해 보자

O < O > O

O 자리에 정수가 들어갈 것이며 최대 경우부터 생각해 보면

첫 O 자리에 가장 큰 정수인 9를 넣게 되면 두번째 O 자리에는 들어갈 수가 없다 (9보다 큰 정수는 없기 때문이다)

따라서 최대 경우를 구할 때에는 뒤따라 오는 < 부등호의 개수를 잘 파악해야 한다

이 경우는 첫번째 O 자리에 8이 들어가고, 두번째 O 자리에 9가 들어가야 최대 경우를 구할 수 있다

 

O < O < O > O

부등호가 하나 더 추가된다면 어떻게 될까?

첫 O 자리에는 7이 들어가야 두번째 O 자리에는 8, 세번째 O 자리에는 9가 들어갈 수 있다

 

규칙을 찾은 것 같다

첫번째 O 자리에 들어갈 수를 고려할 때, 뒤따라 오는 < 부등호의 개수를 함께 고려해야 한다

< 부등호가 1개 있으면, 들어갈 수 있는 숫자 중 가장 최대의 숫자에서 1을 뺀 숫자가 들어가야 하고

< 부등호가 2개 있으면, 들어갈 수 있는 숫자 중 가장 최대의 숫자에서 2를 뺀 숫자가 들어가야 한다

 

첫번째 O에는 뒤따라 오는 < 부등호가 2개 있으므로, 들어갈 수 있는 최대 숫자(9) 에서 2를 뺀 7이 들어간다

두번째 O에는 뒤따라 오는 < 부등호가 1개 있으므로, 들어갈 수 있는 최대 숫자(9) 에서 1을 뺀 8이 들어간다

세번째 O에는 뒤따라 오는 < 부등호가 없으므로, 들어갈 수 있는 최대 숫자(9) 가 들어간다

 

이처럼 > 부등호의 경우에는, 최대 경우에서 고려하지 않아도 된다

 

최소인 경우도 마찬가지이다. 최소의 경우에는 들어갈 수 있는 가장 최소의 숫자와 최대와 반대로 > 부등호를 생각해 주어야 한다

뒤따라오는 O에 현재 자리보다 더 작은 숫자가 들어가야만 성립하기 때문이다

 

정리해 보면,

• 최대인 경우 연속된 < 가 있는지가 중점, 뒤에 나오는 < 들의 개수를 카운팅해서 최대 숫자에서 < 개수만큼 뺀 값이 들어감
• 최소인 경우 연속된 > 가 있는지가 중점, 뒤에 나오는 > 들의 개수를 카운팅해서 최소 숫자에서 > 개수만큼 더한 값이 들어감

 

마지막으로,

숫자들(앞서 설명한 O) 은 부등호의 개수보다 하나가 크다.

따라서 최대의 경우에는 반복이 끝나고 아직 넣지 않은 수들 중 가장 최대의 숫자를 넣어주고,

최소의 경우에는 가장 최소의 숫자를 넣어주면 완성된다

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder maxResult = new StringBuilder();
        StringBuilder minResult = new StringBuilder();
        Set<Integer> maxRest = new HashSet<>();
        Set<Integer> minRest = new HashSet<>();
        for(int i=0; i<10; i++) {
            maxRest.add(i);
            minRest.add(i);
        }

        int N = Integer.parseInt(br.readLine());
        String[] sign = br.readLine().split(" ");
        for(int i=0; i<N; i++) {
            int currentMax = Collections.max(maxRest);
            int currentMin = Collections.min(minRest);
            if(sign[i].equals("<")) {
                int count = 0;
                for(int j=i; j<N; j++) {
                    if(!sign[j].equals("<"))
                        break;
                    count++;
                }
                maxResult.append(currentMax-count);
                maxRest.remove(currentMax-count);
                minResult.append(currentMin);
                minRest.remove(currentMin);
            } else {
                int count = 0;
                for(int j=i; j<N; j++) {
                    if(!sign[j].equals(">"))
                        break;
                    count++;
                }
                maxResult.append(currentMax);
                maxRest.remove(currentMax);
                minResult.append(currentMin+count);
                minRest.remove(currentMin+count);
            }
        }

        maxResult.append(Collections.max(maxRest));
        minResult.append(Collections.min(minRest));
        System.out.println(maxResult.toString());
        System.out.println(minResult.toString());
    }
}

• maxResult는 최대 경우에서 나올 수 있는 최대 정수이고, minResult는 최소 경우에서 나올 수 있는 최소 정수이다
• maxRest 는 최대 경우에서 사용할 수 있는 남은 정수이고, minRest는 최소 경우에서 사용할 수 있는 남은 정수이다
• 해당 수를 사용한 경우에는, 각각의 rest 에서 해당 숫자를 제거해 주는 작업을 한다
• 해당 숫자를 제거하는 연산을 더 효율적으로 진행하기 위하여 HashSet을 사용하였다

 

Source Code on GitHub

---