[프로그래머스] 완주하지 못한 선수

Programmers : 완주하지 못한 선수

 

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

 

---

💬 문제

 정렬(sort) 이나  해시(hash) 에 대한 이해가 있다면, 충분히 풀 수 있는 문제였다.

해시에 대해 익숙하지 않다면, 아래 글을 참고해보길 바란다.

 

https://valueengine.tistory.com/55

[자료구조] 해시 (Hash)

 

💬 문제 설명

1. 마라톤에 참여한 사람들의 배열 participant와 완주한 사람들의 배열 completion이 주어진다.
   
   - 참가자의 수보다 완주자의 수가 1명 적습니다
   
   - 동명이인이 있을 수 있다
   
   
2. 완주하지 못한 선수의 이름을 출력해준다.

 

728x90

 

---

💡 입출력 예시

1번째 예시를 보면, 참가자 중 완주자 배열 completion에 없는 사람은 leo다.

3번째 예시를 보면, 참가자 중 mislav라는 이름의 동명이인이 2명 있고, 완주하지 못한 사람의 이름 역시 mislav다.

 

 

반응형

 

---

💻 풀이

이 문제는 총 2가지 방식으로 풀 수 있다.

🔑 풀이1 : 정렬 (sort)

• 배열 participant와 배열 completion은 정렬되어 있지 않다.
  
  - 인덱스순으로 비교하기 위해 sort()로 각 배열을 알파벳 순으로 정렬해준다.
  
  
• 단 1명만 완주하지 못했으므로, for문을 돌며 같은 인덱스의 값이 다른 경우를 찾아주고, 그 값을 출력해준다.

function solution(participant, completion) {
    participant.sort();
    completion.sort();
    
    for (let i=0; i < participant.length; i++) {
        if (participant[i] !== completion[i]) {
            return participant[i];
        }
    }
}

👣 예제를 참고한 풀이

3번째 예제를 통해 살펴본다면, 두 배열을 정렬했을 때 아래와 같다.

 

participant = [ 'ana', 'mislav', 'mislav', 'stanko' ]

completion = [ 'ana', 'mislav', 'stanko' ]

 

for문에서 인덱스 i가 2일때, participant의 값은 mislav이지만, completion의 값은 stanko이므로, mislav가 완주하지 못했다.

 

 

실행 결과와 채점결과는 다음과 같다.

 

 

 

---

🔑 풀이2 : 해시 (hash)

문제 카테고리가 해시이기에 해시로도 풀어보겠다.

이를 위해 해시 테이블도 만들어보겠다.  해시 테이블(hash table) 은 key와 value로 데이터를 저장하는 자료구조이다.

 

• reduce 메서드를 통해 completion을 해시 테이블로 바꿔준다.
  
  - 테이블에 완주한 선수가 있다면 기존 값(인원 수)에 +1을 해주고, 완주한 선수가 없다면 1을 할당해준다
  
  
• 참가자 중 단 1명만 완주하지 못했으므로 find 메서드를 사용해 찾아준다.
  
  - find는 조건을 만족하는(true라면) 첫 번째 원소의 값을 리턴해준다
  
  - 만약 참가자(key)가 완주한 선수 명단(table)에 있다면, 그 참가자 이름에 해당하는 인원 수를 1명 줄여준다
  
  - 만약 참가자(key)가 완주한 선수 명단(table)에 없다면, true로 find 메서드를 끝내고 그 사람을 출력해준다

function solution(participant, completion) {
    let table = completion.reduce(
        (table, key) => {
            table[key] = table[key] ? table[key] + 1 : 1;  // 완주한 선수가 table 명단에 있다면 +1, 없다면 1 할당
            return table;
        }, {}
    );
    return participant.find((key) => {
        if (table[key]) {
            table[key] = table[key] - 1;  // 완주한 선수 명단에 있다면, 그 수를 1명 빼주기
        } else {
            return true;  // 명단에 선수가 없다면, find() 메서드를 끝내고 그 요소를 반환
        }
    });
}

👣 예제를 참고한 풀이

3번째 예제를 통해 살펴본다면, 참가자 배열과 완주자 해시 테이블은 다음과 같다.

 

participant = ["mislav", "stanko", "mislav", "ana"]

table = { stanko: 1, ana: 1, mislav: 1 }

 

find 메서드를 통해 참가자 배열을 돌면서 mislav와 stanko가 차례대로 1명씩 줄어든다.

key가 mislav일 때, { stanko: 1, ana: 1, mislav: 0 }

key가 stanko일 때, { stanko: 0, ana: 1, mislav: 0 }

 

그러나 3번째 mislav를 완주자 테이블에서 찾으려했을 때 0명이기에 find 메서드는 끝나고, 그때의 요소인 mislav를 출력해준다.

 

 

실행 결과와 채점결과는 다음과 같다.

 

 

 

---

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️