[그리디 알고리즘 Lv.02] 19564번 반복 (Python)

1. 문제

19564번 반복

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

 

muse는 네이버 카페에 글을 올리려고 한다. 하지만 키보드가 고장나서, 어떤 키를 누르든 abcdefghijklmnopqrstuvwxyz가 입력된다!

muse는 글을 올리고 싶지만, 원하는 글을 쓰기 위해서는 아래와 같은 작업을 해야 한다.

1. abcdefghijklmnopqrstuvwxyz를 K번 반복해서 입력한다.
2. 원하는 글자를 마우스로 지워, 최종 글을 완성한다.

muse는 많은 글자를 지우는 일이 귀찮기 때문에, K를 최소화하려 한다. muse가 원하는 글을 입력하려면 abcdefghijklmnopqrstuvwxyz를 몇 번 입력해야 하는지 구해 주자.

 

 

2. 문제 포인트

• a-z까지 무조건 입력
  • n번째 글자가 n+1번째 글자보다 앞에(영어 알파벳 순) 있으면 한번입력으로 2개 이상의 글자를 완성 할 수 있음
• a-z 입력 횟수 구하기

 

3. 접근법

• 입력해야할 글자(input)를 ord()로 아스키 코드로 변환
• n번째 글자와 n+1번째 글자의 아스키 코드를 비교하여 카운트 증가

 

반응형

 

4. 결과 코드

import sys

a = sys.stdin.readline().strip()

# 처음 한번은 무조건 a-z가 입력되어야 한다
cnt = 1

for i in range(len(a)-1):
    # ascii 코드를 이용해 n번 글자와 n+1번 글자 비교
    if  ord(a[i]) >= ord(a[i+1]):
        cnt += 1

print(cnt)

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