SWEA.D3 - 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

🔗문제 링크

SW Expert Academy

 

 

👩‍💻참고 블로그 

https://mungto.tistory.com/212

최대상금 Python(SW Expert Academy)

 

def dfs(count):
    global answer
    # 횟수를 다 사용했다면
    if not count:
        print("count를 다 사용했어")
        # 숫자로 바꿔보고
        temp = int(''.join(values))
        # 가지고 있는 최대수보다 크다면 갱신
        if answer < temp:
            answer = temp
            print("갱신했어 "+str(answer))
        return
    # 바꿔야 하니까 이중 포문
    for i in range(length):
        print("i의 값은 다음과 같다 :"+str(i))
        # 경우의 수를 찾는거니까 i보다 큰위치부터
        for j in range(i + 1, length):
            # 두개의 위치를 바꾸고 나서
            values[i], values[j] = values[j], values[i]
            print("i:"+ str(i),"j:"+ str(j))
            # 가지치기 해야하니까 일단 합쳐보고
            temp_key = ''.join(values)
            # 어떤수가 몇회차에 나왔는지 체크 1이면 안나온거니까 경우의수에 넣어주기
            print("현재 visited는 ?")
            print(visited)
            if visited.get((temp_key, count - 1), 1):
                print("if문에 들어왔어 ")
                print(visited)
                # 이숫자는 몇회차에 사용했으니까 체크해주고
                visited[(temp_key, count - 1)] = 0
                print(visited)
                # dfs도 돌려주고
                print("dfs 돌릴거지롱")
                dfs(count - 1)
            # 다 썻으면 원상복귀
            values[i], values[j] = values[j], values[i]


for t in range(int(input())):
    answer = -1
    value, change = input().split()
    # 바꾸기 편하려고 리스트화시킴
    values = list(value)
    change = int(change)
    # 계속 쓸꺼니까 캐스팅
    length = len(values)
    # 가지치기용 딕셔너리
    visited = {}
    dfs(change)
    print('#{} {}'.format(t + 1, answer))

 

참고 블로그 코드가 쉽게 설명되어 있는 것 같지만 

내 머리로는 따라가지 못해서 .. 

한줄 한줄씩 print 코드를 쳐서 따라잡았다. 

5
123 1
i의 값은 다음과 같다 :0
i:0 j:1
현재 visited는 ?
{}
if문에 들어왔어 
{}
{('213', 0): 0}
dfs 돌릴거지롱
count를 다 사용했어
갱신했어 213
i:0 j:2
현재 visited는 ?
{('213', 0): 0}
if문에 들어왔어 
{('213', 0): 0}
{('213', 0): 0, ('321', 0): 0}
dfs 돌릴거지롱
count를 다 사용했어
갱신했어 321
i의 값은 다음과 같다 :1
i:1 j:2
현재 visited는 ?
{('213', 0): 0, ('321', 0): 0}
if문에 들어왔어 
{('213', 0): 0, ('321', 0): 0}
{('213', 0): 0, ('321', 0): 0, ('132', 0): 0}
dfs 돌릴거지롱
count를 다 사용했어
i의 값은 다음과 같다 :2
#1 321

 이렇게 하니까 좀 이해가 되는 .. -..-

 

- 처음 숫자를 입력받을 때 123 받으면 리스트에 '1','2','3' 들어가게 하고 싶다면 list(value)만 해주면 된다. 

- i는 length(리스트에 들어있는 숫자 개수), j는 i보다 1크고 length보다 작게 하는 식으로 

- 가장 어려웠던 문장은 if visited.get((temp_key, count-1), 1): -> 딕셔너리 visited 안에 (temp_key, count-1)이 있는지 확인하고 없으면 기본값으로 설정해준 1을 반환하니까 if문이 참이 되서 if문 안으로 들어갈 수 있게 된다. (아마?)

 

하면서 느낀건데 이거 .. 수학이랑 비슷하다 (?) 

다른 점은 print로 해서 그 과정을 출력할 수 있다는거 

그 점에서 코딩테스트는 수학보다 할만하다..