알고리즘 스터디 1주차
백준의 단계별 풀어보기에서 문자열 사용하기 를 풀어보았습니다.
파이썬으로 백준 알고리즘 문제를 처음 풀어보았는데,
문자열 반환의 경우 return 을 해주면 따옴표(‘’) 까지 인식 해 틀렸다고 나왔습니다.
return 대신 print 를 해 주면 정상적으로 작동하는 것을 알 수 있었습니다.
1157 단어공부
import collections
def problem_1157(input_string):
# 대소문자 구분을 하지 않으므로 upper case 로 변경
input_string = input_string.upper()
# input 에 대해 count
cnt = collections.Counter(list(input_string))
# count 횟수를 key 로 갖는 딕셔너리 생성
d = dict([(value, []) for value in cnt.values()])
for key, value in cnt.items():
d[value].append(key)
# 가장 많은 count 횟수의 문자가 한개 이상이면 ? 반환
if len(d[max(d.keys())]) > 1:
print '?'
else:
print d[max(d.keys())][0]
my_input = input()
problem_1157(my_input)
문자의 갯수를 Counter 함수를 이용해 세면 간단하게 풀 수 있는 문제입니다.
생각해볼 점은 Counter의 시간복잡도인데, 단순 dictionary 생성이므로 O(n) 을 넘지 않는 것으로 보입니다.
10809 알파벳찾기
def problem_10809(input_string):
lower_case = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p',
'q','r','s','t','u','v','w','x','y','z']
input_list = list(input_string)
rtn = []
# 각 lower case 에 대해
for l in lower_case:
temp = []
# input의 글자를 하나씩 검색
for i in input_string:
# 일치하는 것이 있으면 문자 내 인덱스를 temp 배열에 저장
if l == i:
temp.append(input_list.index(i))
# 처음 등장하는 위치를 출력해야 하므로 배열의 첫번째 원소를 rtn 에 저장
if len(temp) > 0:
rtn.append(temp[0])
# 등장하는 것이 없으면 -1 를 rtn 에 저장
else:
rtn.append(-1)
# 각 lower case 에 대해 반환된 결과를 문자열 형태로 출력
print(' '.join(map(str, rtn)))
my_input = input()
problem_10809(my_input)
주어진 문자열에 대한 인덱스를 계산하기만 하면 되는 문제입니다.
파이썬에는 list.index(element) 라는 기본 함수가 있어 index 를 구하는 데에 사용했습니다.
1316 그룹 단어 체커
def group_checker(input_word):
# input_word 가 그룹단어인지 아닌지 알려주기 위한 flag ( 1 : 그룹단어가 아님)
flag = 0
input_list = list(input_word)
# 단어의 중복없는 철자를 key값으로 가지는 dict 생성
d = dict([(value, []) for value in list(set(input_list))])
idx = 0
# 각 단어의 철자를 돌면서
for idx, val in enumerate(input_list):
d[val].append(idx)
# 철자에 대한 인덱스들을 검사
if len(d[val]) > 1:
# 전에 추가된 인덱스와 현재 추가된 인덱스가 연속이 아니면 flag 를 바꿔주고 break
if d[val][-1] != d[val][-2] + 1:
flag = 1
break
return flag
def problem_1316(input_num):
cnt = 0
# input_num 만큼 input 을 받으며 group_checker 함수를 실행
for n in range(int(input_num)):
cnt = cnt + group_checker(input())
print(int(input_num) - cnt)
my_num = input()
problem_1316(my_num)
앞의 두 문제보다 조금 난이도가 있는 문제였습니다.
단순 count 나 index 문제가 아니라, 연속된 문자열인지 체크할 수 있는지 물어보는 문제입니다.
연속된 문자열인지 확인 하기 위해, 각 철자에 대한 index 를 셀 때 직전 index 와 비교해주었습니다.
파이썬에서 list 에 대해 index 와 value 둘을 동시에 접근할 수 있는 enumerate 함수를 사용했습니다.
2941 크로아티아 알파벳
def problem_2941(input_string):
cro = ['c=','c-','z=','dz=','d-','lj','nj','s=']
# 크로아티아 문자로 변경된 알파벳들을 길이순으로 소팅
sorted_cro = sorted(cro, key = len, reverse=True)
input_len = len(input_string)
# while 문의 종료를 위한 변수
cnt = 0
# 알파벳의 수를 세기 위한 변수
rtn = 0
while (cnt < input_len):
for k in sorted_cro:
# 크로아티아 문자로 변경된 알파벳을 찾은 경우 rtn++ 해주고 해당 문자열을 공백으로 변환
if k in input_string:
rtn = rtn + 1
input_string = input_string.replace(k, ' ', 1)
cnt = cnt+1
# 크로아티아 문자로 변경하고 남은 알파벳들의 길이를 더해 반환
input_string = input_string.replace(' ','')
rtn = rtn + len(input_string)
print(rtn)
my_input = input()
problem_2941(my_input)
네 문제 중 가장 난이도가 있는 문제였습니다.
주의해야 할 점은 크로아티아 문자로 변경된 알파벳들의 길이가 다르다는 점입니다.
cro 배열을 소팅하지 않고 탐색하게 되면, dz= 보다 z= 를 먼저 탐색해 문제가 생길 수도 있습니다.
탐색 결과 문자열에 존재하면 replace 로 해당 문자열을 지워버리기 때문입니다.
존재하는 문자열을 replace로 지우고 크로아티아 문자 외의 것들은 일반 알파벳으로 취급해 길이를 세주었습니다.