baekjoon. 1071 소트 [Platinum V][python]

문제링크 : https://www.acmicpc.net/problem/1071

1071번: 소트

 

최종적인 알고리즘으로는 이 분의 블로그를 참고했다. 

https://hoji25.tistory.com/4

[백준 알고리즘] 1071번 소트 c++

 

1. 사전순으로 가장 앞선 것을 출력해야 하므로 먼저 오름차순 정렬을 한다. 

2. [i] + 1 == [i +1]을 찾으면, 

2-1. [i + 1]보다 큰 숫자가 없다면, [i]와 [i+1]의 순서를 교체한다. 11112222 -> 22221111

2-2. [i + 1]보다 큰 숫자 p가 있다면, [i+1]와p를 교체한다. 111122223 -> 111132222

N = int(input())
numList = list(map(int,input().split()))

# 오름차순으로 정렬
numList.sort()

for i in range(len(numList) - 1):
    # print(numList[i], ' :: ', numList)
    if (i > 0 and numList[i] == numList[i - 1]):
        count = count +1
    else:
        count = 0
    
    if (numList[i] + 1) == numList[i + 1]:
        # i + 1 이 최솟값이라면 
        if (numList[-1] == numList[i + 1]):
            temp = numList[-1]
            del numList[-1]
            numList.insert(i - count, temp)
            # print('>', numList)
        else:
            # i + 1 다음으로 최솟값을 찾아서 다음 값으로 넣어줌 
            for nextIndex in range(i +2, len(numList)):
                if numList[nextIndex] > numList[i + 1]:
                    temp = numList[nextIndex]
                    del numList[nextIndex]
                    numList.insert(i + 1, temp)
                    break
                
        
print(*numList)

 

1% 반례

참고 : https://www.acmicpc.net/board/view/117883

5
0 1 0 1 3
>> 0 0 3 1 1

 

2% 반례 

참고 : https://www.acmicpc.net/board/view/111422

7
1 1 2 3 3 4 5
>> 1 1 3 2 4 3 5

 

9% 반례 

9
1 1 1 1 2 2 2 2 2
>> 2 2 2 2 2 1 1 1 1

 

 

---

 

①차 풀이 

1. 먼저 제일 작은 수를 0번에 넣는다. 

2. 그리고, 1번부터 i = i +1을 만족하지 않은 숫자 중에서 최솟값을 가져와서 다음에 넣어준다. 

>> 이렇게 하면,  12 같은 경우 21을 해야 하는데 그 조건을 만족하지 못하게 된다. 

N = int(input())
numList = list(map(int,input().split()))

# 오름차순으로 정렬
numList.sort()

# https://stackoverflow.com/questions/6142689/initialising-an-array-of-fixed-size-in-python
usedList = [False] * len(numList)

sortedList = [None] * len(numList)

# 처음 숫자는 제일 작은 숫자 ?
sortedList[0] = numList[0]
usedList[0] = True
sortedIndex = 0

# print(len(numList))
# print(numList)
while(sortedIndex < (len(numList) -1) ):
    print(sortedIndex, '>', sortedList)
    print('ㄴ ', usedList)
    
    possibleIndex = 0
    for i in range(len(numList)):
        # print(i, '>>', usedList[i], '>>', (sortedList[sortedIndex] + 1), '!=', numList[i])
        if usedList[i] == False and (sortedList[sortedIndex] + 1) != numList[i]:
            # print('match ? ')
            possibleIndex = i
            
            # 여기 값을 다시 못찾으면 reset ... 
            break;
    
    sortedIndex = sortedIndex + 1
    usedList[possibleIndex] = True
    sortedList[sortedIndex] = numList[possibleIndex]
      
    

print(*sortedList)

 

②차 풀이 

1. 사전순으로 가장 앞선 것을 출력해야 하므로 먼저 오름차순 정렬을 한다.

2. [i] + 1 == [i +1]을 찾으면, 

2-1. [i + 1]보다 큰 숫자 p가 있다면, [i + 1] 전체와 p전체를 교환한다. 1111222233 -> 11113322

2-2. [i + 1]보다 큰 숫자가 없다면, [i]와 [i+1]의 순서를 교체한다. 11112222 -> 22221111

>> 이렇게하면, 1123345 가 있는경우 33이 묶여서 2와 바꾸게 됨으로써, 1123354가 나온다. (답은 1132435이다) 

 

N = int(input())
numList = list(map(int,input().split()))

# 오름차순으로 정렬
numList.sort()

for i in range(len(numList) - 1):
    print(numList[i], ' :: ', numList)
    
    if (i > 0 and numList[i] == numList[i - 1]):
        count = count +1
    else:
        count = 0
        
    # print(count)
    
    if (numList[i] + 1) == numList[i + 1]:
        nextIndex = i + 2
        nextFound = False
        while (nextIndex < len(numList)):
            if numList[nextIndex] > numList[i + 1]:
                next = numList[nextIndex]
                nextFound = True
                break
            nextIndex = nextIndex + 1
        
        nextIndex = i + 2
        if (nextFound):
             while(numList[nextIndex] == next) :
                print('> ',numList[nextIndex],'=', numList)
                next = numList[nextIndex]
                del numList[nextIndex]
                print(numList)
                numList.insert(i + count + 1, next)
                print(numList)
                nextIndex = nextIndex + 1
                
                # 마지막이면 종료 
                if (nextIndex == len(numList)):
                    break
        
            
        tempIndex = i + 1
        if (not nextFound and tempIndex < len(numList)):
            temp = numList[tempIndex]
            
            while(numList[tempIndex] == temp) :
                # print('>> ',numList[tempIndex],'=', numList)
                del numList[tempIndex]
                numList.insert(i - count, temp)
                tempIndex = tempIndex + 1
                
                # 마지막이면 종료 
                if (tempIndex == len(numList)):
                    break
        
print(*numList)