[PGS] 튜플 - Level 2

혜혜·2023년 8월 28일

PS

목록 보기

2/8

📚 문제 내용

셀 수 있는 수량의 순서 있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

(a1, a2, a3, ..., an)

튜플은 다음과 같은 성질을 가지고 있습니다.

중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)

원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)

튜플의 원소 개수는 유한합니다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 {, }를 이용해 표현할 수 있습니다.

{{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

{{2}, {2, 1}, {2, 1, 3}, {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}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한 사항]

s의 길이는 5 이상 1,000,000 이하입니다.
s는 숫자와 {, }, , 로만 이루어져 있습니다.
숫자가 0으로 시작하는 경우는 없습니다.
s가 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

[입출력 예]

s	result
"{{2},{2,1},{2,1,3},{2,1,3,4}}"	[2,1,3,4]
"{{1,2,3},{2,1},{1,2,4,3},{2}}"	[2,1,3,4]
"{{20,111},{111}}"	[111,20]
"{{123}}"	[123]
"{{4,2,3},{3},{2,3,4,1},{2,3}}"	[3,2,4,1]

입출력 예에 대한 설명

입출력 예 #3

(111,20)을 집합 기호를 이용해 표현하면 {{111},{111,20}}이 되며, 이는 {{20,111},{111}}과 같습니다.

입출력 예 #4

(123)을 집합 기호를 이용해 표현하면 {{123}} 입니다.

입출력 예 #5

(3, 2, 4, 1)을 집합 기호를 이용해 표현하면 {{3},{3,2},{3,2,4},{3,2,4,1}}이 되며, 이는 {{4,2,3},{3},{2,3,4,1},{2,3}}과 같습니다.

✍️ 문제 분석

처음에 생각한 풀이

중괄호를 소괄호로 변경(정규식으로)

{ → [
} → ]
배열의 배열이 만들어짐

배열 길이에 따라 정렬
정렬한 배열 첫 번째 원소를 베이스로 삼음
result 배열에 하나씩 push

최종 풀이

중괄호를 굳이 소괄호로 변환할 필요 없이, 배열의 배열 형태로 변경
배열 길이에 따라 정렬
정렬한 배열 첫 번째 원소를 베이스로 삼음
result 배열에 하나씩 push

💻 내 코드

function solution(s) {
    let str = s;
    str = str.slice(1, -1);
    
    let arr = str.split('},{');
    arr = arr.map(el => el.replace(/[{}]/g, ''));
    arr = arr.map(element => JSON.parse(`[${element}]`));
    arr.sort((a, b) => {
        return a.length - b.length;
    });
    
    const result = arr[0];
    
    if(arr.length < 2) return result;
    
    for(let i = 1; i < arr.length; i++){
        for(let j = 0; j < arr[i].length; j++){
            if(!result.includes(arr[i][j])) {
                result.push(arr[i][j]);
                break;
            }
        }
    }
    
    return result;
}

"{{2},{2,1},{2,1,3},{2,1,3,4}}" 형태로 들어오는 문자열에서 맨 앞뒤 중괄호를 잘라냄 → "{2},{2,1},{2,1,3},{2,1,3,4}"
각 요소 안에도 ,가 있기 때문에, ,로 split은 못 하고, }, {로 split 해야 됨 → ["{2", "2,1", "2,1,3", "2,1,3,4}"]
정규식을 통해 각 문자열 요소에 {나 }가 있으면 제거 → ["2", "2,1", "2,1,3", "2,1,3,4"]
구문 분석을 해주는 함수인 JSON.parse()를 이용해, 각 문자열을 풀어 배열에 넣어주고, 배열의 배열을 만듦 → [[2], [2,1], [2,1,3], [2,1,3,4]]
길이가 짧은 순으로 정렬하기 위해 sort() 함수 사용 → [[2], [2,1], [2,1,3], [2,1,3,4]]
result 배열의 기본값을 이 정렬된 배열의 0번째 요소로 삼음
(즉, result는 현재 [2])
만약 배열 길이가 1이라면, 이 result 배열을 그대로 반환
배열 길이가 1보다 크다면, 1부터 차례로 돌면서 result 배열에 없는 요소를 차례로 push 해주면 됨

📌 다른 풀이

function solution(s) {
    return JSON.parse(s.replace(/{/g, '[').replace(/}/g, ']'))
    .sort((a, b) => a.length - b.length)
    .reduce((arr, v, n) => {
        if (n) {
            return arr.concat(v.filter(f => !arr.includes(f)));
        }
        return v;
    }, []);
}

앗... 내가 처음에 생각했던 방식인데 나는 split() 함수로 배열을 쪼갤 생각이었어서 굳이 중괄호를 소괄호로 바꾸는 의미가 없을 것 같아서 이렇게 풀지 못했는데 생각해 보니까 JSON.parse() 사용하면 배열의 배열로 변환된다...🥹
reduce()의 첫 번째 인자는 콜백 함수고, 두 번째 인자는 배열의 초기값
콜백 함수의 각 인자는 콜백의 반환값을 누적할 배열인 arr와 현재 요소를 나타내는 v, 현재 반복 인덱스를 나타내는 n으로 이루어져 있다.
여기서의 arr는 내 코드의 result 배열이라고 생각하면 될 것 같다.
현재 요소 v에서 arr에 포함되지 않는 요소만 필터링해서 배열로 만들고, 그걸 concat()으로 원래 arr에 이어주면, 최종적으로 만들어야 하는 배열이 완성된다.

const tupleFrom = (str) =>
  str.slice(2, -2).split('},{')
    .map((it) => toNumbers(it))
    .sort(accendingByLength)
    .reduce((acc, cur) =>
      [...acc, ...cur.filter((it) => !acc.includes(it))], []);

const toNumbers = (str) => str.split(',').map(it => Number(it));

const accendingByLength = (arr1, arr2) => arr1.length - arr2.length;

const solution = (s) => tupleFrom(s);

이 코드에서는 맨 앞뒤에서 한 글자씩이 아닌 두 글자씩을 지우고, 그 다음에 },{으로 나눈다.
이렇게 보니 이 방법이 더 깔끔한 것 같음...
이러면 이제 ,로만 split 해도 문제 없이 배열이 쪼개진다.
sort()와 reduce()는 직전 코드와 유사하게 사용한 것 같다.
reduce()를 잘 써야 알고리즘을 잘할 것 같은데 아직도 너무 어렵다...
함수를 따로따로 작성한 게 깔끔해서 보기 좋았던 코드

✨ 새롭게 알게 된 점

forEach()와 map()의 차이

forEach()과 map() 둘 다 배열을 순회하면서 인자로 받은 콜백 함수를 실행하지만,
forEach()는 원본 배열을 변경시키지 않고 항상 undefined를 반환하는 반면,
map()은 해당 콜백 함수를 수행한 새로운 배열을 반환한다!
공부 해도 해도 헷갈리는 개념... 언젠가 완벽히 습득하게 되는 날이 올 거야...😂

정규표현식 OR 표현법

{ 또는 }면 잡아주는 정규식이 필요했는데, []로 or를 표현할 수 있다는 것을 알게 되었음
replace('{', '').replace('}', '') 이렇게 작성하지 말고, replace(/[{}]/g, '') 이렇게 작성해 주면 한 번에 {나 }를 찾아낼 수 있다!

return 값에 따른 sort() 함수 동작

sort() 함수는 인자로 들어온 함수의 return 값에 따라 정렬 방식이 달라진다.
인자로 들어온 함수의 파라미터 a, b에 대하여,
return 값이 0보다 작으면 a < b 로 정렬하고,
return 값이 0이면 순서를 바꾸지 않으며,
return 값이 0보다 크면 b < a로 정렬한다.
sort()의 인자로 넣을 함수를 적절히 작성하는 연습을 하자!

문제를 풀 때 2중 for문을 reduce() 등으로 변환 가능한지에 대해 고민해 보자...!