2022년 7월 31일 TIL - 체육복

 

오늘도 코딩 도장 문제 체육복에 대한 글이다.

 

 

웹 페이지 과제 CSS를 수정하고 HTTP에 대해 조사하던 중 자극이 왔고, 40분 가량의 시간을 들여 조건을 파고 파고 판 끝에 다음과 같은 문제 풀이 과정을 도출했다.

 

1. 준비
   1. 수업에 참여 가능한 학생 수 = 전체 학생 수 - 체육복을 도난당한 학생 수
   2. 다음의 변수들을 선언한다.
      - 여벌 체육복을 가진 학생이 체육복을 빌려줬는지 체크하는 맵 변수
      - 여벌 체육복을 가졌으나 도난당한 학생인지를 체크하는 리스트 변수
   3. 여벌 체육복을 가진 학생이 도난당한 학생이라면 여벌 체육복을 가졌으면서 도난당한 학생 체크 리스트에 추가하고, 수업에 참여 가능한 학생 수에 +1
   4. 여벌 체육복을 가진 학생이 도난당한 학생이 아니라면 체육복 빌려줌 상태 체크 맵 변수에 Key로 해당 학생의 인덱스 번호를, Value로 빌려주지 않았음을 나타내는 false를 추가한다.
2. 풀이
   
   1. 체육복을 도난당한 학생 각각에 대하여 다음의 작업들을 수행한다.
      
      1. 여벌 체육복을 가졌으면서 도난당한 학생이면 작업을 수행하지 않고 통과한다.
      2. 앞의 학생이 여벌 체육복을 가졌는지 확인한다.
         1. 여벌이 있으면 해당 여벌 체육복을 가진 학생의 빌려준 상태를 나타내는 Value를 true로 변경한다.
         2. 수업에 참여 가능한 학생 수에 +1
      3. 앞의 학생이 여벌 체육복이 없으면 뒤의 학생에 대해 위의 작업을 다시 수행한다.
      4. (앞 뒤 학생 모두 여벌 체육복이 없으면 해당 학생은 수업에 참여할 수 없다.)
3. 수업에 참여 가능한 학생 수를 반환한다.

 

해당 풀이 과정으로 제출했을 때의 결과는 16개 테스트 케이스 중 2개의 테스트 케이스를 통과하지 못한 것으로 나타났다. 문제를 먼저 풀어서 제출한 동료의 코드를 살펴봤고, 동료의 소스코드에는 가장 먼저 입력으로 주어지는 변수들 중 도난당한 학생들의 인덱스 배열을 오름차순으로 정렬하는 과정이 있었다.

 

해당 부분을 참고해 소스코드의 가장 첫 부분에 도난당한 학생 인덱스 배열을 오름차순으로 정렬하는 과정을 추가한 뒤 제출을 시도해 보았고, 그제서야 테스트 결과 화면에 지긋지긋한 빨간 글씨가 하나도 뜨지 않는 모습을 볼 수 있었다.

 

 

 

왜 도난당한 학생 배열을 정렬하지 않으면 위의 과정에서 틀린 답을 도출할 수도 있을까? 스스로 고민할 힘은 남아있지 않았고, 구글에 '프로그래머스 체육복 정렬'을 검색해 결과로 나온 페이지에 접속해 내용을 읽어봤다.

 

다음과 같은 케이스를 생각해볼 수 있다.

 

학생 1	학생 2	학생 3	학생 4	학생 5	학생 6	학생 7
	도난당함[1]		도난당함[0]
		여벌 있음		여벌 있음

 

해당 케이스에서 도난당한 학생 인덱스 배열의 요소는 {4, 2} 순서이다. 문제 풀이 과정에서 주어진 배열의 요소를 순차적으로 탐색할 경우 4번 학생, 2번 학생 순으로 과정을 수행하게 될 것이다. 먼저 4번 학생의 앞 뒤 학생의 여벌 여부를 탐색하여 체육복을 빌리면 결과는 다음과 같을 것이다.

 

학생 1	학생 2	학생 3	학생 4	학생 5	학생 6	학생 7
	도난당함[1]		참석 가능
		여벌 없음		여벌 있음

 

다음으로 학생 2의 앞 뒤 학생의 여벌 보유 여부를 확인하겠지만, 학생 2의 앞 뒤에 여벌의 체육복이 있는 학생은 없고, 따라서 학생 2는 수업에 참석하지 못한다. 그러나 이 케이스의 최적의 해는 학생 2와 학생 4 모두 뒤의 학생에게 체육복을 빌려 수업에 참석할 수 있는 경우이므로 학생 2가 수업에 참여하지 못하는 해는 최적해가 되지 못한다. 즉 도난당한 학생 앞 뒤의 학생이 여벌의 체육복이 있는지를 검사하는 순서가 앞의 학생 >> 뒤의 학생 순서로 이루어진다면, 도난당한 학생 각각을 탐색하는 순서도 앞 번호의 학생에서부터 진행되어야 할 것이다.

 

 

 

정렬되지 않은 도난당한 학생 인덱스 배열이 주어질 수도 있다는 사실은 인지하고 있었지만, 그게 문제 풀이에 영향을 미칠 것이라고는 생각하지 않고 있었었다. 테스트 케이스를 어느 정도 수준까지 생각해낼 수 있어야 하는지 감이 잡히지 않았었기 때문이다.

 

말도 안 되는 수준의 테스트 케이스까지 생각해내기는 어렵겠지만, '입력으로 주어지는 배열이 정렬되었는지, 정렬되지 않은 것인지에 따라 설계한 작업 수행에 영향을 미칠 수 있으므로 입력의 상태를 더 다양하게 고려해야 한다' 는 부분 정도는 다음에 문제를 풀 때 고려할 수 있을 것 같다.