49. 완주하지 못한 선수

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 완주하지 못한 선수의 이름을 구하라
• 주어진 자료는 무엇인가?
   - 마라톤 참여한 선수의 이름이 담긴 배열 participant / 완주한 선수들의 이름이 담긴 배열 completion
   - 완주하지 못한 선수를 한 사람이다
• 조건은 무엇인가?
   - 참가가 중에는 동명이인이 있을 수 있다.
• 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
• 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라.
   - 리턴 값이 전부 한개이다.

 

2. 계획

참가자 명단에서, 완주한 명단을 뺀다

 

참가자 배열에서 그리고 완주한 명단에서 찾아서 뺀다.

참가자 명단에 남은 선수의 이름을 반환한다.

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

4. 반성

• 문제를 다른 방식으로 해결할 수 있는가?
• 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
• 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
• 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?

 

문제를 총 세가지 방법으로 풀었다.

우선, 첫번째 재귀로 풀기

const findIncompletion = (participants, completions) => {
    if (completions.length === 0) {
        return participants[0];
    }

    const person = completions[0];
    const index = participants.findIndex((it) => it === person);
    
    return findIncompletion(
        [...participants.slice(0, index), ...participants.slice(index + 1)],
        completions.slice(1)
    )
 }

participants랑 completions이랑 비교해서 동일한 요소가 있으면 각 배열에서 그 요소를 제거한다.

그래서 결국에 completions이 빈 배열이 될때까지 반복해주면 된다.

 

처음에 completions이 빈 배열일 때 participants의 첫번째 요소를 리턴하도록 해주었다.

(첫번째 요소랄것도 없이 어차피 리턴 값이 하나이기 때문에 participants에는 요소 하나밖에 안남았을것임)

if (completions.length === 0) {

return participants[0];

}

그다음에는 participants에서 completions의 첫번째 요소랑 같은 값을 찾는 변수를 만들어줬다.

const person = completions[0];

const index = participants.findIndex((it) => it === person);

 

그리고 participants에서 인덱스0부터 위에서 구한 index 변수 전까지 자르고,

index 변수 다음 요소부터 participants의 마지막 인덱스까지 자른것을 새로운 배열로 만든다.

[...participants.slice(0, index), ...participants.slice(index + 1)],

그리고 completions에서 첫번째 요소 삭제

completions.slice(1)

 

이렇게 재귀를 사용해서 풀어보았다.

 

 

그리고 두번째, 재귀랑 풀이는 비슷한데 for 반복문을 사용해서도 풀어보았다.

const findIncompletion = (participants, completions) => {
	let result = participants;

    for (i = 0; i < completions.length; i++) {
        const personIndex = result.findIndex(participant => participant === completions[i]);
        result = [...result.slice(0, personIndex), ...result.slice(personIndex + 1)];
    }
    return result[0];
}

재귀랑 풀이는 똑같은데 for문 안에서 반복을 해줬다.

 

 

근데 이렇게 풀면 코드는 통과하지만 효율성에서 실패한다,,

 

그래서 세번째로 푼 방법

const findIncompletion = (participants, completions) => {
    participants.sort();
    completions.sort();
    return participants.find((it, index) => it !== completions[index]);
}

participants를 정렬시키고

completions도 정렬시키고

participants에서 요소를 찾는데 completions이랑 같지 않은 요소를 찾아주면 된다.

find()를 해주면 발견하는 즉시 요소 찾는걸 끝내기 때문에 동명이인 있는 조건도 처리할 수 있다.