[프로그래머스] 기둥과 보 설치(python) - 2020 카카오 신입 공채

문제 바로가기(프로그래머스)

 

아이디어 : 구현(시뮬레이션), 전체탐색

전형적인 시뮬레이션 문제로, 문제에서 제시한 구체적인 처리과정을 차례대로 코드화하면 된다. 문제를 제대로 이해하는 데 꽤 오랜 시간이 걸렸다. (카카오 코테의 대표적인 특징이랄까) 문제에서 제시해준대로 기둥과 보의 존재 요건을 그대로 적용한다.

설치할 때의 조건 만족 여부는 명확한 확인이 가능하지만, 삭제할 때의 조건 만족 여부는 주변의 여러 기둥, 보를 모두 확인해봐야 하므로 굉장히 까다롭다. 따라서 삭제를 요구할 때마다 일일이 전체 구조물을 확인하는 전체탐색 방법을 사용할 수 있다. 시간복잡도가 문제일 수 있지만, 문제에서 제한한 전체 명령의 개수는 최대 1,000개 이다. O(M^2)으로 하는 것이 가장 이상적일텐데, 이 문제의 시간 제한이 5초로 넉넉하므로 O(M^3)까지의 알고리즘도 가능할 것이다.

 

삭제의 경우를 확인하는 것이 까다롭기 때문에 전체탐색 방법을 사용해야겠다 라는 생각이 들면 성공이다.

삭제 시 전체탐색을 한다면, 코드의 가독성을 위해 설치할 때도 전체탐색 방법을 사용하는 게 좋다.

check 함수를 이용해 기둥이냐 보냐에 따라 주변 상태를 확인하도록 구현했다.

---

잠깐 코딩테스트에서의 시간복잡도에 대해 얘기해보자면,

• 코테에서 시간 제한은 1 ~ 5초 정도
• 문제에 명시되어 있지 않은 경우, 대략 5초 정도라고 생각하고 문제를 푸는 것이 좋다.

시간 제한이 1초인 문제에 대해 N의 범위에 따른 시간복잡도를 계산해보면

• N의 범위가 500인 경우 : 시간복잡도가 O(N³)인 알고리즘 설계 가능
• N의 범위가 2,000인 경우 : 시간복잡도가 O(N²)인 알고리즘 설계 가능
• N의 범위가 100,000인 경우 : 시간복잡도가 O(NlogN)인 알고리즘 설계 가능
• N의 범위가 10,000,000인 경우 : 시간복잡도가 O(N)인 알고리즘 설계 가능

---

def check(answer):
    for x, y, stuff in answer:
        if stuff == 0: #기둥 체크
            #'바닥 위' or '보의 한쪽 끝 위' or '또 다른 기둥 위' 
            if y == 0 or [x-1, y, 1] in answer or [x, y, 1] in answer or [x, y-1, 0] in answer:
                continue
            return False
        elif stuff == 1: #보 체크
            #'한쪽 끝 부분이 기둥 위' or '양쪽 끝 부분이 다른 보와 동시 연결'
            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):
                continue
            return False
    return True

def solution(n, build_frame):
    answer = []
    for build in build_frame:
        x, y, stuff, operation = build
        if operation == 1: # 설치
            answer.append([x, y, stuff])
            if not check(answer): answer.remove([x, y, stuff])
        elif operation == 0: # 삭제
            answer.remove([x, y, stuff])
            if not check(answer): answer.append([x, y, stuff])
    answer.sort()
    print(answer)
    return answer

 

파이썬 연산자 우선순위 다시 확인하기 !!

조건문에서 in과 or 간 우선순위가 헷갈렸는데 in >>>> and > or 이다.

따라서 이 문제에서는 [x, y, a] in answer 부분을 여러 번 반복해야 했다.