[Node.js] 구름톤 챌린지 2주 Day1 풀이

문제명 : 문자열 나누기

문제

길이가 N인 문자열 S가 주어진다.

문자열 S를 서로 겹치지 않는 3개의 부분 문자열로 나눠야 한다.

부분 문자열은 모두 길이가 1 이상이어야 하고, 원래 문자열에서 연속해야 한다.

 

문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다.

점수 계산 방법은 아래와 같다.

• 문자열 S를 위 조건에 따라 3개의 부분문자열로 나눴을 때 등장하는 모든 부분 문자열을 중복제거하고 사전순으로 정렬한 결과를 P라고 하자.
• 나누어진 3개의 문자열이 각각 P에서 i, j, k번째로 등장하는 문자열이라면 얻을 수 있는 점수는 i  + j + k 이다.

abcd라는 문자열을 3개의 부분문자열로 나누는 방법은

{a, b, cd}, {a, bc, d}, {a, b, cd} 가 있다.

 

위의 원소들에서 중복을 제거한 뒤 사전 순서대로 정렬한 배열인 P는

[a, ab, b, bc, c, cd, d] 이다.

 

이 때 {ab, c, d}로 문자열을 나눈 경우, P의 순서에 따라 2 + 5 + 7 이므로,

{a, b, cd}, {a, bc, d}, {a, b, cd} 중에서 얻을 수 있는 최대 점수이다.

 

문자열 S를 3개의 부분문자열로 나눴을 때 얻을 수 있는 점수 중 최대 점수를 출력하시오.

 

입력

첫째 줄에 문자열의 길이 정수 N이 주어진다.

둘째 줄에 문자열 S가 주어진다.

 

제약조건

 

입출력

예시1

입력

4
abcd

출력

14

 

---

풀이

const readline = require('readline');
let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
let input = [];

rl.on('line', (line) => {
	input.push(line.trim());
	if (input.length === 2) {
	  rl.close();	
	}
});

rl.on('close', () => {
	const [strLength, str] = input
	const substr = []
	const set = new Set()
	const keyObj = {}
	let point = -Infinity
	
	for (let i = 0; i < str.length - 2; i++) {
		for (let j = i + 1; j < str.length - 1; j++) {
			for (let k = j + 1; k < str.length; k++) {
				const substr1 = str.slice(0, j)
				const substr2 = str.slice(j, k)
				const substr3 = str.slice(k, str.length)
				set.add(substr1)
				set.add(substr2)
				set.add(substr3)
				substr.push([substr1, substr2, substr3])
			}
		}
	}
	
	const dictArr = [...set].sort()
	dictArr.forEach((e, i) => {
		keyObj[e] = i + 1
	})
	
	substr.forEach(e => {
		const subPoint = e.reduce((acc, e) => acc + keyObj[e], 0)
		if (subPoint > point) point = subPoint
	})
	
	console.log(point)
})

해결해야할 부분 문제가 3가지라고 가정한 뒤에 풀이했다.

• 주어진 문자를 부분 문자열로 나눠본다. 모두 나눠야하므로 완전탐색을 이용한다.
• 나눠진 부분 문자열을 이용해 결과 P를 만든다. 중복을 제거해야하므로 set을 이용한다.
• 사전순 정렬 중 3개를 뽑아 가장 높은 점수가 나오는 것을 출력한다.

 

3개의 부분 문자열을 만들어야 하므로 for문을 3개 사용했으며,

부분 문자열을 만들기 위해 slice 메서드를 이용했다.

이 때, 부분 문자열은 원래 문자열과 같이 이어져있어야 하므로, 첫번째 부분 문자열의 시작 인덱스는 0으로 고정했다.

 

해결은 했지만 맘에 안드는 부분이 하나 있다.

문자열의 길이와 상관 없이 마지막 반복문이 한번 더 돌게 된다.

3중 for문의 length 설정 문제인데... 반복을 하나 줄이게 되면 문자열 길이가 3일 때 원하는 값이 도출이 안된다.

 

일단 비효율적인 부분은 감안하고 문제를 제출했다.

내일 정해코드를 보면서 최적화된 알고리즘을 공부해봐야겠다.