기둥과 보 설치

https://school.programmers.co.kr/learn/courses/30/lessons/60061

프로그래머스

---

try1

문제를 읽고 설치가 가능하면 설치하는 알고리즘과 삭제가 가능하면 삭제하는 알고리즘을 짜면 끝일 것이라 생각함

설치가 가능하면 설치하는 알고리즘은 구현이 쉬웠지만,

삭제가 가능하면 삭제하는 알고리즘은 삭제 시킬 수 있는 조건을 찾기가 어려워 재건축 방식으로 구현함

 

※나의 코드

def solution(n, build_frame):
    answer = []
    for x, y, a, b in build_frame:
        if b == 1:   # 설치 시
            if a == 0:  # 기둥
                if y == 0 or [x, y, 1] in answer or [x - 1, y, 1] in answer or [x, y - 1, 0] in answer:
                    answer += [[x, y, a]]
            else:       # 보
                if [x, y - 1, 0] in answer or [x + 1, y -1, 0] in answer or ([x - 1, y, 1] in answer and [x + 1, y, 1] in answer):
                    answer += [[x, y, a]]
        else:        # 삭제 시
            answer.remove([x, y, a])
            for xx, yy, aa in answer:
                if aa == 0:    # 기둥
                    if yy == 0 or [xx, yy, 1] in answer or [xx - 1, yy, 1] in answer or [xx, yy - 1, 0] in answer:
                        continue
                    answer += [[x, y, a]]
                    break
                else:          # 보
                    if [xx, yy - 1, 0] in answer or [xx + 1, yy -1, 0] in answer or ([xx - 1, yy, 1] in answer and [xx + 1, yy, 1] in answer):
                        continue
                    answer += [[x, y, a]]
                    break
    return sorted(answer)

문제풀이)

for문으로 build_frame을 돌아서 매 작업당 if문을 거침

설치 시 if문으로 기둥일 때와 보일 때 설치 가능한 상태라면 answer에 [x, y, a]를 추가함

삭제 시 answer에서 삭제할 [x, y, a]를 제거하고 남은 answer을 for문으로 돌려서 if문으로 설치가 가능한 상태인지 확인함

설치가 가능하면 continue로 계속 for문을 돌고, 아니라면 answer에 [x, y, a]를 다시 추가하고 break함

마지막으로 정렬한 answer을 return함

 

테스트 결과) - 총합 4919.72ms

테스트 1 〉	통과 (0.05ms, 10.4MB)
테스트 2 〉	통과 (0.09ms, 10.2MB)
테스트 3 〉	통과 (0.04ms, 10.3MB)
테스트 4 〉	통과 (0.12ms, 10.1MB)
테스트 5 〉	통과 (0.11ms, 10.2MB)
테스트 6 〉	통과 (0.92ms, 10.3MB)
테스트 7 〉	통과 (0.02ms, 10.2MB)
테스트 8 〉	통과 (0.02ms, 10.1MB)
테스트 9 〉	통과 (0.03ms, 10.1MB)
테스트 10 〉	통과 (40.51ms, 10.3MB)
테스트 11 〉	통과 (232.89ms, 10.5MB)
테스트 12 〉	통과 (20.73ms, 10.3MB)
테스트 13 〉	통과 (356.79ms, 10.5MB)
테스트 14 〉	통과 (41.63ms, 10.3MB)
테스트 15 〉	통과 (304.61ms, 10.6MB)
테스트 16 〉	통과 (22.78ms, 10.2MB)
테스트 17 〉	통과 (265.96ms, 10.7MB)
테스트 18 〉	통과 (574.67ms, 10.3MB)
테스트 19 〉	통과 (542.24ms, 10.5MB)
테스트 20 〉	통과 (617.35ms, 10.4MB)
테스트 21 〉	통과 (740.63ms, 10.4MB)
테스트 22 〉	통과 (529.69ms, 10.3MB)
테스트 23 〉	통과 (627.84ms, 10.5MB)

 

try2

삭제가 가능하면 삭제하는 알고리즘에서 answer을 전부 돌기보다는 삭제시킬 기둥과 보 주위만 확인하면 될 것 같다는 생각이 듬

 

※ 나의 코드

def solution(n, build_frame):
    answer = []
    for x, y, a, b in build_frame:
        if b == 1:         # 설치 시
            if a == 0:        # 기둥
                if y == 0 or [x, y, 1] in answer or [x - 1, y, 1] in answer or [x, y - 1, 0] in answer:
                    answer += [[x, y, a]]
            else:             # 보
                if [x, y - 1, 0] in answer or [x + 1, y -1, 0] in answer or ([x - 1, y, 1] in answer and [x + 1, y, 1] in answer):
                    answer += [[x, y, a]]
        else:              # 삭제 시
            answer.remove([x, y, a])
            if a == 0:        # 기둥
                lst = [[x - 1, y + 1, 1],[x, y + 1, 1],[x, y + 1, 0]]
                check = [c for c in lst if c in answer]
                for cx, cy, ca in check:
                    if ca == 0:
                        check = []
                        if cy == 0 or [cx, cy, 1] in answer or [cx - 1, cy, 1] in answer or [cx, cy - 1, 0] in answer:
                            continue
                        answer += [[x, y, a]]
                    else:
                        if [cx, cy - 1, 0] in answer or [cx + 1, cy -1, 0] in answer or ([cx - 1, cy, 1] in answer and [cx + 1, cy, 1] in answer):
                            continue
                        answer += [[x, y, a]]
            else:             # 보
                lst = [[x - 1, y, 1],[x + 1, y, 1],[x, y, 0],[x + 1, y, 0]]
                check = [c for c in lst if c in answer]
                for cx, cy, ca in check:
                    if ca == 0:
                        check = []
                        if cy == 0 or [cx, cy, 1] in answer or [cx - 1, cy, 1] in answer or [cx, cy - 1, 0] in answer:
                            continue
                        answer += [[x, y, a]]
                        break
                    else:
                        if [cx, cy - 1, 0] in answer or [cx + 1, cy -1, 0] in answer or ([cx - 1, cy, 1] in answer and [cx + 1, cy, 1] in answer):
                            continue
                        answer += [[x, y, a]]
                        break
    return sorted(answer)

문제풀이)

try1과 다른점은 삭제 시킬 건축물이 기둥일 때와 보일 때를 나눠서 확인해야할 기둥과 보를 lst에 담고 그것이 answer에 있다면 check에 담음

그 후엔 똑같은 방식으로 for문으로 check를 돌아서 설치가 가능하다면 for문을 계속 돌고 아니라면 answer에 [x, y, a]를 다시 추가하고 break

 

테스트 결과) - 총합 216.63ms

테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.08ms, 10.3MB)
테스트 3 〉	통과 (0.03ms, 10.3MB)
테스트 4 〉	통과 (0.04ms, 10.1MB)
테스트 5 〉	통과 (0.06ms, 10.3MB)
테스트 6 〉	통과 (0.15ms, 10.1MB)
테스트 7 〉	통과 (0.01ms, 10.3MB)
테스트 8 〉	통과 (0.02ms, 10.3MB)
테스트 9 〉	통과 (0.02ms, 10.2MB)
테스트 10 〉	통과 (4.04ms, 10.3MB)
테스트 11 〉	통과 (15.91ms, 10.4MB)
테스트 12 〉	통과 (3.49ms, 10.2MB)
테스트 13 〉	통과 (16.35ms, 10.6MB)
테스트 14 〉	통과 (3.70ms, 10.3MB)
테스트 15 〉	통과 (16.45ms, 10.6MB)
테스트 16 〉	통과 (3.94ms, 10.3MB)
테스트 17 〉	통과 (18.64ms, 10.6MB)
테스트 18 〉	통과 (19.63ms, 10.4MB)
테스트 19 〉	통과 (33.73ms, 10.4MB)
테스트 20 〉	통과 (22.97ms, 10.3MB)
테스트 21 〉	통과 (22.87ms, 10.4MB)
테스트 22 〉	통과 (16.72ms, 10.4MB)
테스트 23 〉	통과 (17.75ms, 10.4MB)