Algorithm - Programmers Problems (week 3)

Problem(lev.1) : 성격 유형 검사하기

• 나만의 카카오 성격 유형 검사지를 만들려고 합니다.
  성격 유형 검사는 다음과 같은 4개 지표로 성격 유형을 구분합니다. 성격은 각 지표에서 두 유형 중 하나로 결정됩니다.

지표 번호	성격 유형
1번 지표	라이언형(R), 튜브형(T)
2번 지표	콘형(C), 프로도형(F)
3번 지표	제이지형(J), 무지형(M)
4번 지표	어피치형(A), 네오형(N)

• 4개의 지표가 있으므로 성격 유형은 총 16(=2 x 2 x 2 x 2)가지가 나올 수 있습니다. 예를 들어, "RFMN"이나 "TCMA"와 같은 성격 유형이 있습니다.
• 검사지에는 총 n개의 질문이 있고, 각 질문에는 아래와 같은 7개의 선택지가 있습니다.
  • 네오형(N)과 어피치형(A)의 선택지 점수 예

선택지	성격 유형 점수
매우 비동의	네오형 3점
비동의	네오형 2점
약간 비동의	네오형 1점
모르겠음	어떤 성격 유형도 점수 추가 X
약간 동의	어피치형 1점
동의	어피치형 2점
매우 동의	어피치형 3점

• 질문마다 판단하는 지표를 담은 1차원 문자열 배열 survey와 검사자가 각 질문마다 선택한 선택지를 담은 1차원 정수 배열 choices가 매개변수로 주어집니다. 이때, 검사자의 성격 유형 검사 결과를 지표 번호 순서대로 return 하도록 solution 함수를 완성해주세요.
  • 1 ≤ survey의 길이 ( = n) ≤ 1,000
  • survey의 원소는 "RT", "TR", "FC", "CF", "MJ", "JM", "AN", "NA" 중 하나입니다.
  • survey[i]의 첫 번째 캐릭터는 i+1번 질문의 비동의 관련 선택지를 선택하면 받는 성격 유형을 의미합니다.
  • survey[i]의 두 번째 캐릭터는 i+1번 질문의 동의 관련 선택지를 선택하면 받는 성격 유형을 의미합니다.
  • choices의 길이 = survey의 길이
  • choices[i]는 검사자가 선택한 i+1번째 질문의 선택지를 의미합니다.
  • 1 ≤ choices의 원소 ≤ 7

choices	뜻
1	매우 비동의
2	비동의
3	약간 비동의
4	모르겠음
5	약간 동의
6	동의
7	매우 동의

Solution

function solution(survey, choices) {
    const typeScore = {
        'R': 0,'T': 0,'C': 0,'F': 0,
        'J': 0, 'M': 0, 'A': 0, 'N': 0
    };
    const typeOrder = [['R', 'T'], ['C', 'F'], ['J','M'], ['A','N']];
    for (let i = 0; i < survey.length; i++) {
        calculateTypeScore(survey[i], choices[i], typeScore);
    }
    const answer = typeOrder.reduce((types, currTypes) => {
        const oneType = currTypes[0];
        const otherType = currTypes[1];
        const finalType = typeScore[oneType] < typeScore[otherType] ? otherType : oneType;
        types += finalType;
        return types;
    }, '');
    return answer;
}

function calculateTypeScore(types, choice, typeScore) {
    const oneType = types[0];
    const otherType = types[1];
    switch (choice) {
        case 1:
            typeScore[oneType] += 3;
            break;
        case 2:
            typeScore[oneType] += 2;
            break;
        case 3:
            typeScore[oneType] += 1;
            break;
        case 4:
            break;
        case 5:
            typeScore[otherType] += 1;
            break;
        case 6:
            typeScore[otherType] += 2;
            break;
        case 7:
            typeScore[otherType] += 3;
            break;
    }
    return typeScore;
}

Problem(lev.2) : 뉴스 클러스터링

• 유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 "자카드 유사도"라는 방법을 찾아냈다.
  • 자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.
  • 이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다
  • 입력 형식
    • 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
    • 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
    • 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.
  • 출력형식
    - 입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

Solution

• 첫 번째 풀이 (다른 사람 풀이 참고)

function solution(str1, str2) {
    let strArr1 = [];
    let strArr2 = [];
    getStrPairs(str1, 0, strArr1);
    getStrPairs(str2, 0, strArr2);
    const regExp =  /[\{\}\[\]\/?.,;:|\)*~`!^\-_+<>@\#$%&\\\=\(\'\"0-9 ]/;
    strArr1 = strArr1.filter((str) => regExp.test(str) !== true).map((str) => str.toUpperCase());
    strArr2 = strArr2.filter((str) => regExp.test(str) !== true).map((str) => str.toUpperCase());
    const sameStrCount = getSameStrCount(strArr1, strArr2);
    const totalStrCount = strArr1.length + strArr2.length - sameStrCount;
    const similarity = strArr1.length === 0 && strArr2.length === 0 ? 65536 : (sameStrCount / totalStrCount) * 65536;
    return Math.floor(similarity);
}

function getStrPairs(str, strIndex, strPairs) {
    if (strIndex >= str.length - 1) {
        return strPairs;
    }
    const strPair = str.slice(strIndex, strIndex + 2);
    strPairs.push(strPair);
    return getStrPairs(str, strIndex + 1, strPairs);
}
function getSameStrCount(strArr1, strArr2) {
    let sameStrCount = 0;
    let copiedStrArr1 = [...strArr1];
    for (let i = 0; i < strArr2.length; i++) {
        const sameStrIndex = copiedStrArr1.indexOf(strArr2[i]);
        if (sameStrIndex !== - 1) {
            copiedStrArr1.splice(sameStrIndex, 1);
            sameStrCount++;
        }
    }
    return sameStrCount;
}

• 두 번째 풀이

function solution(str1, str2) {
    const regExp = /^[a-zA-Z]*$/;
    
    const getStrGroup = (str) => {
        const strGroup = [];
        for (let i = 0; i < str.length - 1; i++) {
            const curStr = str[i] + str[i + 1];
            if (regExp.test(curStr)) {
                strGroup.push(curStr.toUpperCase());
            }
        }
        return strGroup;
    }
    
    const str1Group = getStrGroup(str1);
    const str2Group = getStrGroup(str2);
    const smallStrGroup = str1Group.length > str2Group.length ? str2Group : str1Group;
    const largeStrGroup = smallStrGroup === str1Group ? str2Group : str1Group;
    let intersectionLength = 0;
    let unionLength = largeStrGroup.length;
    
    for (const currStr of smallStrGroup) {
        const strIndex = largeStrGroup.indexOf(currStr);
        if (strIndex !== -1) {
            largeStrGroup.splice(strIndex, 1);
            intersectionLength++;
        } else {
            unionLength++;
        }
    }
    
    const jaccadSimilarity = intersectionLength === 0 && unionLength === 0 ? 1 : intersectionLength / unionLength;
    const answer = Math.floor(jaccadSimilarity * 65536)
    return answer;
}

Problem(lev.2) : 가장 큰 수

• 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
  • 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
  • 제한사항
    • numbers의 길이는 1 이상 100,000 이하입니다.
    • numbers의 원소는 0 이상 1,000 이하입니다.
    • 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

Solution

function solution(numbers) {
    let answer = numbers.map((number) => '' + number).
    sort((a, b) => (b + a) - (a + b)).join('');
    return answer[0] === '0' ? '0' : answer;
}

• 핵심 내용

  1. 숫자를 문자로 변환함
  2. sort 메서드의 comparator 함수에서 두 수의 조합을 비교해서 숫자 배열을 정렬함
  3. join 메서드를 사용하여 모든 숫자를 합침
  4. 숫자가 0인 예외 경우를 고려함

• 두 수의 조합 예

• [6, 10, 2]을 정렬했을 경우,

b + a	a + b
610	106
102	210
102	210
62	26

• 정렬된 배열 : [ '6', '2', '10' ]

• [3, 30, 34, 5, 9]를 정렬했을 경우,

b + a	a + b
330	303
3034	3430
3034	3430
334	343
35	53
345	534
39	93
349	934
59	95

• 정렬된 배열 : [ '9', '5', '34', '3', '30' ]

Problem(lev.2) : 124 나라의 숫자

• 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.
  • 124 나라에는 자연수만 존재합니다.
  • 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
• 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

10 진법 수	124 나라 수
1	1
2	2
3	4
4	11
5	12
6	14

Solution

function solution(n) {
    let answer = '';
    const number124 = ['4', '1', '2'];
    while (n > 0) {
        answer = number124[n % 3] + answer;
        n = Math.floor((n - 1) / 3);
    }
    return answer;
}

10진법 수	몫	나머지
1	0	1
2	0	2
3	1	0
4	1	1
5	1	2
6	2	0

• 숫자 분석
  • 나머지 : 1 => 1, 2 => 2, 0 => 4
  • 몫 : 124 나라에서는 3 => 0, 6 => 1이어야함
    • 1 ~ 3의 몫이 0, 4 ~ 6 몫이 1, 7 ~ 9의 몫이 2가 되어야함
    • 몫은 (n - 1) / 3 이어야함

Problem(lev.1) : 완주하지 못한 선수

• 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.

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

Solution

function solution(participant, completion) {
    let answer = '';
    const marathon = new Map();
    participant.forEach((name) => {
        if (marathon.has(name)) {
            const prevCount = marathon.get(name);
            marathon.set(name, prevCount + 1)
        } else {
            marathon.set(name, 1);
        }
    });
    completion.forEach((name) => {
        const prevCount = marathon.get(name);
        marathon.set(name, prevCount - 1);
    });
    for (let name of marathon.keys()) {
        if (marathon.get(name) > 0) {
            answer = name;
        }
    }
    return answer;
}