[백준/2529] 나는 당연히 bubble sort로 풀면될줄 알았지..

 

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

2529번: 부등호

 

부등호를 이용해 가장 큰 수와 작은수를 만들어내는 문제다.

 

 

 

 

예를들어 부등호가 [ > < > ] 가 주어진다면 이 부등호에 들어맞는 숫자는 [ 9 > 7 < 8 > 6 ] 정도로 추측할 수 있다.

 

물론 [ 3 > 0 < 1 > 2 ]도 된다. 다양한 경우가 가능하니 최소, 최대 나열 경우가 있고 그 두가지를 찾으라는게 문제였다.

 

 

 

 

어엄청 고민고민하다가 ㅋㅋ 너무 일차원적으로 생각하지 말아야지를 되네이며 트리로 풀어볼까, brute-force인가.. 다이나믹인가.. bellman-ford인가 삽질을 하다 아래 조건문을 생각했다.

if (M[j] == "<" and arr[j] > arr[j+1]) or (M[j] == ">" and arr[j] < arr[j+1]):

이거 어디서 많이 봤는데??

 

 

 

 

Bubble sort..!!

 

 

 

 

이거 bubble sort 문제구나!! 완전 확신에 가득차서 풀이함 ㅋㅋㅋ

 

Max값, Min값을 찾으라는 문제면 아래와 같은 알고리즘으로 풀면 된다고 생각했다.

 

Max인 경우 => 98765순서로 나열한후 부등호에 맞게 sorting하면 됨
Min인 경우 => 012345..(여기서는 0이 맨 앞에 와도 된다)순서로 나열한 후 부등호에 맞게 sorting하면 됨

 

 

 

 

 

 

내가 풀이한 코드

그래서 나온 코드는 아래와 같다.

def sol(inputArr,find) :
    arr=[]
    
    if find == "max" :
        for i in range(9,9-len(inputArr)-1,-1):
            arr.append(i)
    else :
        for i in range(0,len(inputArr)+1):
            arr.append(i)
    
    #bubble sort
    for i in range(0, len(arr)-1) :
        for j in range(0, len(arr)-1-i) :
            if (M[j] == "<" and arr[j] > arr[j+1]) or (M[j] == ">" and arr[j] < arr[j+1]):
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
    
    return arr

N = int(input())
M = list(input().split(" "))

print(*sol(M,"max"),sep='')
print(*sol(M,"min"),sep='')

 

근데 나만 이렇게 풀었다 ㅋㅋㅋ 다른분들은 다 DFS와 재귀로 접근한 것

 

DFS로 접근하는 방법은 다른분들 코드를 보며 이해하는 중인데 깨달음이 오는데로 아래에 덧붙이겠다.

 

 

확실히 위에 방법으로 하면 MIN과 MAX외에는 찾을 도리가 없을 듯 하다. (만약 모든 경우를 구하라고 하면)

 

 

 

 

 

+ 약간 이해가 되서 덧붙임! 코드는 여러 블로그를 참고했다

DFS로 접근하는 방법

 

내가 봤을때 DFS에서 핵심 개념은 이런 것 같았다.

 

1. 1부터 10까지 집어넣어 보면서 확인

2. 예를들어 0으로 시작했으면 1을 넣어보고 체크한다음 관계를 만족하지 않는다면 2를 넣어본다

3. 이런식으로 하면 01..아니군 021 아니군 .. 이런식으로 늘어날 것

 

def sol(index, ansStr) :
    
    #0부터 9까지 무작정 집어넣기
    for i in range(10) :
        #이미 str에 있는지 체크
        if visited[i] == 0 :
            #str이 비어있거나 주어진 부등호에 만족하면 맨 끝에 붙여주기
            if index == 0 or check(ansStr[-1], str(i), M[index-1]) :
                visited[i] = 1
                #다음 순서를 향해 궈궈~
                sol(index+1, ansStr+str(i))
                visited[i] = 0

위 개념을 코드로 나타내면 이런느낌?

 

 

 

 

 

종료조건이 사실 잘 이해가 안되었었는데 나는 이런식으로 이해했다.

 

1. 종료조건str의 길이가 주어진 길이만큼 채워졌는지 체크한다 (부등호가 4개면 5자리 숫자이므로 5를 체크할때 그만)

2. 처음 종료된 경우라면 0으로 시작해서 작은 숫자부터 채웠으므로 가장 작은 경우일 것이다

3. 마지막으로 종료된 경우라면 9로 시작해서 작은 숫자부터 채웠으므로 가장 큰 경우일 것이다.

 

def sol(index, ansStr) :
    if index == N + 1:
        if len(minStr) == 0 :
            minStr = ansStr
        else :
            #여기는 아마 끝까지 계속 업데이트 될것이다
            maxStr = maxStr

 

 

 

 

 

DFS는 종료조건과 어떤 인자를 넘겨줄 것인가에 대한 파악이 중요해 보인다.

N = 4
M = ["<","<","<",">"]

#0~9까지 숫자를 겹치지 않게 한번씩만 넣어야 한다
visited = [0] * 10
minStr = ""
maxStr = ""

def check(i,j,k) :
    if k == '<' :
        return i < j
    else :
        return i > j

def sol(index, ansStr) :
    global minStr, maxStr
    
    #종료조건
    if index == N + 1:
        if len(minStr) == 0 :
            minStr = ansStr
        else :
            maxStr = ansStr
        return
            
    #0부터 9까지 무작정 집어넣기
    for i in range(10) :
        #이미 str에 있는지 체크
        if visited[i] == 0 :
            #str이 비어있거나 주어진 부등호에 만족하면 맨 끝에 붙여주기
            if index == 0 or check(ansStr[-1], str(i), M[index-1]) :
                visited[i] = 1
                #다음 순서를 향해 궈궈~
                sol(index+1, ansStr+str(i))
                visited[i] = 0
    

# dfs이므로 맨 위(아무것도 없는 상태)에서 시작
sol(0,"")
print(minStr)
print(maxStr)