<2022모각코/TIL> [백준/python] 3048 - 개미

n, m = tuple(map(int, input().split()))
input_a = list(input())
a = []
for _ in range(n):
    a.append(input_a.pop())
b = list(input())
t = int(input())
arr = a + b
check = n * '0' + m * '1' + '9'
check_arr = []
target = []

for i in check:
    check_arr.append(i)

for _ in range(t):
    for i in range(n + m):
        if check_arr[i] == '0' and check_arr[i + 1] == '1':
            target.append(i)
    for j in target:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
        check_arr[j], check_arr[j + 1] = check_arr[j + 1], check_arr[j]
    if not target:
        break
    target = []
    
for i in arr:
    print(i, end='')

알고리즘:

1. 일단 첫번째 그룹을 거꾸로 받아서 CBADEF 처럼 arr를 받는다.

2. check_arr 를 0001119로 만든다 (9 는 의미 없음. index 참조 오류 방지)

3. 만약 i번째 arr의 요소가 0이고, 그 다음 요소가 1이라면 target 리스트에 i를 넣는다.

4. target에 든 index의 요소들을 다음 요소들과 바꿔준다. 이 때, check_arr 또한 바꿔준다.

5. 만약 target이 비어있다면 전체 for문을 탈출

6. 그리고 마지막에 target을 다시 비워주어서 큰 for문을 돌개한다.

 

어떻게 풀까 고민하다가 규칙을 발견해서 알고리즘을 작성하였다.

000111

001011

010101

101010

110110

111000 이런식으로 0 다음 1이면 바뀌어야 한다.