파이썬) 개미 - BOJ

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

3048번: 개미

 

이 문제는 좀 어려웠다.

우선 처음 작성한 코드를 보자

 

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

a = input()
a = a[::-1]
# a = ''
b = input()
t = int(input())
dic = {}
dic2 = {}

k = 0

m = min(len(b), len(a))

for i in range(len(a)):
    dic[a[i]] = k
    k += 1

for i in range(len(b)):
    dic2[b[i]] = k
    k += 1

k = 1


while t > 0:
    for i in range(k):
        dic2[b[i]] -= 1

    for i in range(k):
        idx = len(a)-(i+1)

        dic[a[idx]] += 1

    t -= 1
    k += 1
    if k == m+1:
        break

sorted_items = sorted(
    dic.items(), key=lambda x: x[1]) + sorted(dic2.items(), key=lambda x: x[1])

# 정렬된 아이템들에 대해 값을 순서대로 가져와서 문자열로 합치기
# print(sorted_items)

answer = sorted(sorted_items, key=lambda x: x[1])
#
# print(answer)


s = ''.join(item[0] for item in answer)

print(s)
# result_string = ''.join(str(value) for key, value in sorted_items)

# print(result_string)


# print(a, b)

영감을 떠올린 것은

"두 개미 그룹 중 중복된 알파벳은 없다."라는 문장이었다.

그래서 딕셔너리를 사용했다.

k를 0으로 두고 각 두 그룹을 돌면서 초기 자리 값을 구했다.

예를들어 dic = {'A':0, 'B':1...}, dic2={'D':3, 'E':4.....}
그 다음 while문을 돌며 해당되는 자리 수를 -1씩 해버렸다.

테스트 케이스에서 나온 케이스들은 모두 맞았지만 제출하자마자 반례를 맞이하여 실패했다.

도무지 어디서 반례가 나온 것인지 감이 잡히지 않았다.

 

n1, n2 = map(int, input().split())
ant1 = list(input())
ant2 = list(input())
path = ant1[::-1] + ant2
t = int(input())
for _ in range(t):
    for i in range(len(path)-1):
        # 두 개미 그룹이 만났다면 자리를 바꾼다.
        if path[i] in ant1 and path[i+1] in ant2:
            path[i], path[i+1] = path[i+1], path[i]
            # 위치를 바꾼 개미가 선두 개미면 반복을 멈춘다. 
            if path[i+1] == ant1[0]:
                break
print(''.join(path))

 

결국 다른 이의 정답을 참조했다.

 

t만큼 반복을 돌며 ant1과 ant2를 합친 path만큼 반복문을 또 돌아준다.

만약 path[i] 가 ant1에 있고 path[i+1]이 ant2에 있다면,

즉 개미가 서로 만났다면 서로의 위치를 바꿔준다.

예를들어

abc.  def가 있다

path는 abcdef가 있고 i가 2라면

path[i] = c. ( c in ant1)

path[i+1] = d (d in ant2)가 되어 서로 자리를 바꾼다.

 

그 끝에 path[i+1] == ant1[0]는 방금 바꾼 개미가 선두개미면 반복문을 종료하는 조건문이다.

이 조건문은 선두개미가 또 다시 자리를 옮기게하지 않기 위함이다.

위의 예시를 다시 보자.

 

한번 자리를 바꾼 이후 ant1 = abd., ant2 = cef가 된다.

다음 반복문으로는 i =3이 되고

path[i] = c가된다.

path[i+1]은 d가 된다.

 

path[i]는 방금 바꾼 c가되고 path[i+1] 또한 방금 자리를 바꾼 d가된다. 여기서 반례가 발생한다. 방금 바꾼 것임에도 c가 ant2에 있고 d 또한 ant1에 있으니 또 자리를 바꾸게 된다.

 

 

 

---

 

 

이게 실버 4단계라고..? 우습게 봤다가 진짜 큰 코 다쳤다...