[Python] 13413번 오셀로 재배치

✏️ 문제

 

문제 파악

작업은 두 가지가 있다.

1. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
2. 말 1개를 들어 뒤집어 놓아 색상을 변경한다.

 

나는 다음과 같이 풀었다. 

if 같은 위치에 있는 문자가 다르다면
	if 처음이라면
		save 변수 = 초기 상태 문자열의 해당 문자를 저장
	else 처음이 아니라면
		2번 작업을 해야 하므로 작업 횟수 +1 
		save 변수 초기화
else 같은 위치에 있는 문자가 같다면
	if 같은 데 save 변수에 저장되어 있는 값이 있다면
		1번 작업을 해야 하므로 작업 횟수 +1 
		save 변수 초기화

근데 자꾸 틀렸다고 나와서ㅠ 결국 못풀었다.. 반례가 뭘까...,.,.?

다른 분들 푼 걸 보니 다른 수가 많은 문자의 개수가 정답이 된다는 점을 가지고 푸셨었다.

 

알고리즘

• 그리디 알고리즘
• 문자열

 

코드

• 내가 못 푼 코드

t = int(input())

for i in range(t):
  n = int(input())
  start = list(map(str, input()))
  target = list(map(str, input()))
  number = 0
  save = ''

  for j in range(n):
    if start[j] != target[j]:
      if save == '':
        save = start[j]
      else: 
        number += 1
        save = ''
    else:
      if save != '':
        number += 1
        save = ''
  
  print(number)

• 정답 코드

t = int(input())

for i in range(t):
  n = int(input())
  start = list(map(str, input()))
  target = list(map(str, input()))
  save = []

  for j in range(n):
    if start[j] != target[j]:
      save.append(start[j])

  if save.count("B") >= save.count("W"):
    print(save.count("B"))
  elif save.count("B") < save.count("W"):
    print(save.count("W"))
  else:
    print(0)