[프로그래머스] 해시 - "완주하지 못한 선수" 문제 풀이

오늘은 프로그래머스에서

해시 테마의 "완주하지 못한 선수" 문제 풀이를 통해

알고리즘 공부를 해볼 것입니다.

문제 난이도는 Level 1이며, 저는 JavaScript로 코드를 구현할 것이므로

공부하시는데 참고해주세요~

 

 

 

해시 > 완주하지 못한 선수: Level 1 JavaScript

 

 

♣ 문제 설명

 

완주하지 못한 선수의 문제 설명은 아래와 같습니다.

함께 읽어보시면서 이해해보시죠!!

 

 

 

 

이해를 돕기 위해 문제의 설명을 풀어볼께요~

 

• Summary
  • 마라톤에 참여한 선수 중 단 한명의 선수만 완주하지 못하였다.
• Inputs
  • participant: 마라톤에 참여한 선수 이름 리스트 (문자열 배열)
  • completion: 완주한 선수 이름 리스트 (문자열 배열)
• Output: 완주하지 못한 선수의 이름

 

 

 

이해가 바로 되시나요?

결국 마라톤에 참여하였지만,

완주한 선수 리스트에 빠져있는 사람을 찾는 문제인 것 같습니다~

 

 

 

 

♣ 제한 사항

 

그럼 다음으로 제한 사항 살펴볼께요~

 

 

 

• 1 <= 총 마라톤 참여 선수 <= 100,000
• 1 <= 모든 참가자의 이름 길이 <= 20
• 참가자 중 같은 이름이 존재

 

이 제한 사항을 토대로 알고리즘 만들 때 참고하면 좋을 것 같아요~

 

 

 

 

♣ 입출력 예

 

다음은 입출력 예제입니다.

이 부분을 통해 문제 이해를 좀 더 확실하게 하고 갈 수 있어요.

 

 

예를 보면 이해가 더 잘 되시나요?

participant에 있지만, completion에 없는 이름이 return에 있네요~

 

입출력 예의 설명을 보시면서 이해를 더 해볼까요~

 

 

정말 간단한 설명입니다.

이와 같이 알고리즘도 간단해질 수 있을 것 같아요!!

 

 

충분한 예를 통한 이해가 되었다고 생각하고 

바로 알고리즘을 만들어볼까 합니다~

 

 

 

 

♣ 알고리즘 만들기

---

잘못된 알고리즘 만들기 사례

1. 완주자 리스트에 있는 순차적으로 완주자 이름을 선택한다.
2. 선택된 완주자 이름을 참여자 명단에서 찾는다.
3. 찾은 완주자 이름을 참여자 명단에서 제거한다.
4. 완주자 리스트를 모두 확인하였을 때, 참여자 명단에 남아있는 이름을 확인한다.

---

 

정말 간단하죠~

진짜 이번 문제는 알고리즘이 간단 명료하네요!!

 

하지만 알고리즘의 문제점이 있어요.

저희가 제한사항을 위에서 확인했던거 기억하시죠~

다시 보시면 100,000명이나 참가할 수 있어요.

그 참여자 명단에서 같은 이름 찾고, 완주자 이름을 제거하고 등등

엄청나게 과도한 시간이 소모될 알고리즘으로 보여요.

 

그럼 위 알고리즘과 유사하지만, 

보다 효율적인 알고리즘을 제시해볼께요~

 

 

 

 

---

1. 참여자 리스트와 완주자 리스트를 정렬한다.
2. 앞에서 순서대로 참여자 이름과 완주자 이름을 비교한다.
3. 같은 위치에 참여자 이름과 완주자 이름이 다르다면, 그 때의 참여자 이름이 완주하지 못한 선수의 이름이다.

---

 

뭔가 짧아진 것 같지만,

비교하는 것도 같고 찾는 것도 있어보이는데,

정렬 알고리즘을 통해서 보다 같은 이름 찾는 방법이 바뀌었어요.

위 알고리즘이 가장 속도가 빠른 알고리즘은 아니라고 생각해요.

이해를 돕기 위해 간단한 알고리즘을 만들어 본 것이예요.

혹시 더 좋은 알고리즘과 빠른 속도가 나올 것 같다면

댓글로 공유해주시면 많은 분들이 도움되지 않을까합니다.

 

 

그럼 위 알고리즘을 통해 코드로 구현해볼께요~

 

 

 

 

♣ 코드 구현

 

function solution(participant, completion) {
	// 1. 참여자 리스트와 완주자 리스트를 정렬한다.
    participant.sort();
    completion.sort();
    let answer = '';
    // 2. 앞에서 순서대로 참여자 이름과 완주자 이름을 비교한다.
    for(let i = 0; i < participant.length; i++) {
        if(participant[i] !== completion[i]) {
        	// 3. 같은 위치에 참여자 이름과 완주자 이름이 다르다면, 
        	//    그 때의 참여자 이름이 완주하지 못한 선수의 이름이다.
            answer = participant[i];
            break;
        }
    }
    return answer;
}

 

 

어떤가요?? 알고리즘이 찰떡같이 코드로 구현되어졌죠~

이번 해시 테마의 완주하지 못한 선수 문제는

해시를 활용하지 않았지만....

간단한 알고리즘을 통해 문제를 풀어봤어요~

 

 

 

 

다음에 해시를 활용한 문제 풀이도 다시 올려볼게요~

해시에 대해서도 공부해야하니깐요!!

 

그럼 2000.