프로그래머스 코딩테스트 고득점 Kit의 문제입니다.
https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit
코딩테스트 연습
기초부터 차근차근, 직접 코드를 작성해 보세요.
programmers.co.kr
문제
https://programmers.co.kr/learn/courses/30/lessons/60061
코딩테스트 연습 - 기둥과 보 설치
5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[
programmers.co.kr
내가 작성한 코드
# 아래 다른 분의 코드를 참고하여 작성
def satisfied(construct, n):
for r, c, a in construct:
# 기둥
if a == 0:
# 1. 바닥일 때
if r == n-1:
continue
# 2. 기둥 위 일때
if (r+1, c, 0) in construct:
continue
# 3. 보 위 일 때
if (r, c-1, 1) in construct or (r, c, 1) in construct:
continue
return False
# 보
else:
# 1. 기둥 위 일 때
if (r+1, c, 0) in construct or (r+1, c+1, 0) in construct:
continue
# 2. 보와 보를 연결할 때
if (r, c-1, 1) in construct and (r, c+1, 1) in construct:
continue
return False
return True
def add(construct, crnt, n):
construct.append(crnt)
if not satisfied(construct, n):
construct.pop()
return False
return True
def remove(construct, crnt, n):
construct.remove(crnt)
if not satisfied(construct, n):
construct.append(crnt)
return False
return True
def solution(n, build_frame):
answer = []
construct = []
# 좌표로 볼 때 n+1개
n += 1
for const in build_frame:
# (x,y)에 a(0:기둥,1:보)를 b(0:삭제,1:설치)
# 좌표를 편하게 사용하기위해 (n-y-1, x)를 사용
x, y, a, b = const
if b == 0:
if remove(construct, (n-y-1, x, a), n):
answer.remove([x,y,a])
else:
if add(construct, (n-y-1, x, a), n):
answer.append([x,y,a])
return sorted(answer)
- 추가/제거된 건축물(기둥/보)마다 조건을 만족하면 결과에 반영
- 조건 변형
- n += 1
- 좌표의 개수는 n+1개이므로, 1을 더해줌 - (n-y-1, x)
- 위, 아래, 좌, 우 익숙한 방향으로 사용하기 위해 변형
- n += 1
- 함수
- add
- 추가했을 때 조건을 만족하면 추가한 채로 True - remove
- 제거했을 때 조건을 만족하면 제거한 채로 False - satisfied
- 현재 건축물(기둥/보)들이 모든 조건을 만족하면 True
- add
다른 사람이 작성한 코드
def impossible(result):
COL, ROW = 0, 1
for x, y, a in result:
if a == COL: # 기둥일 때
if y != 0 and (x, y-1, COL) not in result and \
(x-1, y, ROW) not in result and (x, y, ROW) not in result:
return True
else: # 보일 때
if (x, y-1, COL) not in result and (x+1, y-1, COL) not in result and \
not ((x-1, y, ROW) in result and (x+1, y, ROW) in result):
return True
return False
def solution(n, build_frame):
result = set()
for x, y, a, build in build_frame:
item = (x, y, a)
if build: # 추가일 때
result.add(item)
if impossible(result):
result.remove(item)
elif item in result: # 삭제할 때
result.remove(item)
if impossible(result):
result.add(item)
answer = map(list, result)
return sorted(answer, key = lambda x : (x[0], x[1], x[2]))
- 전체가 아닌, 각 건축물의 조건을 확인하는 방식
기둥과 보 설치 - 2020 카카오 공채 (python)
시뮬레이션 해보고 설치 혹은 제거가 가능한지 매번 확인해가는 방식 set 이용, 좌표화, 추상화, 조건 체크
velog.io
기억해야할 것
- 문제 접근 방식
- 전체 건축 상황을 고려하며 추가/삭제하면 문제가 매우 복잡하다
- 예를 들어, 기둥을 제거해도 되는지 확인할 때
- 기둥 위에 보가 있는지 확인
- 보가 있으면 보가 다른 보와 연결되어 있는지 확인
- 연결된 보들이 모두 기둥 조건을 만족하는지 확인 - 탐색이 정형화되지 않는 복잡한 문제에 대해, 간단하게 정형화할 수 있는 방법을 꼭 찾아야한다
'코딩테스트' 카테고리의 다른 글
[백준][분할정복] 퍼즐 자르기 (0) | 2021.08.30 |
---|---|
[백준][그리디] 휴먼 파이프라인 (0) | 2021.08.30 |
[프로그래머스][KAKAO_BLIND][2019] 후보키 (0) | 2021.08.30 |
[프로그래머스][KAKAO_BLIND][2019] 실패율 (0) | 2021.08.30 |
[프로그래머스][KAKAO_BLIND][2020] 자물쇠와 열쇠 (0) | 2021.08.29 |