BOJ 2450(모양 정돈) 풀이

이미지를 누르면 문제로 이동합니다

문제를 요약하면 동그라미, 세모, 네모를 같은 모양이 연속으로 나열되도록 최소 횟수로 바꾸는 문제이다.

이문제에서 입력이 1,2,3 즉 동그라미, 세모, 네모만 존재하기 때문에 이 3개의 도형을 배치할 수 있는 경우의 수 6개를 반복문으로 탐색하면서 최소 개수를 구해주는 방식을 떠올릴 수 있다.

 

그다음은 어떻게 최소 개수를 구하냐 인데,

일단 두 도형을 바꿨을 때, 두 도형이 모두 최종적으로 있어야 하는 구간에 들어간다면 이 방법이 두 도형의 최소 변경 횟수가 될 것이다.

 

예를 들어보자.

 

1 3 3 2 1 1 3 2

 

라는 입력이 들어오고, 3 2 1 순서로 나타난다고 해보자.

그러면 최종적으로 3 3 3 2 2 1 1 1 을 만들어야 한다.

 

초기 입력을 숫자의 개수에 따른 구간을 나눠 보면

1 3 3 | 2 1 | 1 3 2

가 되는데 이때 첫번째 구간의 3과, 3번째 구간의 1을 바꾼다면 모두 자신이 있어야 할 구간에 들어가기 때문에 둘을 바꾼 뒤 그 뒤로 건들지 않아도 된다. 이렇게 두 개를 바꿔서 모두 자신이 있어야 할 구간에 들어갈 수 있다면 좋겠지만 그렇지 못한 경우가 있다.

그렇기 때문에 이 과정을 수행한 뒤, 2개의 위치를 바꿨을 때 서로의 위치를 만족하지 않아도 바꾸는 방식을 한번더 사용해 준다면 최솟값을 구할 수 있다.

어떤 i번째 값이 자신이 있어야 하는 위치에 있지 않다면, 1개이상의 다른 위치의 값이 자신이 있어야 할 위치에 있지 않다는 자명하다. 그렇기에 n번 탐색을 하면서 자신의 위치에 해당되지 않으면, 해당되는 위치로 바꿔주는 과정을 거치면 최솟값을 구할 수 있다.

 

import sys
import math
inf=math.inf
input=sys.stdin.readline
a=int(input())
l=list(map(int,input().split()))

st=[]
nidx=[[]for i in range(4)]
for i in range(a):
    nidx[l[i]].append(i)

#print(nidx)
for i in range(1,4):
    for g in range(1,4):
        if i!=g:
            for j in range(1,4):
                if i!=j and g!=j:
                    st.append([i,g,j])

#print(st)
ans=inf
for i in range(len(st)):
    cnt=0
    fr=len(nidx[st[i][0]])
    sc=len(nidx[st[i][1]])
    th=len(nidx[st[i][2]])
    start_idx=[0,fr,fr+sc,a]
    ud_idx=[0,fr,fr+sc,a]
    inp=[l[i]for i in range(a)]
    ch2={1:{1:[],2:[],3:[]},2:{1:[],2:[],3:[]},3:{1:[],2:[],3:[]}}
    for Q in range(3):
        for g in range(start_idx[Q],start_idx[Q+1]): #현구간의 번호 : st[i][Q]
            if st[i][Q]!=inp[g]:
                ch2[st[i][Q]][inp[g]].append(g)

    #print(ch2)

    for p in range(1,4):
        for g in range(p+1,4):
            CNT=min(len(ch2[p][g]),len(ch2[g][p]))
            cnt+=CNT
            for idx in range(CNT):
                U=ch2[p][g][idx]
                V=ch2[g][p][idx]
                inp[U],inp[V]=inp[V],inp[U]

    #print(cnt)
    ##print("new")
    #print(st[i])
    #print(start_idx)
    #둘이 바꿔서 원래 위치로 갈때

    
    for Q in range(3):
        for g in range(start_idx[Q],start_idx[Q+1]): #현구간의 번호 : st[i][Q]
            if st[i][Q]!=inp[g]:
                locate_idx=st[i].index(inp[g])
                IDX=ud_idx[locate_idx]
                #print("locate_idx")
                #print(locate_idx)
                while inp[IDX]==inp[g]:
                    ud_idx[locate_idx]+=1
                    IDX=ud_idx[locate_idx]

                inp[g],inp[IDX]=inp[IDX],inp[g]
                ud_idx[locate_idx]+=1
                cnt+=1

    #print(cnt)

    ans=min(ans,cnt)

    
print(ans)

 

문제를 풀때 교체를 통해 둘 다 만족하는 경우를 따지지 않고 무지성으로 코딩을 했다가 고치다 보니 코드가 많이 더러워졌다. 그러니 코드를 보기보단 설명을 보고 직접 작성하길 추천하며, 궁금한 점은 댓글에 올려주면 최대한 빨리 답변을 달겠다.