[Python] 백준 13413번 : 오셀로 재배치

출처 : www.acmicpc.net/problem/13413

13413번: 오셀로 재배치

알고리즘

그리디 문제이다.

시작문자열과, 끝 문자열일 비교하여 틀린 부분만 집어넣고 정렬하여, 비교하자.

색이 일치했으면 나중에 위치를 바꿀 놈이 나온다는 의미이므로 +0.5

색이 일치하지 않는다면 뒤집었어야 하는 놈이므로 1을 더하자.

이 풀이방식을 떠올리기 쉽지 않은 문제이다.

 

코드

def main():
    cases = int(input())
    for _ in range(cases):
        length = int(input())
        start = str(input())
        end = str(input())
        s_wrong = []
        e_wrong = []
        for i in range(length):
            if start[i] != end[i]:
                s_wrong.append(start[i])
                e_wrong.append(end[i])
        s_wrong.sort()
        e_wrong.sort()

        answer = 0
        for j in range(len(s_wrong)):
            if s_wrong[j] == e_wrong[j]:
                answer += 0.5
            else:
                answer += 1
        print(int(answer))


if __name__ == '__main__':
    main()