카카오 블라인드 채용

[카카오] 2020 KAKAO BLIND RECRUITMENT 1차 풀이 – 기둥과 보 설치

이 포스팅에서는 2020 카카오 블라인드 채용 1차 문제인 ‘가사 검색’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/60061에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.

공식 풀이는 링크를 참조하시기 바랍니다.


기둥과 보 설치

출처 : 2020 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/60061
카테고리 : Greedy
난이도 : 보통


문제 요약

매 순간 (x좌표, y좌표, 오브젝트 타입, 명령)이 주어진다. 오브젝트는 ‘기둥’ 또는 ‘보’이며 명령은 설치 또는 제거다. 주어지는 좌표는 기둥에 대해서는 아래 지점, 보는 왼쪽 지점을 가리킨다.

기둥이 설치 가능하려면 바닥에 보가 있거나 아래에 기둥이 있어야한다. 보가 설치 되려면 그 아래에 기둥이 존재하거나 양 옆에 보가 있어야 한다.

각 입력에 대해서 입력이 유효한 경우에만 연산을 수행한다. 예를 들어 어떤 오브젝트를 설치할 수 없는 조건에서 설치할 수 없으며, 어떤 오브젝트를 제거했을 때 다른 오브젝트들에 문제가 발생한다면 제거할 수 없다.

유효한 입력들만 수행했을 때 최종적으로 존재하는 오브젝트들의 상태를 (x, y, 타입)의 리스트라고 할 때 정렬을 x -> y -> 타입 순으로 오름차순 정렬한 결과를 리턴하여라.


문제 풀이

상태 관리

Dictionary를 사용해 (x, y)값을 키로하여 상태를 관리한다. 값은 2비트로 관리되는데, 아무것도 없으면 00 = 0, 기둥만 설치되면 01 = 1, 둘 다 설치되면 11 = 3으로 간주할 수 있다.

명령의 유효성

문제에서는 없는 것을 제거하거나, 있는 것을 설치하는 경우는 없다고 하긴 했지만 일단 구현은 했다. Dictionary 상에서 현재 좌표의 상태 값을 받아서 이미 존재하는 오브젝트를 또 설치하려고 하거나 없는 것을 제거하려고 하면 False를 리턴한다.

명령 수행 결과의 유효성

명령을 수행한 결과가 유효한지 살펴야한다. 일단 설치나 제거를 수행했지만 그 결과가 유효하지 않은 상태라면 취소해야하기 때문이다.

이를 위해서는 설치/제거로부터 영향받을 수 있는 지점들의 모든 오브젝트들에 대해 유효성 검사를 수행하면 된다. 일단 기둥이 설치/제거되면 영향을 받을 수 있는 지점은

  • 기둥의 설치/제거 위치 [기둥]
  • 기둥의 설치/제거 바로 윗 지점 [기둥, 보]
  • 기둥의 설치/제거 바로 윗 지점의 왼쪽 [보]

보가 설치/제거되면 영향 받을 수 있는 지점은

  • 보의 설치/제거 위치 [기둥, 보]
  • 보의 설치/제거 위치 왼쪽 [보]
  • 보의 설치/제거 위치 오른쪽 [기둥, 보]
오브젝트의 유효성 검사
  • 기둥
    • 자신의 y좌표가 0이거나
    • 자신의 아래에 기둥이 있거나
    • 자신의 위치에 보가 있거나
    • 자신의 위치 왼쪽에 보가 있거나
    • 자신의 아래에 기둥이 있거나
    • 자신의 오른쪽 아래에 기둥이 있거나
    • 자신의 왼쪽과 오른쪽에 보가 있거나

정답 코드

def has_pillar(plot, x, y):
return (x, y) in plot and plot[(x, y)] & 1 == 1
def has_beam(plot, x, y):
return (x, y) in plot and plot[(x, y)] & 2 == 2
def is_valid_pillar(plot, x, y):
if y == 0:
return True
# has pillar below
if has_pillar(plot, x, y 1):
return True
# has beam side
if has_beam(plot, x 1, y) or has_beam(plot, x,  y):
return True
return False
def is_valid_beam(plot, x, y):
# has pillar below
if has_pillar(plot, x, y 1) or has_pillar(plot, x + 1, y 1):
return True
# has beam at both side
if has_beam(plot, x 1, y) and has_beam(plot, x + 1, y):
return True
return False
def is_valid(plot, x, y):
# empty
if (x, y) not in plot or plot[(x, y)] == 0:
return True
if plot[(x, y)] & 1 == 1 and not is_valid_pillar(plot, x, y):
return False
if plot[(x, y)] & 2 == 2 and not is_valid_beam(plot, x, y):
return False
return True
def is_valid_pillar_operation(plot, x, y):
return is_valid(plot, x, y) and is_valid(plot, x, y + 1) and is_valid(plot, x 1, y + 1)
def is_valid_beam_operation(plot, x, y):
return is_valid(plot, x, y) and is_valid(plot, x 1, y) and is_valid(plot, x + 1, y)
def change_pillar(plot, x, y, b):
if (x, y) not in plot:
plot[(x, y)] = 0
if has_pillar(plot, x, y) and b == 1:
return False
elif not has_pillar(plot, x, y) and b == 0:
return False
plot[(x, y)] ^= 1
return True
def change_beam(plot, x, y, b):
if (x, y) not in plot:
plot[(x, y)] = 0
if has_beam(plot, x, y) and b == 1:
return False
elif not has_beam(plot, x, y) and b == 0:
return False
plot[(x, y)] ^= 2
return True
def operation(plot, x, y, a, b):
# pillar
if a == 0 and change_pillar(plot, x, y, b):
if is_valid_pillar_operation(plot, x, y):
return True
change_pillar(plot, x, y, b^1)
# beam
elif change_beam(plot, x, y, b):
if is_valid_beam_operation(plot, x, y):
return True
change_beam(plot, x, y, b^1)
return False
def solution(n, build_frame):
plot = {}
answer = set()
for frame in build_frame:
x, y, a, b = frame
if operation(plot, x, y, a, b):
if (x, y, a) not in answer:
answer.add((x, y, a))
else:
answer.remove((x, y, a))
# sort answer and print
answer = list(answer)
answer.sort()
for i in range(len(answer)):
answer[i] = [0], answer[i][1], answer[i][2]]
return answer
cs

Competition 카카오 블라인드 채용 기둥과 보 설치

admin

Recent Posts

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

2일 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

1개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

1개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

1개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

2024년 9월 1일 일요일 – 서울 생활 118주차

여행 지난주에 코로나에 걸리는 바람에 근 3주만에 가족을 만나고 왔다. 집에 있어봐야 시간도 안가고 할…

2개월 ago

This website uses cookies.