엘리스 코딩 테스트 후기 + 못푼거 문제 풀이

엘리스에서 코딩테스를 쳤는데 몇 개 못 푼문제를 다시 한 번 풀어봤다.

 

3번, 4번을 시도했지만 완벽하게 풀지 못했는데 3번은 제대로 풀었다고 생각했는데 계속 오답이 나왔다... 왜그런지 지금도 모르겠슴...나중에 전형이 끝나면 인터넷상에서 조금 변형해서 물어볼 예정

 

4번은 잘못 풀이를 했다. 시험이 끝나고 좀 고민하니까 아! 잘못 풀었구나 생각했습니다.

 

4번을 좀 후기를 남길까하는데. 문제를 똑같이 풀이하면 안되기 때문에 조금 변형해서 풀이 해볼까 합니다.

 

문제)

n명의 사람이 사람들이 호감 있는 인물 2명을1순위, 2순위로 적어서 제출하고자 합니다. 해당 쪽지에 적힌 사람은 다음 라운드로 넘어가 서로의 짝을 지어주는 프로그램에 출현할 예정입니다.

여기서 각각의 적힌 1순위 2순위를 보고 그래프를 그려보면 어떤 망형태의 구조가 생길겁니다. 그 망의 형태를 진행자 현성이 번호를 말해서 망대로 순회하면 번호를 호명할때 호명되는 사람은 그 다음 호명될  번호를 1순위 또는 2순위 번호 중 하나를 선택하는 식으로 호명합니다. 호명되지 않는 사람은 다음 짝 프로그램에서 탈락됩니다..(ㅠㅠ)

이럴 때 탈락되는 사람의 수를 구하시오

 

---

풀이)

이 문제를 딱 보고 1순위, 2순위가 한 번 선택하면 고정으로 선택한다고 착각하여

1순위를 고르는 순회 코드

2순위를 고르는 순회 코드를 합쳐서 전첸 번호의 - (합친 순회 코드들의 수)를 해서 문제를 풀었는데

 

다시 생각해보니 번호를 호명할 때 호명된  사람은 다음 번호를 선택할 때 자신이 적은 1순위 2순위를 그때그때 호명될 때 마다 선택이 바뀔 수 있었습니다.

 

이렇게 되면 오히려 문제는 쉬워집니다. 그냥 2줄기의 선택자를 가진 그래프 순회를 짜서 풀면됩니다.

시간 부족때문에 당시에 그렇게 풀지를 못했네요

당시 3번에 문제를 풀었다고 생각했는데 모조리 틀려버려서(차라리 부분은 맞고 부분은 틀렸다면) 바로 넘어갔겠지만 그렇지 않아서 시간을 끌어버린게 시간 부족의 이유 같네요...

 

---

[코드]

 

def solution(n, k, graph):
    ans = [i for i in range(n)]

    visited = []
    q = [k - 1]
    while q:
        cur = q.pop()

        # print(graph[cur])
        while graph[cur]:
            go = graph[cur].pop() - 1
            if go not in visited:
                q.append(go)
                visited.append(go)

    # print(visited)
    # print(ans)
    answer = len(ans) - len(visited)
    return answer


n = 6
k = 1
graph = [[3, 5], [1, 3], [2, 5], [1, 3], [1, 2], [1, 5]]
print(solution(n, k, graph))

---

후기

 

아쉽네요.. 쩝