[BaekJoon] 2529 부등호

pyh8618·2020년 9월 25일
0
post-thumbnail

🔦 문제 링크

✍️ 나의 풀이


  • 브루트포스로 푼 문제

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

  • 공통 : 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까지 반복하며 이미 있는 값부등호에 만족하는 값인지 를 검사하여 다음 단계로 진행한다.

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

🛠 다른 사람 코드


n = int(input())
op = input().split()
c = [False] * 10
mx, mn = "", ""

def possible(i, j, k):
    if k == '<':
        return i < j
    if k == '>':
        return i > j
    return True

def solve(cnt, s):
    global mx, mn
    if cnt == n + 1:
        if not len(mn):
            mn = s
        else:
            mx = s
        return
    for i in range(10):
        if not c[i]:
            if cnt == 0 or possible(s[-1], str(i), op[cnt - 1]):
                c[i] = True
                solve(cnt + 1, s + str(i))
                c[i] = False
solve(0, "")
print(mx)
print(mn)

📝 정리


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

🎈 참조


황소개발자님 블로그

profile
Go Go

0개의 댓글