[PS | 한 번에 맞자!] 백준 3048

1. 문제

개미

3048번: 개미

2. 문제 생각
처음에는 규칙을 찾으려고 했다. T가 몇 번일 때 바뀌는 것과 바뀌지 않는 것들이 몇 번인지를 기준으로 찾아서 구현하려고 하였다.

이후 다시 보니 아래의 두 힌트가 명시적으로 N1과 N2가 굉장히 작고 T도 50밖에 되지 않아 빡구현이겠구나 하고 생각하였다.

 

3. 문제 풀이

N,M=map(int,input().split())
A=list(input())
B=list(input())
T=int(input())

start=A[::-1]+B
for _ in range(T):
    flag=False; #바뀜을 확인하는 flag
    for i in range(N+M-1):
        if start[i] in A and start[i+1] in B:
            start[i],start[i+1]=start[i+1],start[i]; 
        # print(start)
            if start[i+1]==A[0]: break
print(*start,sep='')

 

4. 한 번에 풀었는가? X

한번에 풀지 못한 이유는 위의 break문 때문이었다. 
for문에서 swap하는 과정은 사실상 매우 위험하다..! for문 loop문을 돌면서 상태를 바꾸면서 가다보면, 내가 의도한 것과 다르게 구현될 수 있다. 뒤의 상황이 그대로 있다는 보장이 안 서기 때문이다. 
따라서 위의 내용에서는 규칙대로 start[i+1]==A[0]일 때 이 A[0]가 계속해서 뒤로 가지 않도록 하기 위한 break문으로 해결하면 된다.

5. 다른 사람 풀이

위에서 내가 이야기한 상태값을 해결할 수 있는 코드는 아래와 같이 상태를 변경하지 않고 저장해두었다가 이후 한꺼번에 변경하는 방법으로 구현하면 문제가 없다. 

# 개미의 수
N1, N2 = map(int,input().split())
 
# 첫번째 그룹, 두번째 그룹
N1_lst = list(str(input()))
N2_lst = list(str(input()))
 
# 이동 시간
T = int(input())
 
# 방향 통일
N1_lst.reverse()
 
# N1 N2 통합
N_sum = N1_lst + N2_lst
 
for t in range(T):
 
    # swap해야하는 idx 값 저장
    temp = []
 
    for q in range(1,len(N_sum)):
 
        # 왼쪽 방향으로 이동하는 경우만 확인하면 됨
        # <- -> 의 경우는 방향이 서로 달라도 swap할 필요 없음
        if N_sum[q] in N2_lst:
            if N_sum[q-1] in N1_lst:
                temp.append(q)
 
    # swap 해주기
    for w in temp:
        N_sum[w], N_sum[w-1] = N_sum[w-1], N_sum[w]
 
# 결과
res = ''
 
for r in N_sum:
    res += r
 
print(res)