[BaekJoon] 2529 부등호

🔦 문제 링크

✍️ 나의 풀이

---

• 브루트포스로 푼 문제

• 최대,최솟값만 구하면 되므로 시간 절약을 위해 앞, 뒤로 반복문을 돌림

• 공통 : 0 ~ 9까지 숫자에 대해 문자의 갯수보다 하나 많게 순열을 구한다.

• MIN 값

1. 순열이므로 작은 값부터 시작된다.
2. 구한 순열 중 하나를 뽑아 부등호 앞 뒤의 값을 비교한다.
3. 조건이 갯수 만큼 맞으면 해당 순열로 최솟값을 갱신한다.
4. 최솟값을 구했으므로 반복문을 빠져나온다.

• MAX 값

1. 순열리스트의 뒤에서 부터 순열을 뽑는다.
2. 부등호 앞 뒤의 값을 비교한다.
3. 조건이 맞으면 해당 순열로 최댓값을 갱신한다.
4. 최댓값을 구했으므로 반복문을 빠져나온다.

🛠 나의 코드

---

import itertools

num=input()
sign = input().split()
val=[str(x) for x in range(10)]
per = list(itertools.permutations(val, int(num)+1))
flag = 0
min_v = '9999999999'
max_v = '-1'
for comp in per:
    flag=0
    for i in range(int(num)):
        if sign[i]== '<' and comp[i] < comp[i + 1]:
            flag += 1
        elif sign[i]== '>' and comp[i] > comp[i + 1]:
            flag += 1
        else:
            break
    if flag == int(num):
        min_v = min(min_v, str(''.join(comp)))
        break


for k in range(len(per)-1,0,-1):
    flag=0
    for i in range(int(num)):

        if(sign[i]=='<' and per[k][i] < per[k][i+1]):
            flag += 1
        elif(sign[i]=='>' and per[k][i] > per[k][i+1]):
            flag += 1
        else:
            break
    if flag == int(num):
        max_v = max(max_v, str(''.join(per[k])))
        break
print(max_v)
print(min_v)

✍️ 다른 풀이

---

• 좀 더 효율이 코드이다.

• DFS로 중간에 가능하지 않다고 판단되면 그 이상의 경우는 모두 제외했다. (경우의 수를 훨씬 단축시킬 수 있음)

• 0 ~ 9까지 반복하며 이미 있는 값과 부등호에 만족하는 값인지 를 검사하여 다음 단계로 진행한다.

• idx가 조건에 충족되면 최대, 최소값을 갱신한다.

🛠 다른 코드

---

import sys

n = int(input())
oper = input().split()
check = [False] * 10
v = []
mn = sys.maxsize
mn_str = ""
mx = -1
mx_str = ""


def possible(i):
    if oper[i - 1] == '>' and v[i - 1] < v[i]:
        return False
    elif oper[i - 1] == '<' and v[i - 1] > v[i]:
        return False
    return True


def dfs(idx):
    global mn, mx, mn_str, mx_str
    if idx == n + 1:
        v_str = ''.join(map(str, v))
        val = int(v_str)
        if mn > val:
            mn = val
            mn_str = v_str
        elif mx < val:
            mx = val
            mx_str = v_str
        return
    else:
        for i in range(10):
            if check[i] is True:
                continue
            check[i] = True
            v.append(i)
            if idx == 0 or possible(idx):
                dfs(idx + 1)
            check[i] = False
            v.pop()


dfs(0)
print(mx_str)
print(mn_str)

📝 정리

---

• 모든 경우의 수를 따질 수 있는 문제는 거의 없다.
• 어떤 조건을 적용시킬 수 있는지 생각하자.

🎈 참조

---

황소개발자님 블로그