[탐색] 전략 추려내기 - ABC 줄세우기

문제

처음에 n명의 사람이 서있는 순서가 A부터 순서대로 알파벳으로 주어지면 알파벳 순으로 줄을 세우려고 합니다. 단, 순서대로 줄을 세우기 위해서는 인접한 두 사람의 위치를 계속 바꾸는 행위만 가능하다고 할 때, 가능한 최소 횟수를 구하세요.

예시

ex)n=4, 

A  D  B  C     =>    A  B  C  D 

출력:2

1. A B D C

2. A B C D 

 

따라서, 2

---

풀이

가장 뒤에 있는 알파벳 부터 하나씩 이동해가며 위치를 맞춰준다. 

감소 for 문으로 가장 뒤에 있는 알파벳 (D) 와 입력받은 배열 (arr)에 해당 알파벳이 존재하는 위치 (index)를 찾는다. 

만약 두 값이 다르다면, 옳은 위치에 도달할 때 까지 하나씩 위치를 바꾸어준다. 

코드

python3

n=int(input())
arr=list(input().split())
alpha=[ chr(i).upper() for i in range(97,97+n)]
cnt=0
for i in range(n-1,0,-1):
    index=arr.index(alpha[i])

    if index!=i:
        for j in range(index,i): #인접한 위치끼리 변경
            arr[j],arr[j+1]=arr[j+1],arr[j]
            #옮긴 횟수 +1
            cnt+=1
print(cnt)