[Python] 백준 19564번_반복

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

19564번: 반복

 

• muse는 키보드가 고장나서, 어떤 키를 누르든 abcdefghijklmnopqrstuvwxyz가 입력됨
• 원하는 글을 쓰기 위해서는 아래와 같은 작업을 해야 함
  • 1) abcdefghijklmnopqrstuvwxyz를 K번 반복해서 입력
  • 2) 원하는 글자를 마우스로 지워, 최종 글을 완성
• muse는 많은 글자를 지우는 일이 귀찮기 때문에, K를 최소화하려 함
• muse가 원하는 글을 입력하려면 abcdefghijklmnopqrstuvwxyz를 몇 번 입력해야 하는지 구하기

• 입력
  • muse가 입력하고자 하는 글 S가 주어짐
  • 이 글은 알파벳 소문자만으로 이루어져 있으며, 길이는 L (1≤L≤105)
• 출력
  • K의 최솟값을 출력
• 시간 제한: 1초
• 메모리 제한: 256 MB

 

"""
입출력 예시)

polymath -> 6
"""

 

 

## 의사코드 ##

# k = 1 # 맨 처음 키보드를 눌러야 함

# for i in range(1, len(s)):
#     # 현재 문자가 이전 문자보다 작거나 같은 경우, k+1 
#       -> 같은 문자인 경우에도 +1 해야 함(두번 눌러야 하니까)
#     if s[i] <= s[i-1]: # 현재 문자가 이전 문자보다 사전에서 앞에 있으면
#         k += 1 
#     # 현재 문자가 이전 문자보다 큰 경우, 통과
#      -> 현재 문자가 이전 문자보다 사전에서 뒤에 있는 경우

 

• ex) 'p o l y m a t h'
  • k=1) p y (+ p, y)
  • k=2) p o y (+ o)
  • k=3) p o l y (+ l)
  • k=4) p o l y m t (+ m, t)
  • k=5) p o l y m a t (+ a)
  • k=6) p o l y m a t h (+ h)
  • -> 현재 문자가 이전 문자보다 사전 순에서 뒤에 있으면 k 추가 x
    • => 현재 문자가 이전 문자보다 사전 순에서 앞에 있는 경우에만 k + 1

 

 

 

통과한 코드

s = input()
k = 1 # 맨 처음 키보드를 눌러야 함
for i in range(1, len(s)):
    # 현재 문자가 이전 문자보다 작거나 같은 경우, k+1 
    if s[i] <= s[i-1]: # 현재 문자가 이전 문자보다 사전에서 앞에 있으면
        k += 1
print(k)

-> 현재 문자가 이전 문자보다 사전에서 앞에 있는 경우에만 k+1

 

 

• 문자열 사전순 비교
  • -> 아스키코드 값으로 대소비교 가능

print('o가 p보다 크다:', 'o' > 'p')
print('o는 p보다 작다:', 'o' < 'p')

"""
o가 p보다 크다: False
o는 p보다 작다: True
"""

 

 

 

 

 

참고)

 

https://ddolcat.tistory.com/684

[Python] 파이썬 아스키코드(ASCII) 비교 및 변환 총정리 : ord(), chr(), hex()

 

https://velog.io/@cosmos/boj%EB%B0%B1%EC%A4%80-19564-python

boj/백준-19564-python