카카오 공채 문제 풀이
Question 1: 비밀 지도
내 풀이
def solution(n: int, arr1: list[int], arr2: list[int]) -> list[str]:
result = []
for i,j in zip(arr1, arr2):
line1, line2 = bin(i)[1:], bin(j)[1:]
line3 = bin(i|j)[2:].replace('1','#').replace('0',' ')
result.append(line3)
return result
결과
Total allocated size: 73.0 KiB time : 0.06866025924682617
풀이: 비트 연산자 OR 이용
def solution(n: int, arr1: list[int], arr2: list[int]) -> list[str]:
maps = []
for i in range(arr1):
maps.append(
bin(arr1[i])|bin(arr2[i])[2:]
.zfill(n)
.replace('1','#')
.replace('0',' ')
)
return maps
중요 내용
- 십진수에서 이진수로의 변환은 bin() 함수를 사용한다.
- or 연산은 이진수로 변경한 상태에서 한다.
Question 2: 다트 게임
Question 3: 캐시
내 풀이
import collections
def solution_3(cacheSize: int, cities: list[int]) -> int:
for city in cities:
cities[1:].append(city.lower())
time = 0
for i in range(len(cities)-cacheSize):
if i == 0:
window = collections.deque(cities[:cacheSize])
time += 5 * cacheSize
if cities[cacheSize+i] in window:
time += 1
else:
time += 5
window.popleft()
window.append(cities[cacheSize+i])
return time
결과
time : 0.0011970996856689453 Total allocated size: 462.3 KiB
풀이 1: 데크를 이용한 LRU 구현
def solution_3_book(cacheSize: int, cities: list[int]) -> int:
elapsed: int = 0
cache = collections.deque(maxlen=cacheSize)
for c in cities:
c = c.lower()
if c in cache:
cache.remove(c)
cache.append(c)
elapsed += 1
else:
cache.append(c)
elapsed += 5
return elapsed
중요 내용
- 데크형 자료는 가장 첫번째 요소 및 마지막 요소를 O(n)에 제거할 수 있다.
- 데크의 maxlen 값은 크기를 지정할 수 있는 파라미터이며, 삽입하는 요소가 최대 크기를 초과할 때는 가장 오래된 항목부터 삭제한다.
Question 4: 셔틀버스
풀이 1: 입력값 전처리 및 대기 시각 처리(재풀이)
def solution_4_book(n:int, t:int, m:int, timetable: list[str]) -> int:
timetable = [
int(time[:2])*60 + int(time[3:])
for time in timetable
]
timetable.sort()
current = 60 * 9
for _ in range(n):
for _ in range(m):
if timetable and timetable[0] <= current:
candidate = timetable.pop(0) - 1
else:
candidate = current
current += t
print(candidate)
h, m = divmod(candidate, 60)
return str(h).zfill(2) + ':' + str(m).zfill(2)
중요 내용
- 먼저 온 사람은 먼저 타므로 버스 출발 시간보다 먼저 온 사람은 pop(0)을 하여 항상 타게 한다.
- 더 이상 탈 사람이 없다면 최대한 늦게 오는 것이 목표이므로 candidate는 현재 버스가 온 시간으로 설정한다.
- zfill()은 문자열 앞에 지정한 숫자만큼 빈 0으로 채운다.
- divdmod()는 몫과 나머지를 구하는 함수이다.
Question 5: 뉴스 클러스터링
내 풀이
def solution_5(str1:str, str2:str) -> int:
list1, list2 = [], []
for i in range(len(str1)-1):
if str1[i:i+2].isalnum():
list1.append(str1[i:i+2].lower())
for i in range(len(str2)-1):
if str2[i:i+2].isalnum():
list2.append(str2[i:i+2].lower())
word_count1 = collections.Counter(list1)
word_count2 = collections.Counter(list2)
common_words = set(list(word_count1)+list(word_count2))
print('common_words', common_words)
intersected_word = 0
unified_word = 0
for word in common_words:
intersected_word += min(word_count1[word], word_count2[word])
unified_word += max(word_count1[word], word_count2[word])
if unified_word == 0:
return 65536
else:
return intersected_word * 65536 / unified_word
- str.isalnum() 은 영문자이면 True, 아니면 False 를 리턴한다.
결과
time : 0.0009751319885253906 Total allocated size: 730.4 KiB
풀이: counter을 이용한 합집합, 교집합, 자카드 유사도 판별
def solution_5_book(str1: str, str2: str) -> int:
# 두 글자씩 끊어서 다중집합 구성
str1s = [
str1[i:i + 2].lower()
for i in range(len(str1) - 1)
if re.findall('[a-z]{2}', str1[i:i + 2].lower())
]
str2s = [
str2[i:i + 2].lower()
for i in range(len(str2) - 1)
if re.findall('[a-z]{2}', str2[i:i + 2].lower())
]
# 교집합 계산
intersection = sum((collections.Counter(str1s) &
collections.Counter(str2s)).values())
# 합집합 계산
union = sum((collections.Counter(str1s) |
collections.Counter(str2s)).values())
# 자카드 유사도 계산
jaccard_sim = 1 if union == 0 else intersection / union
return int(jaccard_sim * 65536)
중요 내용
- re.findall(‘[a-z]{2}’, str1[i:i + 2].lower()) 은 str1[i:i + 2].lower()에서 영문자 2개로 이루어진 문자를 리턴한다.
- Counter() 클래스는 딕셔너리 클래스와 다르다.
- Counter() 클래스 객체끼리는 and, or 연산이 가능한 반면, 딕셔너리 클래스 객체는 불가능하다.
Question 6: 프렌즈4블록
풀이: 3단계 비즈니스 로직 구현
def solution(m, n, board):
board = [list(x) for x in board]
matched = True
while matched:
matched = []
# 일치하는 4개 타일의 인덱스를 찾음
for i in range(m-1):
for j in range(n-1):
if board[i][j] == board[i+1][j] == board[i][j+1] == board[i+1][j+1] != '#':
matched.append([i,j])
# 일치하는 타일을 삭제 ('#'으로 바꿔줌)
for i,j in matched:
board[i][j] = board[i+1][j] = board[i][j+1] = board[i+1][j+1] = '#'
# 삭제한 타일('#'인 타일)위의 타일을 아래로 떨어뜨림
for _ in range(m):
for i in range(m-1):
for j in range(n):
if board[i+1][j] == '#':
board[i+1][j], board[i][j] = board[i][j], '#'
return sum(x.count('#') for x in board)
중요 내용
- 단일 알고리즘으로 풀 수 있는 문제가 아닌 비즈니스 로직을 이용하여 풀 수 있는 문제이다.
- 효율보다는 정확도와 기능에 초점을 맞춘 풀이 방법이다.
Question 7: 추석 트래픽
풀이: 윈도우 범위 내 요청 수 계산
import datetime
def solution(lines: str) -> int:
# 로그의 시작, 종료 시각 저장
combined_logs = []
for log in lines:
logs = log.split(' ')
timestamp = datetime.datetime.strptime(logs[0] + ' ' + logs[1], "%Y-%m-%d %H:%M:%S.%f").timestamp()
combined_logs.append((timestamp, -1))
combined_logs.append((timestamp - float(logs[2][:-1]) + 0.001, 1))
print(combined_logs)
accumulated = 0
max_requests = 1
combined_logs.sort(key=lambda x: x[0])
for i, elem1 in enumerate(combined_logs):
current = accumulated
# 1초 미만 윈도우 범위 요청 수 계산
for elem2 in combined_logs[i:]:
if elem2[0] - elem1[0] > 0.999:
break
if elem2[1] > 0:
current += elem2[1]
max_requests = max(max_requests, current)
accumulated += elem1[1]
return max_requests
중요 내용
- 시작 시간은 1, 종료 시간은 -1로 combined_log에 저장한다
- 로그의 시작과 끝을 비교해가며 둘의 차이가 1보다 작으면 current에 계속 쌓는다.
Comments