SWEA 13428. 숫자 조작 (Python, 완전탐색, D3)

문제 접근

1번의 swap으로 현재의 숫자를 최대 또는 최소로 만들 때의 최댓값과 최솟값을 찾아야 한다.
따라서 두가지 방법이 있는 것 같다.
하나는 가장 간단한 완전탐색이다. 모든 경우를 돌아가면서 swap을 진행하고 그 중 가장 큰 수, 작은 수를 저장하는 것이 가장 간단하다. 하지만 이 경우에는 시간초과가 발생할 수 있기 때문에 잘 확인하는 것이 중요하다.

다른 하나는 Greedy방식이다. 그리디 방식은 여러가지 조건이 많이 붙어야 되기 때문에 구현이 좀 더 복잡하지만 완전탐색보다는 빠르다.

이 문제의 경우에는 9자리 이하의 N이 입력으로 주어지기 때문에 그렇게 크지 않다. 따라서 완전탐색으로 충분히 가능하기 때문에 완전탐색으로 풀었다.

• 바꿀 수 있는 경우의 수
• 스왑하기
• 최대 최소 저장하기

문제 풀이

바꿀 수 있는 경우의 수

바꿀 수 있는 경우의 수는 아래와 같다. 이렇게 바꿀 때 모든 경우를 확인하는 것이다.
따라서 i번째와 j번째의 수를 swap의 파라미터로 넘겨서 return 받은 값이 swap된 값이다.

 for i in range(len(num)-1):
        for j in range(i, len(num)):
        	number = swap(i, j, num)

스왑하기

방금 봤던 swap함수는 아래와 같다.
string을 list화 하고 위치를 바꾼 뒤, join을 통해 다시 문자열로 변환한다. 그 후에 number를 return 해준다.

def swap(i, j, string):
    s_list = list(string)
    s_list[i], s_list[j] = s_list[j], s_list[i]
    number = ''.join(s_list)
    return number

최대 최소 저장하기

이렇게 number를 return 받은 후에는 number의 맨 앞자리에 0이 오면 안된다는 조건이 있기 때문에 이 경우에는 continue를 통해 처리해준다.
그 후에 result_max와 result_min과 각각 비교하여 값을 저장해주면 된다.
이 두 값의 초기값은 입력받은 숫자 그대로의 값인데, 그 이유는 swap을 안했을 경우도 생각해줘야 되기 때문이다.

 result_min = int(num)
 result_max = int(num)
    for i in range(len(num)-1):
        for j in range(i, len(num)):
            number = swap(i, j, num)
            if number[0] == '0':
                continue
            if int(number) > result_max:
                result_max = int(number)
            if int(number) < result_min:
                result_min = int(number)

제출 코드

## 완전탐색으로 진행해보기
T = int(input())
def swap(i, j, string):
    s_list = list(string)
    s_list[i], s_list[j] = s_list[j], s_list[i]
    number = ''.join(s_list)
    return number
for test_case in range(1, T + 1):
    num = input().rstrip()
    result_min = int(num)
    result_max = int(num)
    for i in range(len(num)-1):
        for j in range(i, len(num)):
            number = swap(i, j, num)
            if number[0] == '0':
                continue
            if int(number) > result_max:
                result_max = int(number)
            if int(number) < result_min:
                result_min = int(number)
    print(f'#{test_case} {result_min} {result_max}')