[백준] 소수 단어(python)

 

2153번: 소수 단어

TL;DR

• 수학(Mathematics)
• 소수(Prime number)

문제 요약

1. a ~ z까지는 1 ~ 26, A ~ Z까지는 27로 대응된다.
2. 이 때, 주어진 문자열을 이루고 있는 각 문자의 합이 소수인지 아닌지 판별하는 프로그램을 작성하라.

 

- 주어진 문자열을 구성하고 있는 알파벳들이 의미하는 숫자를 파악한 후 그 합을 더해 소수 판정을 하면 되는 문제이다.

입출력 형태

[그림 1] 입출력 예시

 

예시 1 :: 주어진 문자열 'UFRN'의 각 문자의 합은 163으로, 이는 소수이다.

예시 2 :: 주어진 문자열 'contest'의 각 문자의 합은 96으로, 이는 소수가 아니다.

풀이

문자를 숫자로 바꾸는 문제에서는 보통 해당 문자의 아스키(ASCII) 값을 이용하는 경우가 많다. C언어와 같은 언어들에서는 문자를 숫자로 변환할 경우 해당 문자에 해당하는 아스키 값을 얻을 수 있지만 python에서는 문자를 숫자로 변환할 경우 'ValueError'가 발생한다.

파이썬에서 문자를 숫자로 바꾸기 위해서는 ord() 메소드를 써주면 된다. 알고 싶은 문자를 인자로 주면 해당 문자의 아스키 값을 반환한다. a의 값은 97이고, A의 값은 65이다. 원래의 아스키 값에서 소문자는 96만큼, 대문자는 38을 빼주면 문제에서 할당된 값으로 변환할 수 있다. 이를 사용해서 주어진 문자열을 숫자들의 합으로 표현할 수 있다.

import sys
INPUT = sys.stdin.readline

word = sum([ord(c) - 96 if c.islower() else ord(c) - 38 for c in INPUT()[:-1]])
for i in range(2, int(word ** .5) + 1):
  if word % i == 0:
    print('It is not a prime word.')
    sys.exit()
print('It is a prime word.')

 

입력 받은 문자열에 대해 문자가 소문자일 경우에는 96을 빼고, 그렇지 않은 경우에는 38을 빼도록 하여 리스트를 만들고 그 합을 구했다. 리스트 컴프리헨션(List comprehension)을 통해 한 줄로 표현할 수 있다.

 

문자열의 합을 알아냈다면 그 다음은 소수 판정이다. 소수는 1과 자기 자신 외에는 나눠지지 않는 수를 의미한다. 2부터 합을 제곱근한 수의 1을 더한만큼 반복문을 진행하며 word가 나누어 떨어지는 지 확인한다. 이는 소수의 특징으로 소수라면 제곱근한 수까지만 판별하면 나머지는 확인할 필요가 없다. 이 문제의 경우 int(word ** .5) + 1 구문을 그냥 word로 바꾸어줘도 문제 없겠지만 시간복잡도 제한이 걸린 문제에서는 시간 초과 문제가 발생할 수 있다. 소수 판정을 진행한 후 문제가 없다면 소수임을 출력하고, 그렇지 않다면 소수가 아니라는 문장을 출력한 후 프로그램을 종료한다.