[백준 2529번] 부등호 - 파이썬

문제 링크:

https://www.acmicpc.net/problem/2529

2529번: 부등호

 

---

풀이 유형:

브루트포스 알고리즘, 백트래킹

 

풀이 과정:

이 문제는 전에 풀었던 연산자 끼워놓기의 반대 문제이다. 연산자 끼워놓기의 풀이는 다음 포스트를 참고하자.

https://data-flower.tistory.com/72

[백준 14888번] 연산자 끼워넣기 - 파이썬

 

이 문제는 부등호가 고정되어 있고 해당 부등호를 만족하는 숫자들의 최댓값과 최솟값을 구해야 한다.

예를 들어 부등호가 > < 가 있다면, 8>7<9(879)가 최댓값, 1>0<2(102)가 최솟값이다.

0부터 9까지 숫자를 차례대로 입력받아 DFS를 이용하여 풀면 된다.

주의할 점은 0부터 9까지 순서대로 숫자를 받기 때문에 처음 만들어진 문자열은 최솟값이 되며, 마지막에 만들어진 문자열은 최댓값이 된다.

 

풀이 코드:

# 2529번 부등호

# 입력값 받기
n = int(input())
sign = list(input().split())
# 방문 표시
visited = [False] * 10
# 최댓값, 최솟값
max_ans, min_ans = "", ""

# 연산자 계산
def possible(i, j, k):
    if k == '<':
        return i < j
    else:
        return i > j
    return True

# 최댓값과 최솟값 구하기
def solve(cnt, s):
    global max_ans, min_ans
    # 부등호의 개수 + 1만큼 문자열이 구성되었다면
    if cnt == n+1:
    	# 최솟값이 존재하지 않다면
        if not len(min_ans):
        	# 최솟값으로 추가
            min_ans = s
        # 그 외에는 최댓값
        else:
            max_ans = s
        return
    # 숫자를 0부터 9까지 1개씩 입력받아
    for i in range(10):
    	# 특정 숫자를 아직 방문하지 않았다면
        if not visited[i]:
        	# 문자열이 아직 존재하지 않거나, 계산이 가능한 경우
            if cnt == 0 or possible(s[-1], str(i), sign[cnt - 1]):
            	# 방문 표시
                visited[i] = True
                # 문자열 개수 1개 추가
                solve(cnt+1, s + str(i))
                # 방문 표시 제거
                visited[i] = False
# 함수 실행
solve(0, "")
# 최댓값 출력
print(max_ans)
# 최솟값 출력
print(min_ans)

 

 

 

2529번 부등호