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

문제

• 고려해야 할 점
  중복으로 바꿀 수 있다.
  현재 최대 값이라도 교환 횟수가 남아 있으면 교환 횟수만큼 바꿔야 한다.

코드

T = int(input())
for tc in range(1, T+1):
    n, c = input().split()
    n = list(n)
    stn = sorted(n, reverse=True)
    res = ''

    cnt = int(c)
    idx = 0
    while cnt > 0:
        maxI = idx
        lct = 0
        if n == stn:
            break
        for j in range(idx+1, len(n)):
            if n[j:len(n)].count(max(n[j:len(n)])) > 1: # 바꿀 범위 내에 바꿀 가장 큰 수가 중복일 때
                for k in n[j:j+cnt]: # 앞으로 바꿀 범위 내에 바꿀 값보다 작은 값이 있으면
                    if k < n[idx]:
                        lct += 1 # 작은것들의 개수를 셈
            else:
                if n[maxI] <= n[j]:
                    maxI = j-lct
        if maxI != idx:
            n[maxI], n[idx] = n[idx], n[maxI]
            cnt -= 1
        idx += 1

    def check(n):
        global cnt
        if cnt:
            for i in n:
                if n.count(i) > 1:
                    cnt = 0
                    return
    check(n)
    def last_check(n):
        global cnt
        if cnt:
            if cnt%2:
                n[-1], n[-2] = n[-2], n[-1]
                cnt = 0
            else:
                cnt = 0
    last_check(n)
    print('#{} {}'.format(tc, res.join(n)))

풀이

느낀점 : 와 인간승리

후,,, 사실 금요일 문제인데 이 전부터 만만한줄 알고 시도했다가 실패했던 문제이다.
나는 그리디로 푼거같음. 진짜 빡구현으로,,, 사실 지금 테스트 케이스 말고 다른 테스트 케이스가 들어왔더라면 틀릴지도 모른다.

아무튼 아주 완전 내힘으로 푼 건 아니고.. 테스트케이스 5번때문에 애먹었는데(바꿔야 할 최대 값이 여러개일 때) 구글링하다가 좋은 힌트를 봐서 그걸로 풀었슴

32888 2 일 때 32를 8과 바꿔야 한다
일반 인덱스 값 앞부터 최대값을 바꾸는 로직은 82883이 되어서 만들 수 있는 최대값 88832가 되지 않기 때문에 틀린것임

이걸 해결하기 위해서 바꿀값을 찾을 범위가 중복일 경우의 조건문을 만들어 준 후 바꿀값의 범위 내에서 현재 내가 가지고 있는 값(3)보다 작은 수가 있는지 체크해줌. 이때 작은 수가 있으면(2) lct에 +1 해서 몇개를 가지고 있는지 체크해준다. (지금 발견한건데 만약에 작은수보다 바꿀 횟수가 작으면 lct를 바꿀 횟수로 고정해 주어야 추가 테스트케이스에 대응 할 수 있을듯)
이후 바꿀 최댓값 위치 인덱스 - lct 하면 현재 lcn값이 한개니까 찾은 최댓값 위치보다 한개 앞에 들어가게 됨 그래서 다음에 옮길 2가 들어갈 자리가 생김!!!

엄청 비효율적이지만 풀엇으니 됏음

또다른 방법은 모든 경우의 순열을 만들어 그 중 가장 큰 값을 return 하면 되는 방법이 있다. 무려 코드 길이도 5~600줄밖에 안된다...

T = int(input())
for tc in range(1, T+1):
    n, c = input().split()
    N = len(n)
    num = set([n])  # 중복제거
    com = set()
    c = int(c)

    for _ in range(c): # 횟수만큼 반복
        while num:
            a = list(num.pop())
            for i in range(N):  # powerset 방식
                for j in range(i+1, N):
                    a[i], a[j] = a[j], a[i]
                    com.add(''.join(a))
                    a[i], a[j] = a[j], a[i]
        num, com = com, num  # k만큼 교체 해주면서 모든 경우의 수를 더함

    print('#{} {}'.format(tc, max(num)))

그리고 dfs로 푸는방식도 있던데 어렵다...