Programmers.js - 튜플

풀이

// 중복 x 튜플 -> {} 

function solution(s) {
    var answer = [];
    const arr = s.replace('{{','').replace('}}','').split('},{').sort((a,b) => a.length-b.length)
    arr.forEach((fixed) => {
        const numbers = fixed.split(',')
        numbers.forEach((number) => {
            if(!answer.includes(Number(number))) answer.push(Number(number))
        })
    })  
    return answer;
}

위의 방식으로 풀었고 최적화할 방법이 여럿 존재했음.
1. 문자열 파싱 : replace와 split을 동시에 사용하는 것은 불필요한 처리가 중복될 수 있다.
2. includes를 사용한 중복 체크 : includes는 매번 배열 전체를 순회하므로 시간복잡도가 O(n)이다, 이를 Set을 사용하여 중복 검사를 O(1)로 줄일 수 있다.

최적화 방안 :
1. 효율적인 파싱 : 정규 표현식 사용
2. 중복 체크를 위한 Set사용

function solution(s) {
    var answer = [];
    const set = new Set(); // 중복 체크를 위한 Set 생성
    
    // 1. 문자열에서 중괄호 제거 후, 집합을 배열로 변환하고 길이에 따라 정렬
    const arr = s.match(/\d+(,\d+)*/g).map(a => a.split(',').map(Number)).sort((a, b) => a.length - b.length);
    
    // 2. 각 배열을 순회하며 Set을 사용해 중복 없이 숫자 추가
    arr.forEach((fixed) => {
        fixed.forEach((number) => {
            if (!set.has(number)) {
                set.add(number);
                answer.push(number);
            }
        });
    });
    
    return answer;
}

성능 분석 :
1. 시간 복잡도 :

• 문자열 파싱은 정규식을 사용하여 O(n) 시간 복잡도를 가진다.
• 숫자 배열의 정렬은 O(m log m)이다. (m은 집합의 수)
• 숫자를 중복 없이 삽입하는 과정은 Set을 사용하여 O(1)으로 처리하므로, 삽입 과정의 시간 복잡도는 O(m)이다.

정규식 /\d+(,\d+)*/g 해부

1. / 와 / :

• 슬래시는 정규식의 시작과 끝을 나타낸다.
• 이 사이에 있는 것이 실제 패턴이다.
• 예 : /\d_/

2. /d :

• /d는 숫자를 의미한다. 0~9 사이의 숫자와 일치한다.

3. + :

• +는 바로 앞의 패턴이 한 번 이상 반복된다는 의미이다.

4. , :

• 쉽표는 그 자체를 의미한다. 쉼표 문자와 일치하는 패턴이다.
  5.* :
• *는 바로 앞의 패턴이 0번 이상 반복된다는 의미이다. 즉, ,\d+가 0번 이상 반복될 수 있다는 뜻이다.

6. (,\d+)* :

• 쉼표와 뒤따라오는 숫자가 0번이상 반복될 수 있음을 나타낸다.