Skip to main content

작성일 : 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); // 문자열을 숫자로 변환
  1. String 메서드
replace(); // 문자열 치환
split(); // 문자열 분할
  1. Array 메서드
map(); // 배열 변환
sort(); // 배열 정렬
  1. Set 객체
setA.has(); // 원소 존재 확인
setA.add(); // 원소 추가

시간 복잡도​

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

공간 복잡도​

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