프로그래머스 코딩테스트 고득점 Kit의 문제입니다.
https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit
코딩테스트 연습
기초부터 차근차근, 직접 코드를 작성해 보세요.
programmers.co.kr
문제
https://programmers.co.kr/learn/courses/30/lessons/60062
코딩테스트 연습 - 외벽 점검
레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하
programmers.co.kr
내가 작성한 코드
from itertools import combinations
from bisect import bisect_right, bisect_left
def solution(n, weak, dist):
to_check = len(weak)
weak += [i+n for i in weak]
all_checked = set()
for num_friend, l in enumerate(sorted(dist, reverse=True)):
num_friend += 1
checked = set()
for s_i, s in enumerate(weak):
e = s + l
e_i = bisect_right(weak, e)
checked.add(frozenset(map(lambda x: x % n, weak[s_i:e_i])))
nw_checked = set()
for now in checked:
if len(now) == to_check:
return num_friend
nw_checked.add(now)
for before in all_checked:
nw = now | before
if len(nw) == to_check:
return num_friend
nw_checked.add(nw)
all_checked = nw_checked
return -1
- 원형 큐
- 마지막과 처음이 이어지는 경우를 고려하기 위해 weak를 2배로 만들어줌
- 집합
- 탐색한 모든 weak를 set으로 저장
- 친구가 추가될 때마다 합집합으로 탐색 weak들을 누적하여 확인
- 모든 weak를 탐색하면 종료
다른 사람이 작성한 코드
def solution(n, weak, dist):
W, F = len(weak), len(dist)
repair_lst = [()] # 현재까지 고칠 수 있는 취약점들 저장 (1,2,3)
count = 0 # 투입친구 수
dist.sort(reverse=True) # 움직일 수 있는 거리가 큰 친구 순서대로
# 고칠 수 있는 것들 리스트 작성
for can_move in dist:
repairs = [] # 친구 별 고칠 수 있는 취약점들 저장
count += 1
# 수리 가능한 지점 찾기
for i, wp in enumerate(weak):
start = wp # 각 위크포인트부터 시작
ends = weak[i:] + [n+w for w in weak[:i]] # 시작점 기준 끝 포인트 값 저장
can = [end % n for end in ends if end -
start <= can_move] # 가능한 지점 저장
repairs.append(set(can))
# 수리 가능한 경우 탐색
cand = set()
for r in repairs: # 새친구의 수리가능 지점
for x in repair_lst: # 기존 수리가능 지점
new = r | set(x) # 새로운 수리가능 지점
if len(new) == W: # 모두 수리가능 한 경우 친구 수 리턴
return count
cand.add(tuple(new))
repair_lst = cand
return -1
- 집합을 이용한 완전탐색방식
- 처음에 Combination으로 r을 하나씩 증가시키려 했는데 너무 복잡했다
- 집합을 이용하는 방식을 위 코드에서 배웠다
외벽 점검 - 2020 카카오 공채 (python)
모든 경우의 수리 형태를 조사하는 완전탐색 문제 set, 혹은 permutation 사용
velog.io
기억해야할 것
- 원형 큐
- 원형 큐 문제를 처음 접해봐서 해매었다
- 비슷한 문제를 더 풀어보고 싶어서 아래 문제를 풀었다
- 집합
- 집합으로 탐색 영역을 표시하는 방법은 유용할 것 같아서 기억해둬야겠다
2021.08.30 - [[개발] 공부하기/코딩테스트] - [백준][분할정복] 퍼즐 자르기
[백준][분할정복] 퍼즐 자르기
BAEKJOON Online Judge(BOJ) 문제입니다. https://www.acmicpc.net/ Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 문제 https:/..
pythaac.tistory.com
'코딩테스트' 카테고리의 다른 글
[프로그래머스][KAKAO_BLIND][2018] 프렌즈4블록 (0) | 2021.09.01 |
---|---|
[프로그래머스][KAKAO_BLIND][2021] 매출 하락 최소화 (0) | 2021.09.01 |
[프로그래머스][KAKAO_BLIND][2018] 뉴스 클러스터링 (0) | 2021.09.01 |
[프로그래머스][KAKAO_BLIND][2018] 추석 트래픽 (0) | 2021.09.01 |
[백준][분할정복] 퍼즐 자르기 (0) | 2021.08.30 |