글 읽기 - 틀렸습니다라고 나오는데 반례 좀 찾아주세요.

tagun11 4년 전 0

언어는 파이썬입니다.

기본적인 알고리즘만 설명 드리자면 가능한 숫자의 종류를 생각합니다. 만약 1 1 1 1 2 2 2 3 3 3 이 주어진다면 가능한 숫자의 종류는 총 1, 2, 3으로 3개라고 생각을 합니다. 그리고 종류가 2개가 될 때까지 이전 수보다 1 큰 수가 아닌 수 중에서 가장 작은 수를 계속 뽑습니다. 그 후 숫자의 종류가 2개 남았을 경우 둘의 값을 비교하고 1차이라면 더 큰 숫자를 먼저 출력하고 그 뒤에 더 작은 숫자를 출력하는 방식으로 하였습니다. 주어진 test_case도 모두 맞고 질문에 기재된 반례 경우도 모두 맞았고 나름 만들어본 숫자가 하나인 경우, 랜덤으로 막 만든 경우 등 모두 만들어 봤는데 통과를 하는데 답을 내자마자 바로 '틀렸습니다'가 나오네요. 잘못된 부분 좀 알려주세요.

from collections import Counter

input()

l = list(map(int,input().split()))
c = Counter(l)
c2= sorted(c,reverse=True)
num_type = len(c2)
res=[]

if num_type > 2:
    res.append(c2[-1])
    c[c2[-1]]-=1
    if c[c2[-1]] ==0:
        num_type-=1

while num_type > 2:
    i = -1
    while c[c2[i]] == 0 or c2[i] == res[-1]+1:
        i-=1
    res.append(c2[i])
    c[c2[i]]-=1
    if c[c2[i]] == 0:
        num_type -=1

if num_type==2:
    if res:
        print(*res, end= " ")
    i = 0
    j = 0
    while c[c2[i]] == 0:
        i += 1
    while c[c2[j]] == 0 or j == i:
        j += 1
    if c2[i]-c2[j] == 1:
        for _ in range(c[c2[i]]):
            print(c2[i],end=" ")
        for _ in range(c[c2[j]]):
            print(c2[j],end=" ")
    else:
        for _ in range(c[c2[j]]):
            print(c2[j], end=" ")
        for _ in range(c[c2[i]]):
            print(c2[i],end= " ")
else:
    for _ in range(c[c2[0]]):
        print(c2[0],end=" ")

humit 4년 전 1

8
1 2 3 3 3 4 4 7

의 경우 출력이

1 3 2 4 3 3 7 4

가 되어야 하지만 질문자분의 코드를 실행해보면

1 3 2 4 3 3 4 7

로 나오고 있습니다.

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

문제

문제

출처

ICPC

틀렸습니다라고 나오는데 반례 좀 찾아주세요.

tagun11 4년 전 0

humit 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말