글 읽기 - 그리디로 풀 수 없는 문제인건가요..? 파이썬 24% 틀렸습니다.

ckatodmlrna 1년 전 0

24%에서 틀렸습니다가 나옵니다.

그리디로 풀었는데 그래도 테케 다 생각해서 작성했고 어느 부분이 반례인지 모르겠네요 ㅠ

제가 풀이한 방법입니다.

1. 앞자리 수부터 뒷자리 수들 중 max 수로 채워 나간다.

2. 만약 max 값이 여러 개가 나오면, 앞으로 수정할 뒷자리 수를 확인하며, 가져올 index를 정한다.

3. -1은 번호가 len이 1인데 k가 0보다 클 경우와 숫자가 2자리숫잔데 뒷자리가 0일때 반환한다.

-1 부분이 더 추가되야 할 부분이 있는 걸까요? 24%가 어떤 형태인지를 알 수 없네요 ㅠ

혹시 반례 알고 계시면 도와주세요......

number, K = input().split()
numbers = list(map(int,list(number)))
number_set = {}
for num in numbers:
    try: number_set[num] += 1
    except: number_set[num] = 1

K = int(K)
def solution():
    global K
    corrent_position = 0 #현재 바뀌어야 할 위치
    corrent_k = 0 #현재 k 수

    # 전체 k수가 0보다 큰데 len(numbers)이 1이면 -1 반환 (예시 9 2)
    if K > 0 and len(numbers) == 1:
        return [-1]

    while True:
        # corrent_k가 K랑 같아지면 return
        if corrent_k == K:
            return numbers

        # corrent_position이 len(numbers) - 1보다 적으면 앞에서부터 최대값만 교환
        if corrent_position < len(numbers) - 1:
            # corrent position 뒤로 max값과 그에 대한 index들 구하기
            max_num = max(numbers[corrent_position + 1:])
            max_indexs = [i + corrent_position + 1 for i in range(len(numbers[corrent_position + 1:])) if numbers[i + corrent_position + 1] == max_num]

            #만약 남은 k 횟수가 max index들보다 크거나 같으면 최대한 큰 수를 앞으로 옮겨야함 (예시: 342555 3)
            if K - corrent_k >= len(max_indexs):
                #뒤 숫자들과 비교해가며 순위 체크
                sorted_numbers = sorted([(num,i) for i, num in enumerate(numbers[corrent_position:corrent_position + len(max_indexs)])],reverse=True)
                max_index = max_indexs[sorted_numbers.index((numbers[corrent_position],0))]
            #만약 더 작으면 모든 max value를 수정할 수 없으므로 작은 순대로 뒤부터 바꿔주는 것으로 생각
            else:
                cut_len = K - corrent_k
                max_indexs = max_indexs[::-1]
                sorted_numbers = sorted([(num,i) for i, num in enumerate(numbers[corrent_position:corrent_position + cut_len])])
                max_index = max_indexs[sorted_numbers.index((numbers[corrent_position],0))]

            if max_num == 0 and len(max_indexs) == 1 and corrent_position == 0: #만약 처음에 그 다음으로 max값이 0이고 길이가 1이면 return -1 (90 1)
                return [-1]

            if max_num > numbers[corrent_position]: # max value가 기존 numbers보다 더 크면, 서로 switch
                tmp = numbers[corrent_position]
                numbers[corrent_position] = numbers[max_index]
                numbers[max_index] = tmp
                corrent_k += 1 #k수를 늘려줌
            corrent_position += 1 #바꿀 현재 위치 변경

        else: #corrent_position이 len(numbers) - 1과 같거나 크면
            if not max(list(number_set.values())) > 1: #만약에 반복되는 수가 있다면, 그것만 계속 교환해주면 되므로, 아닐 경우만 판단
                #아닐 경우면 젤 숫자가 적은 끝부분들만 계속 교환함
                tmp = numbers[-1]
                numbers[-1] = numbers[-2]
                numbers[-2] = tmp
            corrent_k += 1 #k의 수를 늘려줌

print(''.join(list(map(str,solution()))))

pyb1031 1년 전 5

n,k=381993,3

나온답: 998133

나와야할답: 998313

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

그리디로 풀 수 없는 문제인건가요..? 파이썬 24% 틀렸습니다.

ckatodmlrna 1년 전 0

pyb1031 1년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말