[Python] 백준 3048.개미

문제

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

개미가 일렬로 이동할 때, 가장 앞의 개미를 제외한 나머지 개미는 모두 앞에 개미가 한 마리씩 있다. 

서로 반대 방향으로 이동하던 두 개미 그룹이 좁은 길에서 만났을 때, 개미는 어떻게 지나갈까?

최근 연구에 의하면 위와 같은 상황이 벌어지면 개미는 서로를 점프해서 넘어간다고 한다.

즉, 두 그룹이 만났을 때, 1초에 한번씩 개미는 서로를 뛰어 넘는다. (한 개미가 다른 개미를 뛰어 넘고, 다른 개미는 그냥 전진한다고 생각해도 된다)

하지만 모든 개미가 점프를 하는 것은 아니다. 자신의 앞에 반대 방향으로 움직이던 개미가 있는 경우에만 점프를 하게 된다.

첫 번째 그룹이 ABC로 움직이고, 두 번째 그룹의 개미가 DEF순으로 움직인다고 하자. 그럼, 좁은 길에서 만났을 때, 개미의 순서는 CBADEF가 된다. 1초가 지났을 때는 자신의 앞에 반대방향으로 움직이는 개미가 있는 개미는 A와 D다. 따라서, 개미의 순서는 CBDAEF가 된다. 2초가 되었을 때, 자신의 앞에 반대 방향으로 움직이는 개미는 B,D,A,E가 있다. 따라서, 개미의 순서는 CDBEAF가 된다.

T초가 지난 후에 개미의 순서를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 첫 번째 그룹의 개미의 수 N1과 두 번째 그룹의 개미의 수 N2가 주어진다.

다음 두 개 줄에는 첫 번째 그룹과 두 번째 그룹의 개미의 순서가 주어진다. 각 개미는 알파벳 대문자로 표현할 수 있으며, 두 그룹에서 중복되는 알파벳은 없다.

마지막 줄에는 T가 주어진다. (0 ≤ T ≤ 50)

출력

T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다.

---

풀이

처음에는 2차원 배열로 만들어서 0, 1로 방향을 나타내주고... 뭐 그런 식으로 풀려고 했었는데 이게 참... 간단하게 생각하자...라고 다시 문제를 보았다.

 

그리고 맞췄는데, 가장 고민했던 부분은 바꾸고 난 뒤에 그 초에는 추가적으로 바뀐 건 바뀌면 안되는 거였다! 무슨 말이냐면... 

1초만 진행되었을때

이렇게 AD만 바뀌어야 하는데, 위와 같이 0과 1만으로 판단해서 다음 게 자신과 다르면 바꾸기! << 이런 식으로 풀면 초와 상관없이 그냥 끝까지 바꿔버리는 불상사가 생기고 만다.

 

이걸 어떻게 해결할까 하다가...

 

1. for문을 통해서 지금꺼는 -> group에 들어있고, 다음꺼는 <- group으로 들어있음, idx 배열에 전부 추가해주기

2. 전부 추가한 idx 배열을 또 for문으로 돌면서 위치를 바꿔줬다.

3. 이 각각의 두 for문이 끝나면 time 에서 1을 빼고 while문으로 time이 0이 아닐때까지 반복하도록 했다.

 

import sys
input = sys.stdin.readline

n1,n2= map(int, input().split())
g1 = input().strip()
g2 = input().strip()
t = int(input().strip())
result = []

#result에 CBADEF(ex)처럼 넣어주는 코드
for i in range(n1-1, -1, -1):
    result.append(g1[i])
for i in range(n2):
    result.append(g2[i])

while t != 0:
    num = []
    #for문을 통해서 지금꺼는 -> group에 들어있고, 
    #다음꺼는 <- group으로 들어있음, idx 배열에 전부 추가해주기
    for i in range(len(result)-1):
        if result[i] in g1:
            if result[i+1] in g2:
                num.append(i)
    #전부 추가한 idx 배열을 또 for문으로 돌면서 위치를 바꿔줬다.
    for j in num:
        a = result[j+1]
        result[j+1] = result[j]
        result[j] = a
    #이 각각의 두 for문이 끝나면 time 에서 1을 빼고 while문으로 
    #time이 0이 아닐때까지 반복하도록 했다.
    t-=1

print("".join(map(str, result)))

 

코드로 구현하면 위와 같다!

 

시간복잡도

시간복잡도는 ... 최악의 경우 O(t*(n1+n2)*n1)이지 않을까 싶다.