백준 25181번
https://www.acmicpc.net/problem/25181

문제

후기

⏰ 풀이시간 2시간 ++⏰

수열을 돌면서 중복되는 숫자가 나오면, 맨 앞부터 수열을 돌며 바꿔주는

알고리즘을 생각했다. 단순하게 이렇게 생각했는데, 시간초과를 무려 4번을 겪었다.

그 이유인 즉슨,

1 1 2 3 5 6 8 1 1 1 7 같은 경우에서는

이와 같은 순서로 진행된다.

1 2 1 3 5 6 8 1 1 1 7
1 2 3 1 5 6 8 1 1 1 7
1 2 3 1 6 5 8 1 1 1 7
1 1 3 1 6 5 8 2 1 1 7 <<< 바로 이 라인에서 문제가 생기는데,

앞선 과정에서 이미 바꿔졌던 1이 다시 앞으로 가면서,

수열의 인덱스의 2번째에 해당하는(li[1]) 1이 다시 원래의 자리로 돌아가서, 무한 Loop를 반복하게된다.

이 과정을 해결하는 데 시간을 오래 잡아먹었고, 결론은

서로 다른게 나오면 바꿔주는데, 바꿔줄 숫자 역시
바뀌기 전 숫자와 같으면 안된다.

라는 것을 코드에 추가로 구현하여 문제를 해결할 수 있었다.

나의 풀이

import sys
input= sys.stdin.readline
import copy

N = int(input())
li = list(map(int,input().split()))
new_li= copy.deepcopy(li)
li_dict = dict()

if len(li) % 2 == 0:
    k = len(li) // 2 #바꿔야 하는 횟수
else:
    k= (len(li) //2) + 1 #바꿔야 하는 횟수

for i in li:
    if i not in li_dict.keys(): 
        li_dict[i] = 1
    else:
        li_dict[i] += 1

for i in li_dict.items(): # 어떠한 요소의 count수가 리스트의 길이의 몫보다 크면 아무리 바꿔도 원하는 수열이 되지 못한다.
    if i[1] > len(li) // 2:
        print(-1)
        exit()

# 일단 처음으로 변경한다. k-1만큼 for문 돌릴 예정이고,
# list에서 돌면서 해당 리스트 값이 다음에 있는 리스트 값과 다르면 둘이 swap한다음 list를 처음부터 다시 출발한다.
# new_list와 비교하면서 서로 달라야된다.

for i in range(len(li)):
    if li[i] != li[0]: #우선 리스트의 첫번째 요소와 다른 요소를 바꾸고 시작.
        (li[0],li[i]) = (li[i], li[0])
        break


while True:
    error = 0
    for i in range(len(li)): #만약 모든 list의 값들이 전부 다르면 
        if li[i] != new_li[i]:
            error+=1
        else:
            break
    if error == len(li): #해당 리스트를 출력하고 종료한다. 
        print(*li)
        exit()

    for i in range(len(li)):
        if li[i] == new_li[i] :
            for j in range(len(li)):
                if li[j] != li[i] and new_li[j] != li[i]: #서로 다른게 나오면 바꿔주는데, 바꿔줄 숫자 역시 바뀌기 전 숫자와 같으면 안된다.
                    (li[i],li[j]) = (li[j],li[i])