[프로그래머스] 튜플 (Javascript, 2019 카카오 개발자 겨울 인턴십)

문제 링크

programmers.co.kr/learn/courses/30/lessons/64065

코딩테스트 연습 - 튜플

 

요즘 들어 c++을 지원하지 않는 코딩 테스트가 많이 보여 프로그래머스 문제를 자바스크립트를 이용해 풀기로 했습니다.

 

풀이

1) 주어진 문자열을 파싱 해줍니다. 저는 각 집합을 리스트로 표현해 [[...], [...], [...], ...] 꼴로 저장했습니다.

2) 부분 집합을 길이 순으로 오름차순 정렬해줍니다.

3) 짧은 부분집합부터 순회하며 정답 배열을 채워줍니다.
→ N번 부분집합을 처리할 때, 그 부분집합에서 이전에 나왔던 모든 원소를 제거하면 항상 하나의 원소가 남고, 그 원소를 정답 배열에 추가해주면 됩니다.

 

코드 설명

전체 코드는 맨 아래쪽에 있으니 참고하시면 됩니다.

ES6 문법이 다수 포함되어 있어 거기에 익숙하지 않다면 이해가 안가실 수 있습니다.

파싱

더 간결한 방법이 있을 듯한데 일단 저는 되는대로 파싱 했습니다.

s: '{{1,2,3},{2,1},{1,2,4,3},{2}}'

const subsets = s.substring(1, s.length-2).split('},')
	.map(str=>str.substring(1).split(',')
	.map(v=>Number(v)));

 

3번 줄에서 substring을 이용해 첫 번째 중괄호와 맨뒤 두개의 중괄호를 제거한 후, '},'를 기준으로 스플릿 했습니다. 이때의 반환 값은 다음과 같습니다.

첫 번째 줄 결과: [ '{1,2,3', '{2,1', '{1,2,4,3', '{2' ]

4번 줄에서는 각 문자열의 앞쪽 중괄호를 제거한 후, 콤마를 기준으로 스플릿 했습니다. 반환 값은 다음과 같습니다.

두 번째줄 결과: [ [ '1', '2', '3' ], [ '2', '1' ], [ '1', '2', '4', '3' ], [ '2' ] ]

5번 줄에서 모든 문자열을 정수형으로 치환해주었습니다. 최종적으로 다음의 리스트를 얻게 됩니다.

최종 결과: [ [ 1, 2, 3 ], [ 2, 1 ], [ 1, 2, 4, 3 ], [ 2 ] ]

 

정렬

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

각 부분집합의 길이 순으로 정렬해야 합니다.

자바스크립트의 sort() 함수는 비교 함수를 인자로 받습니다. 두 원소 a, b를 비교했을 때 음수를 반환하면 a가 앞으로, 양수를 반환하면 b가 앞으로 오게 됩니다. 그러니 길이의 차를 반환하도록 합시다.

 

정답 구하기

const ans = subsets.reduce((acc, subset) => {
	const value = subset.filter(v => !acc.includes(v))[0];
	acc.push(value);
	return acc;
}, []);

풀이 3)에서 말했듯 subset에서 acc(정답 배열)의 모든 원소를 제거하면 하나의 원소가 남습니다. 2번 줄에서 이 연산을 수행합니다.

그렇게 남은 원소를 acc에 추가해주면 됩니다.

 

정답 코드

function solution(s) {
    const subsets = s.substring(1, s.length-2).split('},')
    	.map(str=>str.substring(1).split(',')
        .map(v=>Number(v)));

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

    const ans = subsets.reduce((acc, subset) => {
        const value = subset.filter(v => !acc.includes(v))[0];
        acc.push(value);
        return acc;
    }, []);
    
    return ans;
}