[코딩테스트 연습] 완주하지 못한 선수_Level.01
코딩테스트/JavaScript

[코딩테스트 연습] 완주하지 못한 선수_Level.01

_2019.04.15.MON._

 

JavaScript 코드 자체를 읽는데는 문제가 없지만,  직접 코딩한지 오래 되었고 또 책으로만 보니 이해는 가지만

실제 코딩실력이 느는 것 같지 않아 'Programmers'라는 사이트(https://programmers.co.kr/)에서 제공하는

코딩테스트 연습문제를 통해 공부를 하기로 하였다.

 

역시나 직접하지 않았더니 결과는 암울하다:(.. 괜찮아 살아 남는게 이기는 거니 열심히 하다보면 늘겠지!

 

 

[문제 설명]

 

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

[제한 사항]

  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.

[입출력 예]

participant completion return
[leo, kiki, eden] [eden, kiki] leo
[marina, josipa, nikola, vinko, filipa] [josipa, filipa, marina, nikola] vinko
[mislav, stanko, mislav, ana] [stanko, ana, mislav] mislav

 

[입출력 예 설명]

 

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

 

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

 

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

 

문제를 접했을 때 나는 우선 이렇게 생각했다.

 

  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
    • 1<=participant<=100,000
  • completion의 길이는 participant의 길이보다 1 작습니다.
    • completion.length = (participant.length-1)
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
    • 참가자 이름 배열의 이름들이 모두 영어 소문자인지 판별을 해야할 것 같다.
    • forEach문을 사용하여 만약 이름을 모두 .toLowerCase()를 이용해 소문자로 바꾸었을 때와 같은지 비교
  • 참가자 중에는 동명이인이 있을 수 있습니다.
    • 딱히 크게 신경을 쓰지 않았다. 동명이인이라 걸러내야 하면 따로 코드가 필요하지만 아니면 필요가 없다고 생각했다.

 

아래는 내가 작성한 오답 코드이다.

[작성한 코드]

function solution(participant, completion) {
    
    var answer = '';    //완주하지 못한 선수 이름
    var completionLength = 0;   //완주한 선수들 인원수 파악에 사용
    
    if( 1<= participant.length <= 100000 ){   //만약 참가자가 1명보다 많고 100000명보다 적을 때
        console.log("인원 적절! Go ahead!");   // 옳으면 진행
    }else{
        alert("인원 부적절! Error!");    //아니라면 코드 멈춤
        return ;
    }
    
    completionLength = participant.length - 1;    //완주한 선수의 수는 참가자 수보다 1명 적다
    
    participant.forEach(function(element01){
        var lower = element01.toLowerCase();   //선수들 이름의 대소문자 판별에 사용
        if( element01 != lower ){
            alert("선수들 이름의 대소문자를 확인하세요!\n\n영문자인 경우 소문자만 가능합니다.");
            return false;
        }else{
            console.log("선수들 이름 모두 소문자! 완벽!" + element01);
            return true;
        }
    });
    
    completion.forEach(function(element02){
        if( participant.indexOf(element02)!= -1 ){
            
            console.log("이름이 완주자 목록에 있다! Completion!");
    
        }else{
            
            answer = element02;
            console.log("이름이 완주자 목록에 없다! Didn't completion!" + answer);
            
        }
    });
    
    return answer;
}

solution(["leo", "kiki", "eden"], ["eden", "kiki"]);
solution(["marina", "josipa", "nikola", "vinko", "flipa"], ["marina", "josipa", "nikola", "flipa"]);
solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]);

 

 

[실행 결과]

더보기
테스트 1
입력값 〉 ["leo", "kiki", "eden"], ["eden", "kiki"]
기댓값 〉 "leo"
실행 결과 〉 실행한 결괏값 ''이(가) 기댓값 'leo'와(과) 다릅니다.
출력 〉 인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!leo
선수들 이름 모두 소문자! 완벽!kiki
선수들 이름 모두 소문자! 완벽!eden
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!marina
선수들 이름 모두 소문자! 완벽!josipa
선수들 이름 모두 소문자! 완벽!nikola
선수들 이름 모두 소문자! 완벽!vinko
선수들 이름 모두 소문자! 완벽!flipa
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!mislav
선수들 이름 모두 소문자! 완벽!stanko
선수들 이름 모두 소문자! 완벽!mislav
선수들 이름 모두 소문자! 완벽!ana
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!leo
선수들 이름 모두 소문자! 완벽!kiki
선수들 이름 모두 소문자! 완벽!eden
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
테스트 2
입력값 〉 ["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]
기댓값 〉 "vinko"
실행 결과 〉 실행한 결괏값 ''이(가) 기댓값 'vinko'와(과) 다릅니다.
출력 〉 인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!leo
선수들 이름 모두 소문자! 완벽!kiki
선수들 이름 모두 소문자! 완벽!eden
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!marina
선수들 이름 모두 소문자! 완벽!josipa
선수들 이름 모두 소문자! 완벽!nikola
선수들 이름 모두 소문자! 완벽!vinko
선수들 이름 모두 소문자! 완벽!flipa
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!mislav
선수들 이름 모두 소문자! 완벽!stanko
선수들 이름 모두 소문자! 완벽!mislav
선수들 이름 모두 소문자! 완벽!ana
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!marina
선수들 이름 모두 소문자! 완벽!josipa
선수들 이름 모두 소문자! 완벽!nikola
선수들 이름 모두 소문자! 완벽!vinko
선수들 이름 모두 소문자! 완벽!filipa
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
테스트 3
입력값 〉 ["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]
기댓값 〉 "mislav"
실행 결과 〉 실행한 결괏값 ''이(가) 기댓값 'mislav'와(과) 다릅니다.
출력 〉 인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!leo
선수들 이름 모두 소문자! 완벽!kiki
선수들 이름 모두 소문자! 완벽!eden
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!marina
선수들 이름 모두 소문자! 완벽!josipa
선수들 이름 모두 소문자! 완벽!nikola
선수들 이름 모두 소문자! 완벽!vinko
선수들 이름 모두 소문자! 완벽!flipa
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!mislav
선수들 이름 모두 소문자! 완벽!stanko
선수들 이름 모두 소문자! 완벽!mislav
선수들 이름 모두 소문자! 완벽!ana
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
인원 적절! Go ahead!
선수들 이름 모두 소문자! 완벽!mislav
선수들 이름 모두 소문자! 완벽!stanko
선수들 이름 모두 소문자! 완벽!mislav
선수들 이름 모두 소문자! 완벽!ana
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!
이름이 완주자 목록에 있다! Completion!

 

보다시피 완전 망했다.

결과를 보면 코드가 한 함수에 한 결과가 나오는 것이 아니라 내가 적은 모든 배열들을 다 검사한다.

그리고 웃긴게 완주자 목록에 있는 사람은 찾으면서 없는 애는 반환하지 않는다.

completion.forEach(function(element02){
        if( participant.indexOf(element02)!= -1 ){
            
            console.log("이름이 완주자 목록에 있다! Completion!");
    
        }else{
            
            answer = element02;
            console.log("이름이 완주자 목록에 없다! Didn't completion!" + answer);
            
        }
    });

위 코드에서 else문은 전혀 움직이지 않는 것이다.

또한 전체 코드가 반복되는데 왜 그런지 모르겠다. 더 고민해봐야 될 듯...

 

우선은 시간이 없어 다른 사람의 해설을 보았다.

 

 

 

다른 사람들은 크게 2가지 방법으로 문제를 해결하였다.

 

1. sort()함수 이용

2. hash 사용

 

1. sort()함수 이용

//출처: https://code-reading.tistory.com/67

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

 

//출처: https://programmers.co.kr/learn/courses/30/lessons/42576/solution_groups?language=javascript
//MiReuLee

const solution = (p, c) => {
	p.sort();
   	c.sort();
    
    while(p.length){
    	let pp = p.pop();
        if(pp !== c.pop()){
        	return pp;
        }
    }
}

 

기타 다른 형식의 sort( )함수를 이용한 코드들도 있지만 우선 내 맘에 드는 것들 2개만 가져왔다.

 

이 분들 중 오류가 떴었던 분의 말에 의하면 참가자의 수가 더 많으니 참가자의 수만큼 반복문을 돌리면서

완주한 배열과 비교하려 하였는데 계속 undefined가 떴다고 한다.

 

왜냐하면 배열의 순서가 다른 상태에서 진행하여 구조적인 문제가 발생했기 때문이다.

 

그래서 각각의 배열을 정렬한 후 비교를 돌리니 정상적으로 출력되었다고 하였다.

 

 

 

2. hash 사용

 

//출처: https://programmers.co.kr/learn/courses/30/lessons/42576/solution_groups?language=javascript
//김나연, 김테스트

function solution(participant, completion) {
    const hash = {};

    for(let val of participant) {
      if(!hash[val]) hash[val] = 0;
      hash[val]++;
    }

    const result = completion.forEach(val => hash[val]--);

    for(let key in hash) if(hash[key]) return key;
}

 

//출처: https://programmers.co.kr/learn/courses/30/lessons/42576/solution_groups?language=javascript
//이화섭

function solution(participant, completion) {
    let ret = []
    let hashed = []
    participant.forEach(entry => {
        hashed[entry] = hashed[entry] ? hashed[entry] + 1 : 1        
    })
    completion.forEach(entry => {
        hashed[entry] = hashed[entry] - 1
    })

    for (var key in hashed) {
        if (hashed[key] >= 1) return key
    }
}

 

해시 읽었는데 또 까먹어서 적어본다.

 

해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 한다.

 

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시테이블(hash table)이라고 한다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 한다. 해시테이블의 기본 연산은 삽입, 삭제, 탐색(search)이다. 

 

사실 이 문제에 왜 hash를 많이 사용하는지 모르겠다.

1번 방법이 훨씬 쉽고 간편한데 말이다.( 그런데 그걸 못하다니 세상에 0)-< )

 

 

문제 하나 풀고나니 얼마나 코딩적 이해가 모자란지 확연히 보인다.

컴퓨터공학쪽을 전공하였지만.. 오늘 다시 한 번 이론과 실습은 다르단 것을 느낀다.

 

다음 문제는 더 잘 풀어야지!

'코딩테스트 > JavaScript' 카테고리의 다른 글

[코딩테스트 연습] 2016년_Level.01  (0) 2019.04.19
[코딩테스트 연습] K번째 수_Level.01  (0) 2019.04.15

    티스토리툴바