1. 문제 1
두 문자열 s1과 s2가 있을때, 두 문자열의 최대 공약문자열 s3를 아래와 같이 정의하자
- 문자열 s3를 반복하여 문자열 s1, s2를 생성 할 수 있다
- 가능한 s3 중에 가장 긴 문자열을 s3라고 한다
- 위 조건을 만족하는 s3가 없으면 빈 문자열을 s3으로 한다
입력 설명
매개변수 s1과 s2가 주어지며, len(S1)과 len(S2)는 최대 100,000이다.
출력 설명
가능한 s3 중 가장 긴 s3을 반환 하시오
매개 변수 형식
s1 = 'abababab'
s2 = 'abab'
반환값 형식
'abab'
나의 풀이
def solution(s1, s2):
if len(s1) < len(s2): #s1의 길이가 짧은경우
for i in range(len(s1)): # s1의 길이 =인덱스 번호
if s1[i] == s2[i]: # 값 확인후 짧은것이 최대공약수 # p: 한자리만 확인 후 리턴하는게 문제
return s1
else:
return [] # 같지 않다면 빈리스트 리턴
elif len(s1) == len(s2): #s1=s2 같은수
for i in range(len(s1)):
if s1[i] == s2[i]:
return s1
else:
return []
elif len(s1) > len(s2): #s2의 길이가 짧은경우
for i in range(len(s2)):
if s1[i] == s2[i]:
return s2
else:
return []-
s1과 s2 중 어느것의 길이가 더 짧은지 모르기 때문에 3가지 경우의 수로 나누어 판단하려고 했다. 둘 중에 길이가 짧은 것의 원소가 길이가 긴것의 원소랑 같으면 짧은 것이 최대 공약수로 return 하면 된다고 생각 했다. 그리하여, 첫번쨰 s1이 짧은경우, 두번쨰 s1,s2가 길이가 같은 경우, 세번째 s1의 길이가 긴경우 나누어서 큰 틀을 짜봤지만,
문제점으로 길이가 짧은 것의 원소를 다 비교해서 같았는데 그 뒤의 원소가 다를 경우에는 길이가 짧은것이 s3가 될 수 없기 때문이다. 그리고 내가 만든 for 실행문은 둘의 첫번쨰 원소만 비교하므로 올바른 정답이 될 수 없다
정답
def solution(s1,s2):
def isdivisor(string,divsior): # 또다른 함수를 만들어줌
n = len(divsior)
if len(string) % n != 0: #str2가 ''인지 확인
return False
while string != '': # str1이 str2로 이루어졌는지 확인
if string[:n] !=divsior:
return False
string = string[n:]
return True
if len(s1)>len(s2): # 길이로 구별, 길이가 긴 문자열 = str1, 길이가 짧은 문자열= str2
str1,str2 = s1,s2
else:
str1,str2 = s2,s1
divisor = str2 # 길이가 짧은 문자열로 나눠줌
m=1
while divisor !='':
if isdivisor(str2,divisor) and isdivisor(str1,divisor):
return divisor # 길이가 짧은 문자로 나눴는데, 그 문자열이 최대공약수가 되는 경우
m+=1
divisor = str2[:len(str2)//m]
return '' # 최대 공약수가 없는 경우print(solution('abcabc','abcabcabc')) #abc
2. 문제 2
민수의 주소록은 리스트로 구성되어 있으며, 리스트의 각 원소는 [친구이름, 전화번호] 로 구성되어 있다. 민수는 친구들의 전화번호를 저장할때 - 기호를 쓰기도 하고 생략하기도 하고, 띄어쓰기로 기재하기도 했다. 010-1234-5678 이라는 전화번호를
- 01012345678
- 010-1234-5678
- 010 1234 5678
의 세가지 방법중 하나로 저장해 두었다. 민수의 주소록은 여러방법으로 저장한 주소록을 모아둔 것이기 때문에, 같은 전화번호를 가진 친구가 여러번 나타날 수 있다. 전화번호가 변경된 친구는 없다고 할때, 민수의 친구중 동명이인의 수를 출력하시오
입력 설명
[친구이름, 전화번호] 로 구성된 길이가 100,000 이하인 리스트
입력 예시
[['kim', '012-423-0044'], ['park', '042-512-4555'], ['choi', '555-523'], ['kim', '444-524'], ['kim', '0124230044']]
출력 예시
2
첫번째 kim과 마지막 kim은 중복된 같은 사람이며, 네번째 kim과 첫번째 kim은 번호만 다를뿐 다른 사람이므로 첫번째(세번째) kim과 네번째 kim이 동명이인이므로 총 2명의 동명이인이 있다고 판별
나의 풀이
리스트 형태이기 때문에, for문을 사용하여 전화번호만 따로 모아서 -,' ' 을 모두 ''로 바꾸어준 리스트를 또 만들어 각각의 핸드폰 번호가 몇번씩 나왔나 세었다. 근데 시간 초과가 걸렸으며, 동명이인의 숫자가 아니라, 중복된 번호만을 세는 함수를 만들었다
def solution(address_book):
arr_new = [] # 전화번호만 따로 모음,
for i in range(len(address_book)):
arr_new.append(address_book[i][1])
list2 = [] # '-',' ' >> ''로 변환함
for i in arr_new:
b = i.replace('-', '').replace(' ', '') # replace 여러조건값 주기
list2.append(b)
print(list2)
cnt = 0 # 각 핸드폰번호가 몇번씩 나왔나 셈
for x in list2:
if list2.count(x) >= 2:
cnt += 1
return cnt정답
def solution(address_book):
book ={} # 딕셔너리 형태로 담음
for name, number in address_book: # key, value 값
number = number.replace('-','').replace(' ','') #뒤의 -,공백은 모두 없애줘서 동일한 전화번호로 만듬
if name not in book:
book[name] = set() # set 함수를 써서 이름 중복을 제거
book[name].add(number) # 딕셔너리 형식으로 묶어짐 #{'kim': {'444444', '123456'}, 'park': {'567888'}, 'choi': {'111111'}}
print(book)
# 동명이인 숫자 구하기
answer = 0
for name in book:
print(book[name])
num = len(book[name])
if num>1: # 동명이인의 수
answer += num
return answer
address_book =[['kim','123-456'],['park','567-888'],['choi','111-111'],['kim','123456'],['kim','444 444']]
print(solution(address_book))- 딕셔너리 타입으로 동명이인을 카운팅한다 (key 값, value값으로 나누며, value 값은 여러개가 저장 될 수 있으며, 중복을 허용하지 않아야 한다)
- 그러므로 value 값에는 중복을 제거하고, {} 형태로 add 해서 받을 수 있는 set() 함수를 사용해야 한다.
