5002번 도어맨

문제 설명

이번 문제는 클럽의 출입구에서 남녀 수의 차이를 맞춰주는 도어맨이 있고 도어맨이 기억할 수 있는 수 차이의 최대값이 주어졌을 때, 이 도어맨이 아래 규칙을 지키면서 사람들을 들여보낼 수 있는 최대 수를 구하는 문제입니다.

• 줄의 맨 앞에 줄 서 있는 사람을 들여보내야 되는 것은 아니다.
• 남녀 수의 차이를 고려해 두 번째 사람을 들여보내도 된다.

 

 

문제 풀이

아이디어

탐색

이번 문제는 주어진 순서를 모두 파악해야 하므로 모두 탐색해봐야 한다.

 

비교는 절대값으로

앞에서부터 사람을 들여보낼 때, 도어맨이 기억할 수 있는 수 차이의 최대값을 넘기지 않는 선에서 앞 사람이나 두 번째 사람을 들여보내야 합니다.

여기서, 남자를 1, 여자를 -1이라 하면 첫 번째 사람이나 두 번째 사람을 들여보냈을 경우 현재의 수 차이에서 각각을 더해주면 됩니다.

수 차이를 비교할 때는! 절대값으로 크기 비교를 해서 절대값을 작게 만드는 사람을 클럽으로 들여보내줍니다.

 

추가 설명

현재 클럽 내부의 남녀의 수 차이가 -2(여자가 두 명 많은 경우)라고 하면 여기서 줄의 첫 번째 사람은 남자이고 두 번째 사람은 여자라고 해보겠습니다.

만약 첫 번째 사람인 남자를 들여 보낸다고 하면 남녀의 수 차이가 -1이 되고 두 번째 사람인 여자를 들여 보낸다고 하면 남녀의 수 차이가 -3이 됩니다.

-1의 절대값과 -3의 절대값을 비교하면 -1이 더 작습니다. 그러므로 클럽 내부에 첫 번째 사람인 남자를 들여보냅니다.

 

이 문제에서 염두해야 되는 것은 도어맨이 기억할 수 있는 수 차이의 최대값을 넘지 않는 것이므로, 남녀 수 차이의 절대값을 최대한 줄여주는 방식으로 코드를 짜도 될 것 같습니다.

 

풀이

문제에서 주어진 입력 변환

문제에서 남자는 M, 여자는 W로 주어졌는데, 이를 편의성을 위해 M=1로 W=-1로 바꿔 줍니다.

 

절대값을 비교

문제에서 주어진 순서(order 변수에 저장됨)를 while문으로 len(order)>1일 동안 아래 행동을 반복해줍니다.

(difference = 현재 클럽 내부의 남녀 수 차이)

 

difference + order[0]과 difference + order[1]의 절대값을 비교해 선자가 작거나 같을 경우 0번째 원소를 pop시켜 줍니다. 후자가 작을 경우 1번째 원소를 pop시켜 줍니다.

 

추가 설명

while문을 배열의 len(order)>0이 될 때까지 돌지 않는 이유는 절대값 비교를 하기 위해서는 최소 2개의 원소가 필요하기 때문입니다.

그러므로, len(order)>1일 때까지만 반복문을 돌고 남은 하나의 원소에 대해서는 while문 바깥에서 한 번 더 연산해줍니다.

 

difference + order[0]과 difference + order[1]의 절대값 비교에서 선자와 후자가 같은 경우에도 order[0]을 pop시키는 이유는 선자와 후자의 절대값이 같다는 것은 order[0]과 order[1]이 같다는 말로, 둘의 성이 같다는 말입니다.

그러므로 누구나 들어갈 수 있지만 필자가 임의로 0번째 사람을 pop시켜준 것입니다.

 

 

해결

이번 문제는 차근히 생각해 적당한 시간 내에 풀었던 문제였던 것 같습니다. 말로는 설명이 되지만, 이것을 코드로 풀어내는 것을 연습하기에 좋은 문제 같습니다.

 

문제 링크 : https://www.acmicpc.net/problem/5002

5002번: 도어맨

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/5002.py