[프로그래머스-2019겨울카카오인턴]호텔방배정

문제설명

https://programmers.co.kr/learn/courses/30/lessons/64063

문제 이해하는 것은 쉬운 편이나 어떻게 접근할 것인지 결정하는게 어려운 문제

1번방에 배정받은 사람이 있고 1번 방을 배정받기 원한다면 2번방을 배정해줘야 한다.

2번방에도 사람이 있다면 다음 사람이 없는 방인 3번방으로 배정.

예외도 없다.

방이 모두 5개있고 5번방을 2번 요청하는 경우는 input으로 주어지지 않는다고 적혀있다.

접근

1.UnionFind

딱 UnionFind가 생각나는 문제. 1~3번방에 사람이 있다면 결국 하나의 그룹을 이룬다고 생각할 수 있다. 그 이유는

1) 문제의 목표는 번호 x가 주어질 때 다음 방 배정을 찾는 것이다.

2) 번호가 1,2,3일 때 다음 방 배정은 동일하게 4이다.

따라서 연속된 숫자가 주어질 경우 다음 방 번호 배정을 기준으로 하나의 그룹으로 묶을 수 있다는 것이다.

그리고 배정된 방번호를 받는다면 위의 기준에 맞게 연속된 수 선택시 다음 방 번호배정을 통일시켜야 하므로 반드시 그룹을 합쳐줘야 한다.

1)배정해야할 곳 왼쪽에 그룹이 있다면 왼쪽과 합치기

2)오른쪽에 있다면 오른쪽과 합치기

이를 좀 더 구체적으로 서술하자면 다음과 같다. (unionFind에 대한 배경지식 필요)

• parents는 dict 타입이며 key는 childNode value는 parentsNode를 의미한다.

• key와 value가 일치할 경우 해당 그룹의 rootNode이다.

• 그리고 X가 배정 받지 않은 방, O가 배정받은 방, ㅁ`이 배정을 원하는 방이라면

접근1) (이번이 두번째 문제풀이 시도인데 첫번째때 이렇게 짜다가 1시간 반 동안 삽질 후결국 포기했다.)

1. if else 구문으로 ㅁ`ㅁ(배정할 방) ㅁ에 들어오는 8가지를 구분한다. (X,X`,O//X,O`,X.....)
2. 각 케이스에 대하여 합치는 코드 작성

접근2) 집어넣을 곳 기준, 왼쪽 그룹과 집어넣을 곳, 집어넣을 곳과 오른쪽 그룹을 합친다.

1. 집어넣을 곳을 찾는다.

   • 집어넣을 곳에 값이 없다면 집어넣는 부분이 곧 root노드. (parents[roomNum] = roomNum)

   • 집어 넣을 곳에 값이 있다면 루트노드를 찾는다.

2. 집어넣을 곳 기준 왼쪽노드그룹의 root와 오른쪽 노드 그룹의 root를 찾는다.

   • 이때 루트값이 존재하지 않으면 -1반환.

3. 찾았다면 leftRootNode와 집어넣을 곳 노드(curNode), 집어넣을 곳 노드와 rightRootNode Union연산.

   • 이때 두가지 경우에 각각에 대해 두 노드(leftRootNode,curNode // curNode,rightRootNode) 중 하나라도 -1 값을 가진다면 Union연산을 하지 않는다.
     • (leftRootNode,curNode,rightRootNode) = (-1,3,4)일 경우 left,cur에대해선 수행x cur,right에 대해선 수행

접근2가 접근1보다 좋은 점

접근 2처럼 해주면 모든 경우에 대해 if else로 복잡하게 짤 필요가 없다. class마냥 일반적인 계산 과정을 정의해두고, 처리 해주지 말아야할 값이 공통이므로 가독성이 훨씬 좋아지고 코드가 간결해진다.

비유하자면 이와 비슷한 것 같다.

1)북쪽으로 신호등을 건널 때 서쪽 동쪽을 봐주고 동쪽으로 건널 땐 북쪽 남쪽을 봐주고....

2)신호등을 건널땐 좌우를 살펴~

이렇게 한것이다.

근데 이렇게 접근하는건 문제를 매우 잘 이해해야 가능할 듯... 문제를 많이 풀어보면서 일반화시킬 방법을 빨리 생각하는 수 밖에

시간초과 문제

그런데 문제가 있다. 위처럼만 구현하면 효율성테스트는 떨어질 것이다. FindSet연산에서 루트노드를 찾아가는 과정이 계속해서 반복되기 때문.

• 1,1,1,1이 입력으로 주어지면 1, 1->2, 1->2->3, 1->2->3->4 이렇게 중복해서 연산하게 될 것이다.

어차피 연결관계가 중요한게 아닌, rootNode찾는 것이 중요하므로 방문하는 child 노드들의 부모를 root노드로 연결시켜버리면 된다.(이는 백준의 UnionFind와 매우 유사.)

구현

def FindSet(node,parents):
    if node not in parents:
         return -1

    curNode = node
    childList = []
    while parents[curNode] != curNode:
        childList.append(curNode)
        curNode = parents[curNode]

    for child in childList:
        parents[child] = curNode

    return curNode

def UnionSet(root1,root2,parents): #root값이 -1이면 존재하지 않는 값.
    if root1 == -1 or root2 == -1 :
        return -1

    parents[root1] = root2
    return 1

def solution(k, room_number):
    answer = []
    parents = {}
    for room in room_number:
        leftRoot = -1
        #1.room이 들어갈 자리 찾기
        if room not in parents:
            insertedRoot = room
        else:
            leftRoot = FindSet(room,parents)
            insertedRoot = leftRoot + 1

        #2.루트노드는 자기 자신이 담겨야 함.
        parents[insertedRoot] = insertedRoot
        #3.answer에 값담기
        answer.append(insertedRoot)

        #4.찾은 자리 기준 unionFind 실시
            #4-1. 왼쪽노드찾기.   000x 0이 값이 존재한 곳이라면 왼쪽으로부터 3번째 0위치가 값넣는 x기준 왼쪽.
        if leftRoot == -1:
            leftRoot = FindSet(insertedRoot-1, parents)
        rightRoot = FindSet(insertedRoot + 1, parents)

        UnionSet(leftRoot,insertedRoot,parents)
        UnionSet(insertedRoot,rightRoot,parents)

    return answer

1. 이번 구현에선 시행착오 발견시 유지보수 할 수 있도록 모듈화에 매우 신경썼다.

• solution 함수 부분에 root노드가 -1인 것을 따로 작성하려다가 FindSet함수에 적어주었고, UnionSet에서 root노드가 -1이 아닐 때만 들어가도록 하려다 합산 연산 중 에러로 보아 UnionSet에 수행하고 return을 -1로 출력하도록 했다.

2. 이렇게 모듈화에 신경쓴 이유는 라인 코딩테스트 해설을 봤는데 시행착오에 따라 코드를 작성한 것을 보았기 때문. 문제를 완벽히 이해하고 올바른 접근으로 한 번에 코드를 완성하면 좋겠지만 반드시 가능하지는 않다. 따라서 실패시 패닉와서 안되는 코드를 덕지덕지 수정하기 보단 체계적으로 작성된 코드 아래 수정하도록 하려한다.

3. 내가 문제풀이시 할애하는 시간을 보면 다음과 같다

   1)문제이해 10%

   2)접근방법 구체화 40%

   3)코드 작성 20%

   4)디버깅 30%

   디버깅은 평균적인 시간이며, 편차가 매우 크다. 적게는 5분, 많게는 40분까지도 걸렸다. 이 편차를 줄이기 위해 2,3번에 시간을 더 많이 투자하는게 좋다고 생각.