완주하지 못한 선수(1)

GY·2021년 7월 3일
js알고리즘자바스크립트프로그래머스
0

알고리즘 문제 풀이

목록 보기
7/92
post-thumbnail

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.마라톤에 참여한 선수들의 이름이 담긴 배열 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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

결과물

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

과정

계획

  1. 두 배열의 중복값 찾기
  2. 중복값을 배열에서 삭제하기
  3. 남은 값을 리턴하기



1. 두 배열의 중복값 찾기

match, concat, filter,map 함수들 중 하나를 사용할 수 있을 것 같다.

//[배운점 정리 참고] 간단히 participant와 completion배열중 같은 중복값만 찾는 코드
var part=['leo','kiki']
var com = ['leo']
var same = part.map(function(ma){
    if(part==com){return part}
})
                    
var result=part.filter(part=>part==com);

result
["leo"]


//중복되지 않은 값을 리턴하는 코드
var result2=part.filter(part=>part!=com)

result2
["kiki"]


오류 : 순서가 다르면 중복값을 찾을 수 없는 것 같다.

function solution(participant, completion) {
    
    var answer = participant.filter(participant=>participant!=completion);
    return answer;
}

입력값 〉	["leo", "kiki", "eden"], ["eden", "kiki"]
기댓값 〉	"leo"
실행 결과 〉	실행한 결괏값 ["leo","kiki","eden"]이(가) 기댓값 "leo"와(과) 다릅니다.

즉, 순서가 달라도 값을 각각 비교하거나,
값들의 순서를 똑같이 정렬해주는 것이 필요하다.
다만 sort()로 정렬해도 결과는 똑같다.

2. 두 배열의 차집합 찾기

//참가했고 완주한 선수
var participant =["leo", "kiki", "eden"]

var completion=["eden", "kiki"]

var intersection=participant.filter(x=>completion.includes(x))
//completion에 포함되어 있는 원소들만 participant 배열에서 골라 반환한다.

intersection
(2) ["kiki", "eden"]

//참가했으나 완주는 못한 선수
var difference=participant.filter(x=>!completion.includes(x))
//completion에 포함되어 있지 않은 원소를 participant배열에서 골라 반환한다.

difference
["leo"]

3. 동명이인

//동명이인이 있는 경우 참가/완주 모두 한 선수
var participant=["mislav", "stanko", "mislav", "ana"]
var completion=["stanko", "ana", "mislav"]
var intersection=participant.filter(x=>completion.includes(x))
var difference=participant.filter(x=>!completion.includes(x))

intersection
(4) ["mislav", "stanko", "mislav", "ana"]
//mislav가 하나만 반환되어야 한다.

Array.from(new Set(intersection))
(3) ["mislav", "stanko", "ana"]


difference
[]
  1. 참가/완주한 선수는 mislav 두 명 모두가 반환된다.
  2. 참가했지만 완주하지 못한 선수는 반환되지 않는다.

동명이인인 mislav 중 한 명만 반환되면 된다.
(둘 중 누가 완주하지 못한 선수인지는 구분할 수 없으므로)
즉, sort()로 정렬한다음 연속으로 같은 요소가 나오면 splice()로 둘 중 하나를 삭제해버리는게 가장 간단할 것 같다.

intersection.sort()
(4) ["ana", "mislav", "mislav", "stanko"]

for(i=0;i<intersection.length;i++){
    if(intersection[i]==intersection[i+1]){
        intersection.splice(i,1)}
}

intersection
(3) ["ana", "mislav", "stanko"]

위의 경우 차집합의 원소는 없다.완주하지 못한 선수는 mislav인데, 참가 및 완주한 선수의 이름도 mislav이기 때문에 같은 이름으로 처리되기 때문이다.
이럴 경우에 한해 중복값을 찾아낸 다음 정답으로 리턴하도록 하면 어떨까?

if(difference.length==0){
  var si = intersection.sort()


for(i=0;i<intersection.length;i++){
    if(si[i]==si[i+1]){
        var answer=si.slice(i,i+1)}
}
}
answer
["mislav"]

정리해보자

function solution(participant, completion) {
	var intersection=participant.filter(x=>completion.includes(x))
	var difference=participant.filter(x=>!completion.includes(x))
    if(difference.length==0){
        var si = intersection.sort()


        for(i=0;i<intersection.length;i++){
           if(si[i]==si[i+1]){
           var answer=si.slice(i,i+1)}
}
}
    else{
        var answer=difference
    }

    return answer;
}

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

콘솔창에선 맞게 출력되는데, 프로그래머스에서는 오답으로 나온다.
결국 그냥 for문으로 일일히 비교하는 방법밖엔 없는걸까?

for문

function solution(participant, completion) {
	for (i=0;i<participant.length;i++){
    for(j=0;j<length;j++){
        if(participant[i]==completion[j]){
            participant.splice(i,1)
            var answer=participant
            }
                if(participant[0]==participant[1]){
                    participant.pop();
                    var answer = participant               
                    }
    
}
}
    return answer;
}

sort+for 문

//예시 1
var participant = ["marina", "josipa", "nikola", "vinko", "filipa"]
var pl=participant.length;
var completion=["josipa", "filipa", "marina", "nikola"]

var sp=participant.sort();
var sc=completion.sort();
console.log(sp)
console.log(sc)
for(i=0;i<pl;i++){
   if(sp[i]!=sc[i]){
console.log('index'+i+',',answer);
   break
    }



}
VM3373:7 (5) ["filipa", "josipa", "marina", "nikola", "vinko"]
VM3373:8 (4) ["filipa", "josipa", "marina", "nikola"]
VM3373:11 index4, vinko



//예시2
var participant = ["leo", "kiki", "eden"]
var pl=participant.length;
var completion=["eden", "kiki"]
var cp=[];
var sp=participant.sort();
var sc=completion.sort();
console.log(sp)
console.log(sc)
for(i=0;i<pl;i++){
   if(sp[i]!=sc[i]){
var answer=sp[i]
console.log('index'+i+',',answer);
   break
    }



}
VM3414:7 (3) ["eden", "kiki", "leo"]
VM3414:8 (2) ["eden", "kiki"]
VM3414:12 index2, leo



//동명이인
var participant = ["mislav", "stanko", "mislav", "ana"]
var pl=participant.length;
var completion=["stanko", "ana", "mislav"]
var cp=[];
var sp=participant.sort();
var sc=completion.sort();
console.log(sp)
console.log(sc)
for(i=0;i<pl;i++){
   if(sp[i]!=sc[i]){
var answer=sp[i]
console.log('index'+i+',',answer);
   break
    }



}
VM3419:7 (4) ["ana", "mislav", "mislav", "stanko"]
VM3419:8 (3) ["ana", "mislav", "stanko"]
VM3419:12 index2, mislav

이걸 토대로 답을 작성해보자.

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

도대체가..어려운 문제가 아닌것같은데 계속 돌고 돌았다.
그 과정에서 많은 걸 배울 수 있었지만!

Review

filter()

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/filter
filter() 메서드는 주어진 함수의 테스트를 통과하는 모든 요소를 모아 새로운 배열로 반환한다.
즉, 특정 조건에 부합하는 배열의 모든 값을 배열 형태로 리턴한다.

//예시
const words = ['spray', 'limit', 'elite', 'exuberant', 'destruction', 'present'];

const result = words.filter(word => word.length > 6);

console.log(result);
// expected output: Array ["exuberant", "destruction", "present"]


//예시2
function isBigEnough(value) {
  return value >= 10;
}

var filtered = [12, 5, 8, 130, 44].filter(isBigEnough);
// filtered 는 [12, 130, 44]

이전에 작성해두었던 주요 배열 함수 10가지 참고 


// Q6. make an array of enrolled students
{
    const result = students.filter((student) => student.enrolled);
//==>:aero function:각각의 학생이 전달이되면, 등록되었는지 확인하고, 등록된 학생들만 출력한다
}





### map()
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/map
map() 메서드는 배열 내의 모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환한다

```jsx
var numbers = [1, 4, 9];
var doubles = numbers.map(function(num) {
  return num * 2;
});
// doubles는 이제 [2, 8, 18]
// numbers는 그대로 [1, 4, 9].

includes()

includes() 함수는 배열이 특정값을 포함하고 있는지의 여부를 boolean 값으로 반환한다.

출처: https://hohoya33.tistory.com/134 [개발 메모장]

reduce()

https://brunch.co.kr/@swimjiy/15
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce
Array.includes(value) : value가 Array배열에 존재하는지 판단해 true, false를 반환한다.

let arr = [3, 1, 3, 5, 2, 4, 4, 4];
arr.reduce((acc,curr) => acc.includes(curr) ? acc : [...acc,curr],[]); 
// [2, 1, 5, 6, 3]


출처: https://hohoya33.tistory.com/132 [개발 메모장]
//배열의 중복 항목 제거
참고: Set과 Array.from()을 사용할 수 있는 환경이라면, let orderedArray = Array.from(new Set(myArray));를 사용해 중복 요소를 제거할 수도 있습니다.

let arr = [1, 2, 1, 2, 3, 5, 4, 5, 3, 4, 4, 4, 4];
let result = arr.sort().reduce((accumulator, current) => {
    const length = accumulator.length
    if (length === 0 || accumulator[length - 1] !== current) {
        accumulator.push(current);
    }
    return accumulator;
}, []);
console.log(result); //[1,2,3,4,5]

두 배열 중복 제거 방법 참고

https://hianna.tistory.com/422
https://hohoya33.tistory.com/134

배열 교집합

filter와 includes을 사용하여 두 배열에 포함된 동일한 요소를 확인 할 수 있습니다.

includes() 함수는 배열이 특정값을 포함하고 있는지의 여부를 boolean 값으로 반환합니다.

let arrA = [1, 4, 3, 2];
let arrB = [5, 2, 6, 7, 1];

arrA.filter(it => arrB.includes(it)); // returns [1, 2]


출처: https://hohoya33.tistory.com/134 [개발 메모장]

Set

set (data object)로 배열내 중복값 없애기 (유니크 값만 남기기)

splice

array.splice(start[, deleteCount[, item1[, item2[, ...]]]])

매개변수

start : 배열의 변경을 시작할 인덱스
deleteCount (Optional) : 배열에서 제거할 요소의 수
item1, item2, ... (Optional) : 배열에 추가할 요소

교집합

https://stackoverflow.com/questions/1187518/how-to-get-the-difference-between-two-arrays-in-javascript

sort - 정렬

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

arr.sort([compareFunction])

매개변수

compareFunction (Optional) :정렬 순서 정의
생략하면 배열은 각 요소의 문자열 변환에 따라 각 문자의 유니 코드 코드 포인트 값에 따라 정렬된다. *원 배열이 정렬됨. 새 배열이 생성되지는 않는다.

다른 풀이를 하나씩 뜯어보며 공부하자.
https://muhly.tistory.com/58
1.for문으로 하나하나 비교하기(이렇게 하고 싶지는 않았는데..다른 방법을 찾고 싶었다.)
2.hash사용하기 (공부해보자!!)

profile
GY
Why?에서 시작해 How를 찾는 과정을 좋아합니다. 그 고민과 성장의 과정을 꾸준히 기록하고자 합니다.
이전 포스트

[CSS]반응형 네비게이션 바 만들기

다음 포스트

하샤드 수

0개의 댓글