이번 문제는 그리디 알고리즘을 통해 해결하였다. 처음에는 주어진 리스트에 있는 1, 2, 3의 각 갯수를 세고, 리스트를 앞에서 뒤로, 뒤에서 앞으로 순회하며 연속으로 있는 수의 갯수가 그 수의 전체 갯수의 절반 이상일 경우에 리스트의 다른 곳에서 해당 수를 찾아오는 방식으로 구현하였다. 예제는 맞았지만 4%에서 오답처리 되었다.

다른 방법을 생각하다가, 다른 사람의 풀이를 보게 되었고, 1, 2, 3의 permutation을 만들고, 이를 이용해야 한다는 것을 알게 되었다. 만약 [1, 2, 3]이라는 permutation이 주어졌다면, 1이 들어가야 하는 범위 내에서의 2, 3의 갯수(a)를 구하고, 2가 들어가야 하는 범위 내에서의 3의 갯수(b), 3이 들어가야 하는 범위 내에서의 2의 갯수(c)를 구하고, a+max(b, c)의 값을 구한다. 모든 permutations의 a+max(b, c) 중 가장 작은 값을 결과값으로 출력하였다.

Code

import itertools
n = int(input())
tmp = list(map(int, input().split()))
w = [0 for _ in range(4)]
for i in range(len(tmp)):
    w[tmp[i]] += 1
answer = 1e9
seq = list(itertools.permutations([1, 2, 3], 3))
for i in range(len(seq)):
    ans12, ans13, ans2, ans3 = 0, 0, 0, 0
    for j in range(w[seq[i][0]]):
        if tmp[j] == seq[i][1]:
            ans12 += 1
        if tmp[j] == seq[i][2]:
            ans13 += 1
    for j in range(w[seq[i][0]], w[seq[i][0]]+w[seq[i][1]]):
        if tmp[j] == seq[i][2]:
            ans2 += 1
    for j in range(w[seq[i][0]]+w[seq[i][1]], n):
        if tmp[j] == seq[i][1]:
            ans3 += 1
    answer = min(answer, ans12+ans13+max(ans2, ans3))
print(answer)