[Programmers/Javascript] 완주하지 못한 선수

2021.07.04

 

드뎌 백준에서 프로그래머스로 넘어왔다.

나의 목표는 코테를 볼 수 있을 정도로 능력치를 끌어올리는 것이기 때문에 이제 프로그래머스로 전향!

 

Brainstorming

 

filter와 includes를 이용

이중for문을 이용해 completion과 participant 요소를 비교

reduce로 객체 만들어서 비교.

 

 

 

How to solve

 

 

1. completion 배열 안에 participant 요소가 존재하지 않으면 반환. (includes)

const answer = participant.filter(el => !completion.includes(el));

//큰 배열이 앞으로 가야함. 작은 배열 안에 큰 배열의 값이 있는지 확인해야하니까.
//includes로 가면 동명이인을 걸러내지 못함. 두개를 같은 값으로 보니까.
//그럼.. indexOf을 사용?

 

사용한 코드

- Array.filter

- Array.includes

 

결과

- 동명이인을 동일인으로 인식함.

 

 

 

2. completion 배열 안에 participant 요소가 존재하지 않으면 반환. (indexOf)

 

const answer = [];

for ( let i = 0; i < participant.length; i++ ) {
    if ( completion.indexOf(participant[i]) == -1 ) {
        answer.push(participant[i]);
    }
}

사용한 코드

- Array.indexOf

- for문

- if문

 

결과

- 동명이인을 동일인으로 인식함.

- 이미 비교한 값을 배열에서 제거하는 식으로 처리하면 될 것 같은데, p의 요소를 c에서 없애야 하는데 어떻게하지.?

 

 

 

3. 이중 for문으로 participant 각 요소와 completion 각 요소를 비교

 

const answer = [];

for ( let i = 0; i < participant.length; i++ ) {
    for (let j = 0; j < completion.length; j++ ) {
        if(participant[i] !== completion[j]) {
            answer.push(participant[i])
        }
    }
}

//이렇게 하면 participant랑 completion의 각 요소를 비교하기는 하지만 비교할 때마다 값이 다르면 그 값을 다 push하기때문에 안됨
//그래서 indexof를 쓴건데 흠. 동일한 값을 다른 값으로 인식하도록 어케할까.

 

- 나는 두 요소가 같지 않다면 answer이라는 배열에 일치하지 않는 요소를 push하라고 했지만 논리로 따지자면 particiapant[i]와 completion 전체를 비교해야하는 것이기 때문에 일치하지 않는 요소를 찾더라도 completion 요소 전체를 비교하게 됨.

- 동명이인 처리를 위해서 이미 비교한 요소를 completion에서 제거하기위해 shift같은 메서드를 생각함.

 

 

const answer = [];

for ( let i = 0; i < participant.length; i++ ) {
    let flag = true; //true, false로 판별하기!!!

    for (let j = 0; j < completion.length; j++ ) {
        if(participant[i] === completion[j]) {
            completion[j] = null;
            flag = false;
            break; //더이상 순환하지 않아도 되도록 빠져나오고
        }
    }

    if(flag) answer += participant[i]; //결과값은 for문 밖에서 넣는걸로.
}

 

- 타 풀이를 보니, participant와 completion 요소가 일치하면 c 배열의 요소값을 null로 바꾸고 flag라는 것을 만들어서 false값으로 만들어 줌. 

- 배열에서 요소를 없앨생각만 했지 바꿀생각은 못함. null로 바꾸면 동명이인 문제는 해결되겠군.

- flag 세워서 boolean값으로 두 배열 값이 일치하는지 체크하는거는 백준에서 풀었었는데 어떤 문젠지 기억이 안나네.

 

결과

- 정확성은 있지만 속도가 느림. 50점.

 

 

 

 

4. reduce로 객체 만들기

 

const p = participant.reduce( (acc, cur) => {

    acc[cur] = (acc[cur] | 0 ) + 1;
    return acc;

    // 프로퍼티 키가 최초로 등장하는 것이라면 1로 초기화.
    //acc[cur] = 0 + 1 

    // 프로퍼티 키가 존재하는 키라면, 해당 키에다가 1을 더 더해줘야 하니까.
    //acc[cur] = acc[cur] + 1; //acc[cur] += 1
},{});


const c = completion.reduce( (acc, cur) => {

    acc[cur] = (acc[cur] | 0 ) - 1;
    return acc;

},{});


for (const key in p) {
    for (const key2 in c) {
    p[key] == c[key2] ? true : false
    }
}

// 나는 두 객체를 구해서 entry를 매치시키려고 했는데, 그렇게 안하고 아예 value값을 빼버리는 방법도 있네.
// 그러면 안에서 또 for문을 돌려야하는구나.... flag세우는거.
// 아.. 객체는 이터러블이 아니구나. map은 이터러블이고.

 

차라리 reduce로 객체를 만들어서 각 key값이 몇번 나왔는지를 체크해서 비교하면 될 것 같다는 생각을 함.

나는 p과 c의 객체를 각각 구해서 각 entries를 비교할 생각했는데 그렇게 하면 3번에서 했던 방법을 다시 돌려야하기 때문에 아주 비효율적이 되어버림.

 

 

 

const acc = {};

participant.reduce( (acc, cur) => {

    acc[cur] = (acc[cur] | 0 ) + 1;
    return acc;

    // 프로퍼티 키가 최초로 등장하는 것이라면 1로 초기화.
    //acc[cur] = 0 + 1 

    // 프로퍼티 키가 존재하는 키라면, 해당 키에다가 1을 더 더해줘야 하니까.
    //acc[cur] = acc[cur] + 1; //acc[cur] += 1
},acc); // { mislav: 2, stanko: 1, ana: 1 }


completion.reduce( (acc, cur) => {

    acc[cur] = (acc[cur] | 0 ) - 1;
    return acc;

},acc); //{ mislav: 1, stanko: 0, ana: 0 }

// 외부에서 객체변수를 지정해서 들어와도 되네. (acc)
// 그럼 굳이 각각 변수 선언 안해줘도 되겠네


for (const answer in acc) {
    if(acc[answer] >= 1) return answer;
}

 

아예 객체 자체를 하나로 만들어서 거기에 직접 값을 변경하는 방법이 있었음.

그렇게 하면 각 메서드마다 변수에다 저장해 줄 필요가 없다.

 

그리고 한 객체에 변동값을 반영해버리니까 아주 간결하게 코드를 짤 수가 있음.

 

 

 

 

 

5. forEach 메서드로 해시테이블 만들기.

 

let hashed = []

participant.forEach(entry => {
    hashed[entry] = hashed[entry] ? hashed[entry] + 1 : 1
    //[mislav:2, stanko:1, ana:1]
})
completion.forEach(entry => {
    hashed[entry] = hashed[entry] - 1
    //[mislav:1, stanko:0, ana:0]
})

for (const answer in hashed) {
    if(hashed[answer] >= 1) return answer
}

 

- reduce 메서드를 사용한 것과 비슷한 로직.

- 배열 안에 값을 key : value형태로 넣음 (해시)

- '해시'라는 자료구조 문제이기도 했고 해당 자료구조를 공부하기 위해 찾아 본 코드인데 흠, 아직 이해가 잘 안된다.

이론도 무슨 말인지 알겠고 코드도 알겠는데 두개가 연결이 안된다. 이건 앞으로 문제를 풀면서 이해해가야 할 듯.

 

 

 

 

 

6. 배열의 요소를 1:1로 직접 비교

for ( let i = 0; i < participant.length; i++ ) {
    participant.sort()
    completion.sort()
    // sort는 원본배열을 바꿈

    if (participant[i] !== completion[i]) {
        return participant[i];
        // return을 통해 즉시 종료
    }
}

 

어떻게 배열을 직접비교하나했더니 sort로 두 배열을 정렬해서 각 인덱스에 존재하는 값이 같은지 확인한다. 아. 대박.

해당 비교가 가능한 이유는 completion의 값은 particiapant에 무조건 존재하니까.

내가 3번에서 이중 for문으로 각 인덱스로 불러와서 요소를 비교하려했던걸 sort를 사용해서 이렇게 간단하게 처리하다니.. 꺅. (근데 해당 코드도 시간초과가 난다)

 

근데 이해가 안되는게...

만약에 참가자가 a, b, c, d고 이 중에서 a, c만 완주를 했다면, 위 코드에 의하면 b만 완주를 못한 것으로 나오는데 그러면 틀린거아냐?

 

맞다. 하지만 위 코드가 통과될 수 있는 이유는 아래 조건 때문이다.

• completion의 길이는 participant의 길이보다 1 작습니다.

그렇구만.

 

---

 

해시테이블에 대해 공부하자.

그리고 문제 풀 때 항상 떠오른 방식이 있는데 그 방식을 어떻게 심화시킬지를 잘 정리하자.

 

 

++추가

오늘 아침(7/5)에 갑자기 생각난건데 해시테이블은 암호화기법으로도 많이 사용된다고 하니까 해당 input을 숫자로 단순화시켜서 input값이 뭔지 모르도록 만드는 것, 그건가??