19th KOALA 4주차

휴.. 이번주는 진법변환 문제가 많이 나와서 넘 어려웠다 ...(  ˊ࿁ˋ ) ᐝ

 

그치만 펠린드롬 문제는 풀만 했던 것 같다!! 규칙만 알면 금방 풀리는 문제들이라 재미있었다 (๑˘ω˘ )و “

 

아무튼 오늘 리뷰할 문제는 바로..!!

 

 

 

백준 17502번 : 클레어와 펠린드롬

 

 

어떤 문자열이 주어지는데 중간중간 ?가 섞여있다. 그 문자열은 원래 회문이었지만 지워진 부분을 ?로 설정했다고 한다. ?를 알맞게 소문자로 바꿔서 다시 완전한 회문을 만들어주는 문제다!! ( •̀ ω •́ )✧

 

먼저 이 문제의 조건을 세워보았다..!

 

1. ?는 아무 소문자로 바꾸어도 된다 (가장 만만한 a로 바꾸려한다!!)

2. 앞뒤 대칭을 맞추면 통과된다

3. 방법이 여러 개일때는 아무거나 출력할 수 있다

 

n = int(input())
s = list(input())  

for i in range(n // 2):
    left = s[i]
    right = s[n - 1 - i]

    if left == '?' and right == '?':
        s[i] = s[n - 1 - i] = 'a'
    elif left == '?':
        s[i] = right 
    elif right == '?':
        s[n - 1 - i] = left
    elif left != right:
        print("Not a palindrome") 
        break

if n % 2 == 1 and s[n // 2] == '?':
    s[n // 2] = 'a'

print(''.join(s))

 

전체 코드는 이러하다! 

 

회문은 결국 앞과 뒤가 똑같아야 하므로, 양쪽 끝부터 가운데까지 비교하면서 ?를 채워주면 된다!! 덱(Deque)과 비슷하다고 생각하면 쉬울 것 같다! 이후에는 각각의 케이스에 따라 조건이 나뉜다. 

 

1. left와 right가 모두 ?면 'a'를 넣는다. 

2. 하나만 ?면 상대편 값을 복사한다.

 

마지막으로 길이가 홀수일 때는 가운데도 ?일 수 있으므로 'a'로 채워준다! 

 

파이썬 문자열은 변경이 불가하므로 list로 바꾸어주었고, [::-1]로 뒤집어서 확인하는 방식도 있지만, 이 문제는 직접 채우는게 핵심인 것 같아 이렇게 구현했다 (●ˇ∀ˇ●)

 

 

 

C++이었으면 문자 하나하나 직접 배열로 다뤘어야 해서 조금 번거로웠을 것 같은데, 파이썬은 문자열을 리스트로 바꾸기만 하면 바로 수정할 수 있어서 편하다 헤헤 (〃 ω 〃)  특히 s[i] = s[n-1-i] 이런 식으로 대칭을 그대로 채워넣는 게 파이썬에선 직관적으로 딱 보이는 느낌이라 좋다. 다음 주엔 꼭 더 일찍 풀어야지 진짜루!!! (다짐만 몇 번째임 (･⏠･))