알고리즘 3일차
7번 단어공부
입력받은 알파벳 중에서 가장 많이 사용된 단어를 대문자로 반환하는 문제이다. 이때 가장 많이 사용된 단어가 여러개로 중복된다면 물음표를 출력한다.
풀이
-
참고로 알고리즘 강의에서 배웠던 것처럼 알파벳을 숫자로 변환하는 아스키코드 개념을 활용하여, 알파벳을 숫자로 변환하는 함수인 ord() 와, 다시 알파벳으로 변환해주는 chr() 함수를 활용한다.
-
먼저 입력 받은 값을 소문자로 변환(lower()) 해준 뒤, 알파벳 갯수를 저장할 리스트를 만들어준다.
alpha_check_list = [0] * 26 # 알파벳 26글자-
소문자로 변환된 입력값의 알파벳을 하나씩 돌면서 문자인지 확인하고 아스키코드를 활용하여 저장할 인덱스 값을 특정짓는다. 이후 해당 인덱스를 1씩 추가한다.
-
완성된 알파벳 갯수 체크 리스트에서 가장 많이 나온 숫자를 찾고 해당 인덱스에 해당하는 문자를 다시 변환해주면 되는데, 이때 최대값이 중복된 경우가 있을 수 있기 때문에 체크리스트에서 최대값을 가지는 인덱스 값을 모두 저장한다.
index_num = []
for i in range(len(alpha_check_list)):
if alpha_check_list[i] == max_count_alpha: # 가장 자주 나온 알파벳 갯수가 들어 있는 ind 값 저장
index_num.append(i)-
그리고 그 인덱스를 저장한 리스트의 길이가 1이라면 최대값 중복이 없다는 의미이므로 해당 인덱스의 문자를 반환해준다.
-
1개가 아니라면 중복이므로 '?'를 반환해 준다.
포인트
- 알파벳 체크리스트를 만들고 아스키코드 변환 방법을 잘 숙지 해야한다.
- 최대값이 중복되었을 때 어떻게 처리할지에 관해 고민해야한다. (더 좋은 코드들이 있을 테니, 찾아봐야함)
8번 크로아티아 알파벳
처음에는 어떻게 접근해야할지 감이 오지 않는 문제였다. 해설을 참조했는데 생각보다 단순한 풀이다.
크로아티아 문자 샘플을 리스트로 저장한 후 입력받은 문자와 대조하여 크로아티아 문자를 한가지 문자로 치환하는 것이 포인트이다. 크로아티아 문자는 여러개의 단어나 기호로 이루어져 있어서 문자 갯수를 셈하기 위해서는 하나의 문자로 통일 시킨 후 길이를 구해야했다.
풀이
cro_alpha_sample = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z=']
cro_alpha = input()
for alpha in cro_alpha_sample:
if alpha in cro_alpha:
cro_alpha = cro_alpha.replace(alpha, '*') # 샘플 문자가 입력값 안에 있으면 * 로 치환해서 남은 글자의 갯수를 셈
print(len(cro_alpha))- 여기서 처음 배운 개념이 replace !!
- replace를 사용하면 지정한 문자를 새롭게 지정한 문자로 대체한다.
9번 그룹 단어 체커
문자가 연속해서 중복으로 나오거나 그 뒤로 해당 문자가 다시 나오지 않는 조건일때 그룹단어라고 정의하고 해당 단어의 갯수를 입력받은 데이터 중에서 골라서 개수를 출력하는 문제이다.
풀이
-
나는 처음에 위에 크로아티아 문자에서 아이디어를 얻어서 replace 함수를 사용해 풀려고 했었지만 하나의 문자를 특정하는 순간 연속된 문자 이외에도 떨어져 있던 문자까지 모두 바뀌게 되어 오답이 되었다.
-
이후 문자 처음부터 앞 뒤로 비교하여 해당 문자가 같으면 앞에 있던 문자를 '' 공백처리 하려고 하였으나 문자열 상태에서 바꿔버리니 여러종류의 에러가 발생했다.
- 자료형이 맞지 않다.
- 참조 범위를 벗어난다.
-
그래서 처음부터 입력받는 값을 리스트 형태로 가져왔고 해당 리스트의 값을 '' 처리한 후 새로운 단어라는 변수에 바뀐 리스트를 모아 문자열로 만들었다.
word = list(input()) # 함수가 불리면 단어로 값을 받음
for i in range(len(word)-1):
if word[i] == word[i+1]: # 단어 앞 뒤로 비교하면서 같은 단어면
word[i] = '' # 해당 자리를 공백 처리 >> 이거할때 그냥 문자열 상태면 에러(자료형 안 맞다는 것, 참조 범위 벗어난다는 것)나서 리스트로 만들어서 공백으로 바꾸고
new_word = ''.join(word) # 문자열인 리스트 인자들을 모아서 문자열로 합쳐달라는 뜻- 이 작업 이후에도 단어에 중복된 문자가 있다면 해당 문자는 그룹단어가 아니므로 새 단어에서 문자를 하나씩 꺼내 해당 문자가 단어에 있다면 갯수를 카운트라하는 함수를 사용하였다. 이때 count()라는 함수를 처음 사용해보았다.
alpha_count = 0 # 새로 만들어진 앞 뒤 중복이 제외된 단어 상태에서 또 중복 글자가 있는 지 확인
for alpha in new_word:
alpha_count += new_word.count(alpha) # 해당 알파벳이 문자 안에 있는 만큼 계수하라는 뜻- 그리고 이 갯수가 해당 문자열의 길이보다 길다면 중복된 숫자가 있었다는 의미 이므로 False를 반환하고 중복 없이 문자열 길이와 같다면 True를 반환하여 반환된 True 값만큼 갯수를 출력하는 것으로 풀이했다.
count = 0
for i in range(n): # 받는 n 만큼 반복문을 돌려서
if check_word() is True: # 조건에 맞는 단어면 count 해라.
count += 1
포인트
- 처음에 input 받을 갯수를 입력받고 나면 그만큼 반복문을 실행시켜서 함수를 실행하라는 저 개념을 배울 수 있었다.
10번 설탕 배달
N kg의 설탕을 입력받았을 때, 3kg, 5kg 의 설탕 자루를 최소한의 횟수로 정확하게 배달하는 횟수를 계산하는 문제이다.
풀이
- 예를 들어 10kg 일때 최대로 많이 움직이는 것은 모두 3kg으로 배달하는 것이기 때문에 배달 횟수 가능 범위를 N // 3 + 1로 잡아서 시도해 보았다. 즉, 3kg 을 최소 몇 자루 부터 있어야 나머지를 전부 5kg 으로 배송 가능한지 알아보려는 방향이다.
index = N // 3 + 1 # 최대 이동 횟수 범위
sum_list = []
for i in range(index): # 이동 횟수 시도
mid = 3 * i # 3kg 가 최소 몇번 필요할지
if (N - mid) % 5 == 0: # 즉, 처음 i 가 0 일때는 5kg로 전부 배송 가능하다는 의미
x = i # 이렇게 해서 딱 떨어지는 수가 나오면 x 는 i (3kg 횟수)
y = (N - mid) // 5 # 5kg 횟수
sum_list.append(x + y) # 딱 맞게 배송가능한 횟수를 리스트로 저장- 만약 이 리스트의 길이가 하나도 없다면 딱 맞아 떨어지는 배송 횟수가 없다는 뜻이므로 -1 을 반환한다.
- 배송 횟수가 있다면 가장 작은 횟수를 찾아서 반환해준다.
if len(sum_list) >= 1:
min_num = sum_list[0]
for num in sum_list:
if num < min_num:
min_num = num
else:
min_num = -1포인트
- 리스트 내용 크기를 비교할 때는 최대든 최소든 하나를 정해서 그 값과 반복문 돌리는 값을 비교해서 해당 조건에 맞는 값을 다시 그 변수에 저장하는 방식으로 해주면 된다.
11번 알파센타우리 (우주선)
우주선이 -1, 0 ,1 만큼 앞 숫자에 더해져서 이동가능 범위가 생기고, 마지막은 꼭 다시 1로 돌아오고 싶을때 최소한으로 움직이는 이동 횟수를 구하라는 문제이다.
(이 문제 풀다가 진짜 열받았다. 휴..)
풀이
-
나는 문제를 등차수열로 접근했다. 마지막에 1로 들어오려면 무조건 최대로 나온 이동가능 수보다 하나 작은 값까지는 앞 뒤로 총 두번 등차수열의 합으로 이동수가 생기기 때문이다.
-
차수가 1이고, 등차가 1일때 숫자 n 까지 등차수열의 합은 n(n+1)/2 이다.
-
이게 해당 두 입력값 사이 움직여야 하는 간격을 c 라고 할때 c = n(n+1)/2 * 2 라고 생각해볼 수 있다.
-
그럼 이때 최대 이동 가능 칸수를 num 이라고 했을 때, 맨 처음에는 num = 1 이고 이후 조건에 따라 1씩 증가하게 된다.
-
그 조건은 한번에 이동가능한 최대 이동 칸수의 제곱을 한 수보다 이동 거리가 같거나 멀고, 최대 이동 칸수 + 1 의 제곱을 한 값 보다 이동 거리가 짧을 때 해당 최대 이동 칸수를 쓸 수 있고
-
그 범위보다 이동해야 하는 거리가 멀다면 최대 이동 칸수를 +1 해주면서 num을 특정해 준다.
-
그리고 그 범위에 이동해야하는 거리가 들어 왔다면 다음 조건으로 최소 이동 횟수를 구해준다.
- c == num ** 2
- c에 해당하는 n 이 num 보다 작거나 같을 때
- n 이 num 보다 클 때
-
그리고 해당 조건에 맞게 규칙을 찾아서 최소 이동 횟수를 구해주고 입력값 만큼 함수를 실행해준다.
import math
ind = int(input())
# 근의 공식
# c 는 나중에 입력값 차
def answer_n(c):
return (-1 + math.sqrt(1+4*c))/2
def find_count(c):
num = 1
while True:
if num ** 2 <= c < (num + 1) ** 2:
break
num += 1
if c == num ** 2:
count = num * 2 - 1
elif answer_n(c) <= num:
count = num * 2
else:
count = num * 2 + 1
return count
for i in range(ind):
a, b = map(int, input().split())
c = b - a
print(find_count(c))- math 를 임포트해서 제곱근을 활용하는 방식으로 했는데 사실 문제가 좀 어려웠다..
- 이동 횟수 규칙을 노트로 써보면서 푸는 것이 가장 눈에 잘 들어오는 풀이법일 것 같다.
포인트
- 이 문제는 규칙을 직접 보면서 해당 정답에 접근하는 것이 가장 직관적인 풀이일 것 같다.
- 다른 사람들의 풀이도 참고해 보아야 겠다.
12번 베르트랑 공준
입력값보다 크고 그 값의 두배보다 작거나 같은 범위 안에 있는 소수 갯수를 구하는 문제이다.
풀이
-
이 문제는 무조건 에라토스테네스의 체를 이용해야 풀린다. 그 외의 방법은 답이 틀리거나 시간초과로 오답처리된다.
-
소수를 구하는 가장 좋은 방법은 에라토스테네스의 체 인 것 같다. 소수 문제라면 무조건 함수를 쓰고 봐야 하지 않을 까 싶을 정도!!
-
에라토스테네스의 체 함수 링크
def prime_list(num):
sieve = [True] * num
m = int(num ** 0.5)
for i in range(2, m + 1): # 해당 범위 i 의 배수를 지우겠다.
if sieve[i] == True:
for j in range(i+i, num, i):
sieve[j] = False
return [i for i in range(2, num) if sieve[i] == True]- num에 해당하는 숫자 앞까지 포함하는 수의 소수가 모두 찾아진다. ex) 11 일때 11 제외
prime_list(11) = [2, 3, 5, 7]-
따라서 입력값을 받아서 0인 경우 반복문을 break 해서 탈출 시키고
-
아니라면 입력값 * 2 + 1 인 수의 소수 리스트를 찾아서 그 리스트 중에 입력값 보다 큰 소수반 반환해 갯수를 출력 해주는 함수를 만들면 된다.
def find_prime(n):
list = prime_list(n * 2 + 1)
count = 0
for i in list:
if i > n:
count += 1
return count
from sys import stdin
while 1:
number = int(stdin.readline())
if number == 0:
break
print(find_prime(number))포인트
- 2 * n 이 아니라 + 1을 해야 한다는 점
- 빠른 계산을 위해 입력값을 input 이 아닌 stdin.readline()으로 받았고, 해당 메서드를 임포트 해왔다.
- while 1: 0 이 아닌 수에 관해서 무한 루프 그래서 실행해보면 숫자 넣으면 무한번 숫자를 입력 받게 되고 값으로 0을 넣어야 프로그램이 종료된다.
