프로그래머스 [튜플] - 구현, 정렬 Lv.2

구현, 정렬

• 문제가 제시한 요구사항에 맞게 구현하고, 정렬해서 해결 가능한 문제이다.

문제에서 제시한 튜플의 정의, 성질

• 튜플이란 특정한 순서를 따르는 수들의 모음을 의미한다.
• 정해진 순서가 있고, 순서가 다르면 서로 다른 튜플로 간주한다.
• 원소의 갯수는 유한개이다.
• n - 튜플은 n개의 원소를 가지는 튜플을 의미한다.

규칙성

• 먼저 문제에서 제시한 조건과 입출력 예시를 보면, 튜플을 부분집합으로 표현한다. 이때 부분집합은 순서가 중요하지 않다.
• 자세히 보면, 부분 집합 모두에 공통적으로 들어가는 원소가 있다. 튜플의 가장 맨 앞에 오는 원소일 수록 부분 집합 모두에 들어가 있을 확률이 높다.

풀이 과정

• 위의 규칙성을 이용하자.
• 튜플은 아래와 같은 형태를 띠고 있다.

"{{1,2,3},{2,1},{1,2,4,3},{2}}"

"{{20,111},{111}}"

즉 { }을 통해 집합이 구분되어 있고, 수를 포함한 요소는 ' , '로 구분이 되어있다. 따라서 먼저 아래와 같이 split 함수를 이용하여 수를 구분하자.

s = s.split(',')

["{{1","2","3}","{2","1}","{1","2","4","3}","{2}}"]

["{{20","111}","{111}}"]

생성된 배열의 형태를 잘 보면, 중간에 중괄호가 들어가있기는 하지만 각 수들이 ',' 를 기준으로 분리가 된 것을 확인할 수 있다.

• 해당 배열을 순회하며 각 요소에 대해 정규 표현식을 이용하여 숫자를 분리해내자.

   const regex = /[^0-9]/g;	
   
    const arr = []
   
    for(let i = 0; i < s.length; i++) {
        arr.push(Number(s[i].replace(regex, '')))
    }

return arr

[1,2,3,2,1,1,2,4,3,2]

[20,111,111]

위처럼 쉼표를 기준으로 분리가 된 중괄호가 섞인 요소들을 숫자만을 추출해내는데 성공했다.

• 이제 문제에서 제시한 튜플의 규칙성을 토대로, 부분집합에 많이 포함되어있는 순서대로 튜플을 만들자.
• Map을 이용하여 각 원소와 해당 원소의 갯수로 구성된 데이터를 만들었다.

   const tuple = new Map()
   arr.forEach(item => {
       const data = tuple.get(item) || 0
       tuple.set(item, data + 1)
   })

return [...tuple]

[[1,3],[2,4],[3,2],[4,1]]

[[20,1],[111,2]]

각 배열 요소의 첫 번째 인덱스에 해당하는 요소는 숫자, 두 번째 요소는 등장 횟수를 의미한다.
이를 등장 횟수를 기준으로 내림차순 정렬하고, 각 요소가 앞의 원소만을 남기도록 sort와 map 함수를 이용하자.

return [...tuple].sort((a, b) => b[1] - a[1]).map(item => item[0])

[2, 1, 3, 4]

[111, 20]

해결하는데 성공하였다.

후기

• 처음에 규칙성을 찾는데 헤멨었다. 도대체 이 부분집합으로부터 어떻게 튜플을 유추해내라는거지..? 라는 생각이 들었지만, 다시 보니 튜플의 맨 앞에 오는 요소일 수록 모든 부분집합에 해당 요소가 포함이 되어있는 것을 확인하고, 그럼 그 다음 요소는 거의 모든 부분집합에 포함되있나..? 하는 생각에 순서대로 확인해보니 정말 맞았다. 그 다음 다음 요소는 튜플의 순서에 비례해서 부분집합에 포함이 되어있었다.

• 규칙성만 찾으면, 그 다음은 시간 문제인 문제였다.