작성일 : 2024.11.24

튜플 문제

문제 설명

중복되지 않는 원소를 가진 튜플을 집합으로 표현한 문자열에서, 원래의 튜플을 찾아내는 문제입니다.

튜플의 성질

1. 중복된 원소가 있을 수 있음 (예: (2, 3, 1, 2))
2. 원소의 순서가 중요함 (예: (1, 2, 3) ≠ (1, 3, 2))
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}}

제한 조건

1. 입력 문자열 s
   • 길이: 5 ≤ 길이 ≤ 1,000,000
   • 구성: 숫자, ', ', ','만 사용
   • 0으로 시작하는 숫자 없음
2. 튜플의 원소
   • 범위: 1 ≤ 원소 ≤ 100,000
   • 중복 없음
3. 반환 배열 길이: 1 ≤ 길이 ≤ 500

해결 코드

function solution(s) {
  var answer = [];
  let arrSet = [];
  let setA = new Set();
  let arrStr = s.replace("{{", "").replace("}}", "").split("},{");

  arrStr.sort((a, b) => a.length - b.length);

  for (let i = 0; i < arrStr.length; i++) {
    arrSet.push(arrStr[i].split(",").map((v) => parseInt(v)));
  }

  for (let k = 0; k < arrSet.length; k++) {
    for (let c = 0; c < arrSet[k].length; c++) {
      if (!setA.has(arrSet[k][c])) {
        setA.add(arrSet[k][c]);
        answer.push(arrSet[k][c]);
      }
    }
  }

  return answer;
}

알고리즘 설명

1. 문자열 전처리
   • 바깥쪽 중괄호 제거
   • 내부 집합들을 분리

   s.replace("{{", "").replace("}}", "").split("},{");
   

2. 길이 기준 정렬
   • 집합의 크기가 작은 것부터 정렬

   arrStr.sort((a, b) => a.length - b.length);
   

3. 배열 변환
   • 각 집합을 숫자 배열로 변환

   arrStr[i].split(",").map((v) => parseInt(v));
   

4. 튜플 구성
   • Set을 사용하여 중복 확인
   • 새로운 숫자를 발견할 때마다 튜플에 추가

중요 문법 요소

1. parseInt()

parseInt(v); // 문자열을 숫자로 변환

2. String 메서드

replace(); // 문자열 치환
split(); // 문자열 분할

3. Array 메서드

map(); // 배열 변환
sort(); // 배열 정렬

4. Set 객체

setA.has(); // 원소 존재 확인
setA.add(); // 원소 추가

시간 복잡도

• O(n * m): n은 집합의 개수, m은 가장 큰 집합의 크기

공간 복잡도

• O(n): n은 튜플의 크기