문자열 그리디 연습1 - 최소 횟수로 교환해서 두 문자열 같게 만들기

1. 문제

 

13413번: 오셀로 재배치 (acmicpc.net)

13413번: 오셀로 재배치

 

2. 풀이1

 

문자열의 문자를 바꾸는 방법이 2가지

 

1) B는 W로, W는 B로 뒤집기

 

2) 서로 다른 두 위치의 문자를 교환하기

 

이런 상황에서 두 문자열이 서로 같게 만드는, 최소 횟수로 교환하는 방법을 찾을려면?

 

탐욕적으로 생각해보면 생각보다 간단한 문제다

 

두 문자열을 처음부터 동시에 순회해서, 두 문자가 서로 같다면 그대로 넘어가면 될거고

 

두 문자가 서로 다른 순간에 교환을 해야할거임

 

 

0번째는 W와 W가 같고, 1번째는 B와 B가 같고... 2번째부터 B와 W로 다르니까 여기는 교환을 시도해야함

 

그런데 B를 W로 바꾸는 1) 방법을 해야하나? 아니면, 다른 자리의 W와 교환하는 2) 방법을 해야하나?

 

어느 방법을 시도해야 최소 횟수로 가능할까?

 

당연히 2) 방법을 먼저 시도해야한다.

 

왜냐하면 2) 방법을 시도해서 성공하면, 한번의 시도에 2개의 문자를 서로 같게 만들 수 있으니까 무조건 이득이다

 

근데 현재 2번째 위치에서 서로 다르다고 판단이 되어 2)방법을 시도할려고 한다면... 어느 자리의 W와 교환해야하나?

 

이전의 문자는 서로 같다고 하니 쳐다볼 필요도 없고, 당연히 3번째, 4번째 위치의 문자중 하나랑 교환해야한다.

 

3번째, 4번째가 모두 W라 교환 대상인데, 당연히 3번째랑 교환해야한다.

 

3번째는 대응하는 문자가 B로 서로 다르니까, 2번째 문자랑 교환하면 서로 같아진다.

 

하지만 4번째는 대응하는 문자가 W라 바꾸면 오히려 손해이다

 

from sys import stdin

T = int(stdin.readline())

for _ in range(T):

    n = int(stdin.readline())

    s = list(stdin.readline().rstrip())
    t = list(stdin.readline().rstrip())

    answer = 0
    skip = False
    
    #두 문자열을 처음부터 순회
    for i in range(n):
        
        # 두 문자가 서로 다르다면.. 교환을 시도
        if s[i] != t[i]:
            
            find = False

            if skip == False:
                
                #i+1번째부터, 교환이 가능한지를 검사함
                for j in range(i+1,n):
                    
                    #현재 위치의 문자와 다른 문자여야하며, 대응하는 문자와도 다른 문자여야함
                    if s[i] != s[j] and s[j] != t[j]:
                        
                        #조건에 맞으면 교환하고,
                        s[i],s[j] = s[j],s[i]
                        
                        #시도횟수를 1 증가
                        answer += 1
                        find = True
                        break
            
            #어느 순간 조건에 맞는 문자를 찾지 못했다면,
            if find == False:
                
                #그 뒤로는 절대로 조건에 맞는 문자를 찾을 수 없으니
                #1) 방법만 사용해서 문자를 바꿔야한다.
                skip = True
                answer += 1
                s[i] = t[i]
    
    print(answer)

 

2) 방법을 위해 조건에 맞는 문자를 찾아봤는데, 그런 문자가 없다면, 그 뒤로는 바꿀 수 있는 문자가 존재하지 않으니

 

1) 방법만 시도해야한다. 이를 위해 skip이라는 boolean 변수를 뒀다

 

 

3. 풀이2

 

위 방법은 $O(n^{2}T)$라서 너무 느리다.. n이 10만이라 너무 느림

 

pypy3로 간신히 통과할 정도

 

사실 더 쉽게 생각하면 더 쉽게 풀 수 있는데

 

어차피 두 문자열을 처음부터 순회해서 서로 다른 문자라면 교환을 시도해야한다

 

근데 만약에, 교환을 시도해야하는 대상 문자가 B,B,B밖에 없다면?

 

그러면 서로 다른 위치의 문자랑 교환할 수 없으니 3번해야한다.

 

예를 들어 BBBBBBB를 BWBWBWB로 바꿀려면, 교환을 시도해야하는 대상 문자는 2번째, 4번째, 6번째의 B이다.

 

얘들은 W로 바꿔야하는데, W로 바꿀 수 있는 문자가 없으니 1)방법의 뒤집기만 가능해서 3번 바꿔야한다

 

반대로 교환을 시도해야하는 문자를 조사해보니 W,W,B가 있더라

 

이 경우에 서로 다른 문자를 교환하는 방법이 W와 B로 1쌍이 있고, 뒤집어야하는 방법으로 W 1개가 있어서

 

2번만 교환하면 가능하다

 

예를 들어 WWBB를 BBWB로 바꿀려고 하면, 교환을 시도해야하는 문자는 1번째, 2번째, 3번째 W,W,B이다.

 

그리고 1번과 3번(혹은 2번과 3번)을 교환하고, 2번을 B로 뒤집어서(혹은 1번을 B로 뒤집어서) 2번만에 대상 문자열로 바꿀 수 있다.

 

--------------------------------------------------------------------------------------------

 

오히려 간단하게 생각해보니..

 

길이가 N인 두 문자열을 동시에 순회해서, 서로 다른 문자인 경우에 W인지 B인지를 조사해본다.

 

W이면 W만 들어간 리스트에 넣어준다.

 

B이면 B만 들어간 리스트에 넣어준다.

 

그러면 W 리스트랑 B 리스트에 들어간 W,B는 교환을 시도해야하는 문자이다.

 

이때, 서로 다른 위치의 문자를 교환한다는 의미는, W리스트와 B리스트에서 각각 하나씩 뽑아서 서로 바꿔 주는 것이다.

 

1) 방법으로 뒤집는다는 의미는 각 리스트의 문자를 다른 문자로 바꿔주는 것이다.

 

그런데 2)방법을 먼저 시도해야 무조건 최소 횟수로 대상 문자열로 바꿀 수 있다.

 

2)방법을 시도할 수 있는 방법의 수는 두 W,B리스트에 들어간 문자의 개수의 최솟값만큼 가능하다.

 

그리고 남은 문자는 (두 리스트의 길이의 최댓값) - (두 리스트의 길이의 최솟값) 만큼의 횟수로 1)방법으로 뒤집어야한다.

 

따라서 교환해야하는 최소 횟수는 두 리스트의 길이의 최댓값만큼 교환하면 된다.

 

결국 두 문자열을 순회해서 서로 다른 문자인 경우 W인지 B인지 개수를 세서 더 많은 문자의 개수가 정답이다

 

from sys import stdin

T = int(stdin.readline())

for _ in range(T):

    n = int(stdin.readline())

    s = stdin.readline()
    t = stdin.readline()
    
    W = 0
    B = 0

    for i in range(n):
        
        if s[i] != t[i]:
            
            if s[i] == 'W':
                
                W += 1
            
            else:
                
                B += 1
    
    if W >= B:
        
        print(W)
    
    else:
        
        print(B)