[코테] 문제풀기 #5

Yuno·2021년 7월 1일

코딩테스트

프로그래머스 문제풀기

목록 보기

6/8

튜플

(a1, a2, ... an)라는 튜플은
{{a1},{a1,a2},....{a1,a2,...,an}} 이러한 집합의 구성으로 표현할 수 있습니다.

튜플은,

중복된 원소가 있을 수 있습니다. (2,1,3,2)
원소에 순서가 있으며, 순서가 다르면 다른 튜플입니다. (1,2,3) ≠ (1,3,2)
원소의 개수는 유한합니다.

튜플을 집합으로 표현하면,

튜플이 (2,1,3,4) 일때,
{{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} 와 같이 표현할 수 있습니다.

이때, 집합은 원소의 순서가 바뀌어도 상관없으므로
{{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
{{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}
도 가능합니다.

튜플을 표현하는 집합이 담긴 문자열 s가 주어질 때, s가 표현하는 튜플을 반환합니다.

튜플은 순서가 있으나, 집합은 순서가 없고 이해가 안되기 시작합니다...

이해가 안되기 시작

튜플을 집합으로 어떻게 변경하는지 살펴보면 됩니다.
순서가 있는 튜플 (2,1,3,4)는 집합 {{2},{2,1},{2,1,3},{2,1,3,4}}로 표현할 수 있습니다.

튜플의 첫번째 원소가 집합의 원소가 됩니다. (a1, .... ) => {{a1}, ...}

다음 원소들은 이전 집합 원소에 추가하여, 집합의 원소가 됩니다.
(a1,a2, .... ) => {{a1},{a1,a2}, ...}

위의 설명, (a1, a2, ... an) => {{a1},{a1,a2},....{a1,a2,...,an}}과 동일합니다.

즉, 집합의 원소들은 순서가 다르더라도, 순서 있는 튜플 하나를 표현합니다.
{{a1,a2},{a1}} 이든지, {{a1},{a1,a2}} 이든지 표현하는 튜플은 (a1,a2) 입니다.

알고 보면, 왜 이해 못했지? 생각할 정도로 문제에 그대로 있는데, 왜 항상 이해가 안될까요

이해가 쉽게 안된 이유는 집합 내부 원소들도, 순서가 없기 때문인 것 같습니다.

문제의 입출력 예시 2번에서 "{{1,2,3},{2,1},{1,2,4,3},{2}}" 이러한 예시는,
3과 4의 길이를 가진 원소의 내부 원소들도 순서가 없습니다.

기존 2,1에서 추가된 값이 3이기 때문에, 튜플의 세 번째 순서 값은 3입니다.

풀이

집합 원소의 길이가 짧은순으로 정렬합니다.
prev와 find()를 통해, 집합의 원소에 새로 추가된 값을 찾습니다.

function solution(s) {
    const result = [];
    
    const sortByLength = (a,b) => a.length - b.length;
    const sets = parseArray(s).sort(sortByLength);

    let prev = [];
    for (const set of sets) {
        const newValue = set.find(v => !prev.includes(v));
        prev = set;
 
        result.push(newValue);
    }   

    return result;
}

정규식과 split()을 활용해 문자열로 표현된 집합을 배열로 변환합니다.

function parseArray(s) {
    const result = [];
    const reg = /(?<=}),(?={)/;

    for (const set of s.slice(1,-1).split(reg)) {
        result.push(set.slice(1,-1).split(',').map(v=> parseInt(v)));
    }

    return result;
}