Python으로 푸는 SW Expert Academy 1244. 최대 상금

SW Expert 아카데미 1244. 최대 상금

문제에서는 숫자판을 주어진 횟수만큼 교환하여 최대 숫자를 만들도록 코드를 짜야한다.

미리 말해두지만 여기에 올린 코드는 남이 이해하기에 좋은 코드가 아니다. (효율도 그닥 안좋은 것 같고..)

그럼에도 이 포스팅을 하는 이유는 문제가 계속 fail이 뜨는데 그 이유를 모르는 사람이 있다면 풀이 방법을 참고하면 해결할 수 있기 때문이다.

앞서 말하지만, 주어진 케이스가 잘못된게 아니고 그냥 코드를 잘못 짠거다.

나중에  알고리즘을 다시 정리해서 좀더 깔끔한 코드로 포스팅을 수정했으면 좋겠다.

github에서 코드 보기

삼성 SW Expert Academy에서 푼 문제 리스트 보기

문제에서 제시한 조건

- 주어진 횟수만큼 반드시 모두 교환이 일어나야 한다. 

- 동일한 위치의 교환도 가능하다. (94를 10번 교환해도 94이다. 즉, 짝수만큼 교환하면 그 자리 그대로 있을 수 있고, 홀수만큼 교환한다면 순서가 반드시 하나는 뒤바뀌어 있어야 한다)

문제를 틀렸다면 이걸 볼 것

제시한 10개의 케이스 중에서 5번째와 10번째가 오답인 경우에는 아래를 보고 해결하면 된다. 

1. 케이스 5번째가 오답인 경우 - 앞에서 부터 한자리씩 교환을 했을 경우 다음의 케이스를 놓쳐 결과 값이 오답을 낸다.

32888 2 -> #5 88832

앞에서부터 순서대로, 뒤에 있는 최댓값 중에 가장 index가 큰 경우와 교환을 했다면 위와 같은 예외 케이스를 놓쳤을 수도 있다.

뒷부분에 교환하고자 하는 최댓값이 연속으로 놓여져 있고, 교환하려고 하는 앞의 숫자들이 연속으로 감소하는 경우에는 교환이 동시에 이뤄져야 한다.

(32)8(88) -> (88)8(32) 

만약 이 부분을 고려하지 않았을 경우에는 88823의 오답이 나오게 된다.

2. 케이스 10번째가 오답인 경우 - 주어진 횟수만큼 모두 교환을 하지 않았을 경우 다음의 입력값에 대해서 오답을 낸다.

456789 10  ->  #10 987645

숫자판이 최댓값일 경우에 교환을 멈추었다면 987654이 나왔을 것이다. 

그러나 교환 횟수를 모두 소모해야 하므로 최댓값과 최소한만 차이가 있도록 마지막 두자리를 교체하게 되어 987645가 정답이 된다.

문제 풀이 방법

이 문제는 문제와 예시만 잘 이해하면 된다. 그렇지 않으면 아래와 같이 코드가 더러워질 수가 있다. 

문제에서 제시한 두 조건을 빠삭하게 이해하고 제시된 케이스 5,10번째를 무난하게 통과한다면 아마 문제를 푸는데는 오래걸리지 않을 것이다. 

내가 푼 방법은 checkIndex 를 0으로 두고 맨 앞 checkindex의 값부터 뒤에 있는 값들의 촤댓값 target과 값을 비교하여, check 값이 작을 경우 교환을 한다는 것을 큰 틀로 잡았다.

그 사이에 문제를 틀렸다면 이걸 볼 것 부분을 고려해서 코드에 조건을 채워넣으면 된다. 

파이썬 코드

def gen(n):
    for i in range(n):
        yield input().strip().split()
def solve(n, count):
    number = list(map(int, n))
    # 중도에 멈춰야 하는 경우 flag를 False로 변경
    flag = True
    checkIndex = 0 #앞부분부터 체크하고 있는 index
    targetIndex = -1 #교환할 index
    lastIndex = len(number) - 1
    while count and flag:
        chk = number[checkIndex]
       # target이 number의 범위를 초과하는지 체크
        if checkIndex + 1 < lastIndex:
            other = max(number[checkIndex + 1:])
            otherCount = number.count(other)
            # checkIndex 값과 뒷자리의 최댓값과 값 비교
            if chk < other:
                changeLen = 0
                # 뒤에서부터 target의 index 확인
                for i in range(lastIndex, 0, -1):
                    if number[i] == other:
                        targetIndex = i
                        break
                # targetIndex의 값이 여러개인 경우 연속되어 있는지 체크 ex) (32)8(88) -> (88)8(32)
                if otherCount > 1:
                    for i in range(checkIndex, lastIndex):
                        if number[checkIndex] >= number[i]:
                            changeLen += 1
                        else:
                            break
                    # 변경할 길이는 checkIndex 부분의 감소하는 값들의 갯수, 뒷자리의 연속된 값의 갯수, 교환 가능한 count의 수 중에 최솟값
                    changeLen = min(changeLen, otherCount, count)
                    for i in range(0, changeLen):
                        if number[targetIndex] == number[targetIndex - i]:
                            break
                        else:
                            targetIndex -= 1
                    # targetIndex 부터 changeLen만큼 통째로 자리 교환
                    number = number[0 :checkIndex] + number[targetIndex:targetIndex + changeLen] \
                            + number[checkIndex + changeLen: targetIndex]+ number[checkIndex:checkIndex + changeLen] \
                            + number[targetIndex + changeLen:]
                    # 변경한 길이 만큼 차감
                    count -= changeLen
                else:
                    # 한개만 바꾸면 되는 경우
                    number[checkIndex], number[targetIndex] = number[targetIndex] , number[checkIndex]
                    count -= 1 # 변경 count 차감
        checkIndex += 1
        # 마지막 index까지 갔으나 count가 남아 있을 경우
        if checkIndex == lastIndex and count > 0:
            # 동일한 자리 변경이 가능하므로 변화가 없다
            if count % 2 == 0:
                flag = False
            else:
                # 꼭 한번은 바꿔줘야 한다.
                # 동일한 숫자가 2번 이상 있는 경우 : 그 분을 교환하면 되므로 flag를 Flase로 변경
                # 동일한 숫자가 없는 경우 : 맨 마지막 두자리의 값을 변경
                for i in number:
                    if number.count(i) >= 2:
                        flag = False
                if flag:
                    number[lastIndex], number[lastIndex -1] = number[lastIndex - 1], number[lastIndex]
                    flag = False
    return ''.join(map(str, number))
 
num = 0
n = int(input().strip())
for n, count in gen(n):
    num += 1
    print('#{0} {1}'.format(num, solve(list(n), int(count))))

#1244 최대 상금 #python 1244 최대 상금 #1244. 최대 상금 #1244 최대 상금 python #Python으로 푸는 SW Expert Academy 1244. 최대 상금 #SW Expert Academy

#파이썬 1244 #파이썬 1244 최대 상금 #1244 최대 상금 파이썬 #1244 최대 상금 정답