[최대 공약 문자열]
def solution(s1, s2):
if len(s1)>=len(s2): # word1에 더 긴 문자열 저장
word1, word2 = s1,s2
else:
word1, word2 = s2,s1
s3 = "" # 찾고자 하는 s3 초기화
for i in range(len(word2),0,-1): # word2 전체 문자열 부터 해서 뒤부터 한칸 씩 줄여가며 word1의 시작 문자열인지 체크
if word1.startswith(word2[:i]):
s3 = word2[:i]
break
return s3
startswith 함수가 뭔지 알 수 있었다. ( 쉽게 검사가 되더라 )
endswith 라는 함수도 있다.
완전한 코드는 아니다. 왜냐면 구한 s3가 word1과 word2에 대한 반복이 되는지는 검사하지 않았기 때문.
그러나 감안하여도 효율성에서도 그렇고 우수한 코드이다.
반면에 다음은 내가 작성한 코드이다.
반복문이 많이 들어간다..
def solution(s1, s2):
best_ans = ''
if len(s1) < len(s2):
s1, s2 = s2, s1
for i in range(1,len(s2)+1):
j=0
k=0
while k+i <= len(s2):
while j+i <= len(s2):
A = s1[k:k+i]
B = s2[j:j+i]
if A == B:
ans = B
if B*(len(s1)//len(B))==s1 and B*(len(s2)//len(B))==s2:
if len(best_ans) < len(ans):
best_ans = ans
j += 1
k+=1
return best_ans
[형식다른 중복된 연락처 제거 후, 동명이인 찾기]
- 연락처 형식 : 01012345678, 010-1234-0678, 010 1234 5678
def solution(address_book):
names = []
for i in address_book:
names.append(i[0])
numbers = []
for i in address_book:
tmp = i[1].replace('-','').replace(' ', '') # replace 함수로 간단히 형식을 정리한다.
numbers.append(tmp)
address_dict = {i:[] for i in names} # name을 키로 딕셔너리 생성, value는 리스트로 초기화
for i in range(len(address_book)):
address_dict[names[i]].append(numbers[i]) # value에다가 전화번호 추가
same_name = []
for i in address_dict.values(): # name에 해당하는 전화번호 리스트를 집합으로 바꾼 뒤 숫자를 셈
tmp = set(i)
same_name.append(len(tmp))
answer = [i for i in same_name if i >= 2]
return sum(answer)
반면에 내가 짠 코드는 dict을 안써서 효율성에서 점수가 낮았다.
그리고 replace 쓰면 간단한걸 굳이 split 써서 붙이는걸 번거롭게 반복하였다.
def solution(address_book):
for i in range(len(address_book)):
# 형태 1
address_book[i][1] = address_book[i][1].split('-')
address_book[i][1] = ''.join(address_book[i][1])
# 형태 2
address_book[i][1] = address_book[i][1].split()
address_book[i][1] = ''.join(address_book[i][1])
address_book[i] = tuple(address_book[i])
# 중복 제거
address_book = set(address_book)
address_book = list(address_book)
# 이름만 따로 담아서
name_book = [address_book[i][0] for i in range(len(address_book))]
temp = list(set(name_book)) # 이름 중복 제거
ans = 0
for name in temp:
cnt = name_book.count(name)
if cnt > 1 :
ans += cnt
return ans
위에서 배운 교훈들을 바탕으로 다음과 같이 코드 수정
def solution(address_book):
names = []
for i in range(len(address_book)):
# 이름을 담는 리스트를 만듬
names.append(address_book[i][0])
# 전화번호 형태 통일
address_book[i][1] = address_book[i][1].replace('-','').replace(' ','')
# 집합으로 만들어주기 위해 튜플 사용
address_book[i] = tuple(address_book[i])
# 중복 제거
address_book = set(address_book)
address_book = list(address_book)
# 이름도 중복 제거 ( 키 값으로 쓸 꺼 )
names = set(names)
# 이름을 키값으로, value는 0을 갖는 dic 생성
dic = {name : 0 for name in names}
# 같은 이름이 등장하면 1씩 더함
for i in range(len(address_book)):
dic[address_book[i][0]] +=1
ans = 0
for cnt in dic.values():
if cnt > 1 :
ans += cnt
return ans
[숫자 배열이 주어졌을 때, 몇개의 숫자를 더하면 0이 되는지 찾는 문제]
from itertools import combinations
def solution(nums):
plus = []
minus = []
for i in nums:
if i>0:
plus.append(i)
elif i<0:
minus.append(-i)
else:
return 1 # 배열 중 0이 있다면, 답은 1개
plus = sorted(plus)
minus = sorted(minus)
# 2개 확인
for i in plus:
if i in minus:
return 2
# 3개 확인
# 조합으로 plus 중에 2개 골라내고, minus에서 한 개 골라냄
temp = list(combinations(plus, 2))
for i in temp:
if sum(i) in minus:
return 3
# 조합으로 minus 중에 2개 골라내고, plus에서 한 개 골라냄
temp = list(combinations(minus, 2))
for i in temp:
if sum(i) in plus:
return 3
답이 4일 때의 경우는 체크 안한 코드 이지만 테스트 케이스의 한계 탓인지 정답으로 처리되었다. (민수님 코드)
내 문제는 combination을 쓸 생각을 아예 안했다는 것.
브루트포스 임에도 combination을 쓰면 적어도 중복 없이 다 해보니 시간을 꽤 많이 절약할 수 있다.
🍉 깨달은 점 및 정리
1. 문자열 일치여부 검사할 때, startswith나 endswith 같은 함수 떠올리면 좋다.
for i in range(len(word2),0,-1):
if word1.startswith(word2[:i]):
s3 = word2[:i]
2. replace 함수 쓰면 문자열에서 필요없는 부분 다음과 같이 쉽게 소거 가능하다.
address_book[i][1].replace('-','').replace(' ','')
3. 딕셔너리 활용!!!! 진짜 꼭 해야한다.
dic = {name : 0 for name in names}
for i in range(len(address_book)):
dic[address_book[i][0]] +=1
4. combination을 잘 활용하자.
# 조합으로 plus 중에 2개 골라내고, minus에서 한 개 골라냄
temp = list(combinations(plus, 2))
for i in temp:
if sum(i) in minus:
return 3
'코딩테스트' 카테고리의 다른 글
[ 백준 19238 ] 스타트 택시 (0) | 2024.05.03 |
---|---|
[백준 16236] 아기 상어 (2) | 2024.05.03 |
[백준 3343] 장미 (0) | 2024.05.02 |
[제로베이스] 코테 3회차 영화보기 ( 다이나믹 프로그래밍 ) (0) | 2022.07.23 |
[제로베이스] 5월 10일 코딩 테스트 연습 리뷰 (0) | 2022.05.11 |