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

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

• 문제

문제 풀이

1. 1차 접근 방법
2. 정답 여부
3. 2차 접근 방법
4. 정답 여부

1차 접근 방법

1차로 접근 했을 때는 배열을 순회하면서 현재의 index와 value에 대해서 index도 크고 가장 value가 큰 것을 변경하는 과정을 거쳐서 총 교환 회수에서 빼주었다.
또한, 교환 횟수가 배열을 다 순회하고도 남았을 경우에 짝수 개수이면 49 -> 92 -> 49 (총 2회) 다시 제자리 값으로 돌아오기 때문에 넘겨주고, 홀수인 경우에는 중복 숫자가 있으면 짝수 개수처럼 처리하고, 중복 숫자가 없는 경우에는 마지막 두 자리 수를 변경해주었다.

import sys
sys.stdin = open("1244_D3/input.txt", "r")
from collections import Counter
import time

start = time.time()

T = int(input())
for test_case in range(1, T + 1):
    num, count = map(int, input().split())
    num_list = list(str(num))
    while count > 0:
        for i in range(len(num_list)):
            max_num = max(num_list[i:])
            max_index = list(filter(lambda x: num_list[x] == max_num, range(len(num_list))))[-1]
            if count > 0 and max_index > i and num_list[max_index] > num_list[i]:
                num_list[max_index], num_list[i] = num_list[i], num_list[max_index]
                count -= 1
            else:
                continue
        print(count, num_list)
        if count % 2 == 1:
            isDuplicatedNumber = False
            count_num_dict = Counter(num_list)
            for value in count_num_dict.values():
                print(value)
                if value > 1:
                    isDuplicatedNumber = True
                    break
            print(isDuplicatedNumber)
            if isDuplicatedNumber:
                break
            else:
                num_list[-1], num_list[-2] = num_list[-2], num_list[-1]
                break
        else:
            break
    print('#{} {}'.format(test_case, "".join(num_list)))

end = time.time()
print(f"{end - start:.5f} sec")

1차 정답 여부

정답 여부를 확인 하니 14/15 case를 통과해 fail 처리되었다...ㅜㅜ

문제에서 처음에 제시한 예시 32888 2 에 대해 이 과정으로 처리하면 88823가 되어서 정답인 88832와 달라 테스트 케이스를 통과하지 못한 것이다....

조금 더 자세히 확인했어야 했다...!!!

2차 접근 방법

해결 방법에 대해서 찾아보니 완전 탐색 알고리즘을 통해서 수행하면 되었다.

• 완전 탐색 알고리즘??
  • 모든 경우의 수를 탐색'하면서 원하는 결과를 얻는 알고리즘이다.
  • for문과 if문으로 다 탐색하여 볼 수도 있지만, back-tracking, dfs 등 r가지치기를 통해 더 빠르게 해결할 수 있다.
• dfs를 통해 문제를 해결해보겠다.

입력 받은 숫자를 리스트로 만들고, 해당 리스트에서 만들 수 있는 모든 수를 dfs로 탐색한다.

주의할 점은 dfs로 탐색 후 다시 리스트를 원 상태로 복구해놓아야 백트래킹을 원활하게 할 수 있다.(중요)

그러면 15(6C2 -> 최대 6의 문자열 길이에서 2개의 문자를 선택)의 10(문자 최대 교환 수)승의 시간 복잡도가 발생해 시간 초과가 발생한다.

이를 위해 가지치기를 해야한다.

 

if (n, int("".join(num_list))) not in v:
    dfs(n+1)
    v.add((n, int("".join(num_list))))

이 코드를 통해서 v라는 set 자료구조에 교환한 횟수와 그때의 숫자를 넣어서 해당 횟수와 숫자를 미리 방문했으면 그 하위의 것들은 방문하지 않아도 된다는 것이다. (중복 방문 제외)
이때 주의할 점은 dfs로 방문한 한 후 자료구조에 add하여 방문 처리를 해주어야 한다는 것이다.

이 과정을 거치면 32888 2 같은 경우도 올바르게 88832로 나타나는 것을 확인할 수 있다.

정답 코드

T = int(input())
for test_case in range(1, T + 1):
    num, count = map(int, input().split())
    num_list = list(str(num))
    L = len(num_list)
    v = set()
    answer = 0
    def dfs(n):
        global answer
        if n == count:
            answer = max(answer, int("".join(num_list)))
            return
        for i in range(L - 1):
            for j in range(i + 1, L):
                num_list[i], num_list[j] = num_list[j], num_list[i]
                if (n, int("".join(num_list))) not in v:
                    dfs(n+1)
                    v.add((n, int("".join(num_list))))
                num_list[j], num_list[i] = num_list[i], num_list[j]
    dfs(0)
    print(f'#{test_case} {answer}')