최대 상금

from collections import defaultdict
T = int(input())
temp = defaultdict(list)


def swapCards(idx, cardList):
    cur = int(cardList[idx])
    cand = [int(x) for x in cardList[idx+1:]]
    maxCand = str(max(cand))
    maxIdx = (len(cardList)-1) - cardList[::-1].index(maxCand)

    if cur >= int(maxCand):
        return False
    else:
        cardList[idx] = str(maxCand)
        cardList[maxIdx] = str(cur)
        temp[maxCand].append(maxIdx)
        return True


def dupExists(cardList):
    for c in cardList:
        if cardList.count(c) > 1:
            return True
        else:
            return False


for test_case in range(1, T + 1):
    cards, swapCnt = map(int, input().split())
    cardList = list(str(cards))
    temp.clear()
    idx = 0
    while swapCnt and idx < len(cardList)-1:
        if swapCards(idx, cardList):
            swapCnt -= 1
            idx += 1
        else:
            idx += 1

    # 최대가 되었지만 swap 횟수가 남은 상황
    if swapCnt > 0 and idx >= len(cardList)-1:
        if swapCnt % 2 != 0 and not dupExists(cardList):
            last = cardList[len(cardList)-1]
            cardList[len(cardList)-1] = cardList[len(cardList)-2]
            cardList[len(cardList)-2] = last

    # 같은 숫자를 swap 한 경우 순서 보정 가능
    for k, v in temp.items():
        if len(v) > 1:
            tempVal = []
            v.sort()
            for vv in v:
                tempVal.append(cardList[vv])
            tempVal.sort(reverse=True)
            tempIdx = 0
            for vv in v:
                cardList[vv] = tempVal[tempIdx]
                tempIdx += 1
    cardList = [str(x) for x in cardList]
    print("#" + str(test_case) + " " + ''.join(cardList))

D3 문제였지만 엣지 케이스를 상당히 많이 확인해야 하는 조금 까다로운 문제였다.

핵심 알고리즘 자체는 순차적으로 탐색하고 나머지와 비교하면서 swap 해주면 되는 간단한 로직이었지만,

최대 수를 만들고 swap 횟수가 남았을 때의 처리, 같은 수를 바꾼 카드의 경우 swap 횟수를 차감하지 않고 순서를 보정할 수 있는 처리 등 신경 써야 하는 예외 사항들이 많았다.

하지만 이런 스타일의 코드를 작성하면 예외 케이스를 놓치기 매우 쉽다. 조금만 테스트 케이스가 치밀하고 세밀해지면 반드시 100% 맞춘다고 생각할 수는 없다.

따라서 우선, 자료구조의 사이즈에 따라 다르겠지만 이 문제의 경우 완전탐색이 타임아웃 되지 않음을 인지하고 차라리 모든 swap 경우의 수를 구해서 그 중에서 max 를 반환하는 코드가 더 좋은 코드라고 생각한다.

아래와 같이 말이다.

⭐️
T = int(input())

for test_case in range(1, T + 1):
    # 숫자판의 정보 board, 교환 횟수 n
    board, n = input().split()
    n = int(n)
    # 중복을 제거한 경우의 수를 담아주기 위한 set
    now = set([board])
    nxt = set()

    # 교환 횟수만큼 반복
    for _ in range(n):
        while now:
            s = now.pop()
            s = list(s)
            # 가능한 모든 교환 경우의 수를 nxt에 담는다
            # set 자료구조의 특성상 중복은 알아서 걸러진다.
            for i in range(len(board) - 1):
                for j in range(i + 1, len(board)):
                    s[i], s[j] = s[j], s[i]
                    nxt.add(''.join(s))
                    # 원상복귀
                    s[i], s[j] = s[j], s[i]

        # 모든 경우의 수를 nxt에 담았으니
        # 다음 교환을 위해 now에 nxt를 nxt에 빈 set를 할당
        now, nxt = nxt, now

    answer = max(map(int, now))
    print("#" + str(test_case) + " " + str(answer))

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD