[Coding Study]
프로그래머스 Study 7주차
jjinyeok
2023. 7. 24. 13:00
신규 아이디 추천 - 2021 KAKAO BLIND RECRUITMENT, Level1
def solution(new_id):
new_id = new_id.lower() # 1) 대문자 → 소문자
temp_id = ''
for char in new_id:
if char.isalnum() or char in ['-', '_', '.']:
temp_id += char
new_id = temp_id # 2) 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외 모든 문자 제거
while '..' in new_id:
new_id = new_id.replace('..', '.') # 3) 마침표(.) 2번 이상 연속 부분 → 하나의 마침표(.)
if len(new_id) > 0 and new_id[0] == '.':
new_id = new_id[1:]
if len(new_id) > 0 and new_id[-1] == '.':
new_id = new_id[: -1] # 4) 마침표(.) 처음이나 끝에 위치 → 제거
if new_id == '':
new_id = 'a' # 5) 빈 문자열 → new_id = 'a'
if len(new_id) >= 16:
new_id = new_id[:15] # 6-1) new_id 길이 >= 16 → new_id = 처음 15개 문자 제외 나머지 문자 제거
if new_id[-1] == '.':
new_id = new_id[:-1] # 6-2) 마침표(.)가 new_id의 끝에 위치 → 끝에 마침표(.) 문자 제거
if len(new_id) <= 3:
new_id = new_id + new_id[-1] * (3 - len(new_id)) # 7) 길이 <= 2 → 마지막 문자를 길이가 3까지 반복
return new_id1. 요구하는 규칙에 따라 순서대로 문자열 변경
메뉴 리뉴얼 - 2021 KAKAO BLIND RECRUITMENT, Level2
from itertools import combinations
def solution(orders, course):
answer, course_menu_counts, course_menu_max_count = [], {}, {num: 0 for num in course}
for order in orders:
for num in course:
course_menus = combinations(''.join(sorted(list(order))), num)
for course_menu in course_menus:
course_menu = ''.join(course_menu)
if course_menu not in course_menu_counts:
course_menu_counts[course_menu] = 1
else:
course_menu_counts[course_menu] += 1
if course_menu_max_count[num] < course_menu_counts[course_menu]:
course_menu_max_count[num] = course_menu_counts[course_menu]
for course_menu, count in course_menu_counts.items():
if count == course_menu_max_count[len(course_menu)]:
answer.append(course_menu)
answer.sort()
return answer1. 주문 목록을 코스 개수에 맞춰 조합
1.1) 조합 전 오름차순을 통해 조합 형식 일치
2. 조합된 코스 딕셔너리에 저장 (key: 코스명, value: 코스가 나온 횟수)
3. 코스 개수에 따라 최대로 나온 횟수 딕셔너리에 저장 (key: 코스 길이, value: 길이에 해당하는 코스가 나온 최대 횟수)
4. 모든 코스에 대해 그 길이의 코스의 최대 횟수와 코스가 나온 횟수가 같다면 정답에 추가
순위 검색 - 2021 KAKAO BLIND RECRUITMENT, Level2
from bisect import bisect_left
def solution(infos, queries):
answer = []
applicants = {} # 지원자 (key: 지원조건 조합코드, value: 해당 지원조건 지원자 점수)
for lang in ['-', 'cpp', 'java', 'python']: # 개발언어
for pos in ['-', 'frontend', 'backend']: # 지원직군
for career in ['-', 'junior', 'senior']: #경력구분
for food in ['-', 'chicken', 'pizza']: # 소울푸드
applicants[lang + pos + career + food] = []
for info in infos:
info_lang, info_pos, info_career, info_food, info_score = info.split(' ')
for lang in ['-', info_lang]:
for pos in ['-', info_pos]:
for career in ['-', info_career]:
for food in ['-', info_food]:
applicants[lang + pos + career + food].append(int(info_score))
for comb_code, scores in applicants.items():
scores.sort()
for query in queries:
query_lang, query_pos, query_career, query_food_score = query.split(' and ')
query_food, query_score = query_food_score.split(' ')
query_score = int(query_score)
applicant = applicants[query_lang + query_pos + query_career + query_food]
passer = len(applicant) - bisect_left(applicant, query_score) # bisect_left: 문의점수 미만 점수 개수
answer.append(passer)
return answer1. 지원조건을 조합해 코드를 만들고 해당하는 지원자의 점수를 딕셔너리에 저장
1.1) - 경우 추가하고 - 지원조건은 모든 조건에 해당하므로 모두 저장
2. Binary Search를 위해 지원자 점수 정렬
3. 문의조건에서 문의점수 미만 점수 개수를 bisect_left를 통해 구하고 문의조건 해당 데이터 개수에서 빼 정답 저장
합승 택시 요금 - 2021 KAKAO BLIND RECRUITMENT, Level3
from collections import deque
'''
@param n: 지점의 개수
graph: 지점과 지점 사이 택시요금 2차원 배열
start: 출발지점
end: 목적지점
@return fare: 출발지부터 목적지까지 최소 택시 요금
@desc 다익스트라 알고리즘 사용
'''
def calc_fare(n, graph, start, end):
fares = [987654321 for _ in range(n + 1)] # 출발지로부터 최소 택시 요금
visited = [False for _ in range(n + 1)] # 방문여부
fares[start] = 0
while True:
# 비용 계산 기준 노드 구하기
min_value, node = 987654321, -1
for i in range(1, n + 1):
if fares[i] < min_value and not visited[i]:
min_value, node = fares[i], i
if node == -1: break
# 비용 계산
visited[node] = True
for idx, next_node in enumerate(graph[node]):
if next_node != -1 and fares[idx] > fares[node] + next_node:
fares[idx] = fares[node] + next_node
return fares[end]
'''
@param n: 지점의 개수
s: 출발지점
a: A의 도착지점
b: B의 도착지점
fares: 지점 사이의 택시요금 ([지점1, 지점2, 택시요금]) 리스트
'''
def solution(n, s, a, b, fares):
answers = []
graph = [[-1 for _ in range(n + 1)] for _ in range(n + 1)]
for node_1, node_2, fare in fares:
graph[node_1][node_2], graph[node_2][node_1] = fare, fare
# case1) 경유지까지 합승하는 경우
for waypoint in range(1, n + 1):
s_to_waypoint = calc_fare(n, graph, s, waypoint)
waypoint_to_a = calc_fare(n, graph, waypoint, a)
waypoint_to_b = calc_fare(n, graph, waypoint, b)
answers.append(s_to_waypoint + waypoint_to_a + waypoint_to_b)
# case2) 합승하지 않고 각자 탐승하는 경우
s_to_a = calc_fare(n, graph, s, a)
s_to_b = calc_fare(n, graph, s, b)
answers.append(s_to_a + s_to_b)
return min(answers)1. 2차원 배열을 통해 그래프를 작성
2. 합승하는 경우와 합승하지 않는 경우 2가지 존재
2.1) 합승하는 경우: s → (중간지점), (중간지점) → a, (중간지점) → b 경로의 최저택시요금 계산
2.2) 합승하지 않는 경우: s → a, s → b 경로의 최저택시요금 계산
3. 택시요금을 최단경로로 하는 다익스트라 알고리즘 적용
4. 모든 경우 중 가장 적은 최저택시요금을 정답 저장
광고 삽입 - 2021 KAKAO BLIND RECRUITMENT, Level3
'''
@param time: HH:MM:SS 형식 시간 문자열
@return num: 초로 환산
'''
def time_to_num(time):
hh, mm, ss = map(int, time.split(':'))
num = hh * 60 * 60 + mm * 60 + ss
return num
'''
@param num: 초
@return time: HH:MM:SS 형식 시간 문자열로 환산
'''
def num_to_time(num):
hh, mm, ss = str(num // 3600), str((num % 3600) // 60), str((num % 3600) % 60)
time = '0' * (2 - len(hh)) + hh + ':' + '0' * (2 - len(mm)) + mm + ':' + '0' * (2 - len(ss)) + ss
return time
def solution(play_time, adv_time, logs):
play_time, adv_time = time_to_num(play_time), time_to_num(adv_time)
play = [0 for _ in range(play_time + 1)]
for log in logs:
start_time, end_time = log.split('-')
start_time, end_time = time_to_num(start_time), time_to_num(end_time)
play[start_time] += 1
play[end_time] -= 1
for idx in range(1, play_time):
play[idx] += play[idx - 1]
for idx in range(1, play_time):
play[idx] += play[idx - 1]
max_watcher, answer = -1, 0
for idx in range(adv_time - 1, play_time):
watcher = play[idx] - play[idx - adv_time]
if max_watcher < watcher:
max_watcher, answer = watcher, idx - adv_time + 1
return num_to_time(answer)1. 영상 초에 대해 사람들이 본 횟수를 저장하는 리스트 생성
1.1) 시간 단축을 위해 누적합 사용
2. 누적으로 본 횟수를 저장하는 리스트 생성
2.1) k초에서 광고시간(초) 동안 누적된 사람들이 본 횟수를 구하기 위해 k초 - 광고시간(초) = 광고시간동안 누적된 사람들이 본 횟수
2.2) 앞선 누적합 다시 사용
3. 이를 사용해 광고 동안 가장 누적된 횟수가 많은 구간의 시작 시간 정답 저장