[Python] 백준 3048번 문제 풀이 - 개미

문제 링크

https://www.acmicpc.net/problem/3048

문제 이해

우선 문제를 확인하면 첫번째 그룹 ABC, 두번째 그룹 DEF면 초기 상태는 “CBADEF” 입니다.

첫번째 그룹은 A부터 오른쪽으로 이동해서 A / B A / C B A 상태가 되는거고 두번째 그룹은 D부터 왼쪽으로 이동 해서 D / D E / D E F 상태가 됩니다.

어쨌든 시간별로 상태를 보면 다음과 같이 개미의 상태가 변합니다.

• T0 : CBADEF
• T1 : CBDAEF
• T2 : CDBEAF
• T3 : DCEBFA

아이디어

제가 생각한 아이디어는 다음과 같습니다.

• 첫번째 그룹의 개미가 두번째 그룹의 개미를 만난다면 둘의 위치를 바꾸고 인덱스 +2
  • 인덱스를 + 2 해주는 이유는 한번 이동했던 개미는 같은 시간대에 다시 이동하지 않기 때문입니다.
• 아니라면 그냥 인덱스 +1

시간복잡도

그리고 이 문제의 시간복잡도는 알파벳 대문자는 26개이고 중복은 없다고 했기 때문에 최대 26개이고 시간은 50까지니

한번 배열을 순회할 때 26이고 50번 반복하니 26*50 → 1300 밖에 안되어 가능합니다.

코드 구현

그래서 이 아이디어를 코드로 구현하면 다음과 같습니다.

n1, n2 = map(int, input().split())

first_group = list(input())
second_group = list(input())
T = int(input())

first_group.reverse()

ant_status = first_group + second_group

for _ in range(T):
    i = 0
    while i < (n1+n2-1): # 어차피 첫번째 그룹만 세기 때문에 마지막 애가 첫번째 그룹이여도 오른쪽에 아무도 없으니 영향 없음
        if ant_status[i] in first_group and ant_status[i+1] in second_group: # 첫번째 그룹의 개미이고 다음 개미가 두번째 그룹일 때
                # Swap
                ant_status[i], ant_status[i+1] = ant_status[i+1], ant_status[i]
                # 둘의 위치 바꾸고 두칸 뒤로 이동
                i += 2
        else: # 두번째 그룹의 개미일 때
            i += 1

print("".join(ant_status))