[프로그래머스] 위클리 챌린지 7주차(python)

[문제 설명]

코딩테스트 연습 - 7주차

---

[나의 답안]

def solution(enter, leave):
    answer_dict = {person: 0 for person in enter}
    num_person = len(enter)

    for i in range(1, num_person + 1):
        for j in range(i + 1, num_person + 1):
            person1 = leave[-i]
            person2 = leave[-j]

            if enter.index(person1) < enter.index(person2):
                answer_dict[person1] += 1
                answer_dict[person2] += 1
            else:
                for k in range(max(i, j) + 1, num_person + 1):
                    threshold = max(enter.index(person1), enter.index(person2))
                    if threshold < enter.index(leave[-k]):
                        answer_dict[person1] += 1
                        answer_dict[person2] += 1
                        break

    return [num[1] for num in sorted(answer_dict.items(), key=lambda x: x[0])]

결과부터 말하면, 왼쪽 사진처럼 시간 초과가 났다.

문제를 처음 보자마자 Stack 원리로 풀려고 했으나, 일단 조건부터 찾게 되었다.

 

1) enter.index(leave[i]) < enter.index(leave[j])

   : 비교 대상보다 먼저 입실 했지만, 더 늦게 퇴실한 경우

2) threshold < enter.index(leave[-k])

   : 1번 조건에 부합하지 않고,

     비교하고 있는 두 대상보다 늦게 입실 했는데, 먼저 퇴실한 경우

 

위와 같은 조건으로 코드를 작성했는데, 역시 자료구조 활용 없이 다중 for loop로 문제를 풀어서 시간 초과가 났다.

 

최대한 시간 초과가 안나려고 머리를 짜내봤지만, 결국 못 풀어서 구글링 하여 답안을 제출하고, 다른사람의 코드를 보고 공부하였다. 

---

※회고

아직 실력이 많이 부족해서, 이번에는 내 코드를 고치는 것 보다 다른 사람이 어떻게 접근했는지 확인했다.

아래 코드는 가장 심플하고, 이번주 추천을 많이 받은 코드이다.

def solution(enter, leave):
    answer = [0] * len(enter)

    room = []
    e_idx = 0
    for l in leave:
        while l not in room:
            room.append(enter[e_idx])
            e_idx += 1
        room.remove(l)
        for person in room:
            answer[person - 1] += 1
        answer[l - 1] += len(room)

    return answer

전제 : 퇴실 할 사람이 방에 들어올 때 까지 입실 리스트에서 차례대로 채워 넣는다.(퇴실 하기 위해선 입실을 해야 하니깐)

- L7 : 퇴실 할 사람이 들어올 때 까지 반복문을 계속한다

- L8 : 퇴실 할 사람이 아직 방에 안들어와 있으면, 차례대로 입실시킨다.

- L9 : 퇴실 할 사람이 방에 들어와서 while문을 빠져나오면, 퇴실 시킨다.

- L11 : 퇴실 후 방에 남은 사람은 지금 퇴실하려는 사람과 만났으므로,

  - L12 : 방에 남은 사람들 모두 만난 사람 1명씩 추가한다.

  - L13 : 지금 퇴실하려는 사람은 방에 남은 모든 사람들을 만났으므로, room 길이 만큼 더해준다.

- index를 (person-1), (l-1)로 하게 되면, 자연스럽게 n번 사람은 n-1번에 넣어지므로 사람 번호 순서대로 오름차순 해줄 필요도 없다.

 

애초에, 문제 푸는 접근법부터 잘못했던 것 같다.

제일 원초적인 다중 for loop 보다, 로직을 생각해보는 쪽으로 앞으로 문제를 접근해야 겠다.

코딩은 어려워~