BOJ 1071번: 소트

www.acmicpc.net/problem/1071

1071번: 소트

N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다.

 

문제풀이:

연속된 두 수가 연속된 값일 경우 (A[i] + 1 == A[i+1]) A[i+1]과 그 이후에 나오는 수 중 A[i+1]이 아닌 수 A[index]를 찾는다. 그리고 찾은 A[index]가 A[i]와 같다면 ([1, 2, 2, 1])같은 경우.. swap(A[i], A[i+1]) 한다. 아닌 경우에는 swap(A[i+1], A[index])

그리고 이때 인덱스가 N을 넘어가도록 A[i+1]과 다른 수가 나오지 않으면 A[i]와 A[i+1]을 swap한다. 

 

[1,1,2,2]같은 경우에는 한 번 돌리는 걸로는 구할 수 없으므로 while문을 이용해서 한 번 함수를 돌리고 연속되는 수가 있는지 체크해서 연속되는 수가 없을 때까지 함수를 계속 돌린다..

 

import sys

N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
num.sort()

def swap(num):
    global N

    for i in range(N-1):

        if (num[i]+1 == num[i+1]):
            index = i+2
            if (index > N-1):
                temp = num[i+1]
                num[i+1] = num[i]
                num[i] = temp
                #swap(num[i], num[i+1])
                continue
                
            while (num[i+1]==num[index]):
                index+=1
                if (index>N-1):
                    temp = num[i+1]
                    num[i+1] = num[i]
                    num[i] = temp
                    break
                    #swap(num[i], num[i+1])
            if (index<=N-1):
                if (num[index]==num[i]):
                    temp = num[i+1]
                    num[i+1] = num[i]
                    num[i] = temp
                    #swap(num[i], num[i+1])
                else:
                    temp = num[index]
                    num[index] = num[i+1]
                    num[i+1] = temp
                    #swap(num[i+1], num[index])
            
swap(num)
while (True):
    check = 0
    for i in range(N-1):

        if (num[i]+1 == num[i+1]):
            check = 1
            swap(num)
            break
    if (check==0):
        break

for i in num:
    print(i, end=" ")

 

ㅈ   ddfd dfsda

fd adfs fdfa 

어려웠고 오래걸렸는데ㅠㅠ 처음엔 그냥 연속되는 두  숫자를 swap 하기도 해보고, i+2번째 수와 i+1번째 수를 swap하기도 해봤는데 최적의 경우를 찾는 규칙을 찾는 게 어려웠다. 그래도 내 손으로 풀어서 뿌듯하다..