[ 구름톤 챌린지 ] 문자열 나누기

문제

길이가 N인 문자열 S가 주어진다. 플레이어는 문자열 S를 서로 겹치지 않는 3개의 부분문자열로 나누려고 한다. 부분문자열은 모두 길이가 1 이상이어야 하며, 원래 문자열에서 연속해야 한다. 문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다. 점수는 다음 과정에 따라 계산된다. • 문자열 S를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 P라고 한다. • 나누어진 3개의 문자열이 각각 P에서 i, j, k번째로 등장하는 문자열이라면, 얻을 수 있는 점수는 i+j+ k 이다. 예를 들어, abcd 라는 문자열을 3개의 부분문자열로 나누는 방법은 a,b,cd, a, bc, d, ab, c, d 의 세 가지가 있다. 여기서 부분문자열을 중복 제거하고 사전 순서로 정렬한 결과 P 는 a, ab, b, bc, c, cd, d 이다. 이때 ab, c, d 로 문자열을 나눈 경우 얻을 수 있는 점수는 2+5+7= 14점이고, 얻을 수 있는 최대 점수이다. 문자열 S를 3개의 부분문자열로 나눴을 때 얻을 수 있는 점수 중 최대 점수를 출력하시오.

입력

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

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

• 3≤N≤ 100
• S는 알파벳 소문자로만 구성되어 있다.

출력

문자열을 나눠서 얻을 수 있는 최대 점수를 출력한다.

제출 코드

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

rl.on('close', () => {
	let arr=input[1];
	const setArr=new Set();
	let answer=0;
	for(let i=0; i<arr.length; i++){
		for(let j=1; j<=arr.length-2; j++){
			setArr.add(arr.slice(i,i+j));
		}
	}
	const sliced = [...setArr];
	sliced.sort();
	const obj={};
	sliced.forEach((item,index)=> (obj[item]=index+1));
	
	for(let i =1; i<arr.length; i++){
		for(let j=i+1; j<arr.length; j++){
			let temp = obj[arr.slice(0,i)];
			temp+=obj[arr.slice(i,j)];
			temp+=obj[arr.slice(j)];
			answer=Math.max(answer,temp)
		}
	}
	console.log(answer)
})

배운점

• Set
  • 동일한 값을 중복하여 포함할 수 없음
  • 요소 순서에 의미가 없음
  • 인덱스로 요소에 접근할 수 없음

→ 위와 같은 특성을 이용해서 중복을 제거하는데 사용하였다.

• forEach
  • 중복을 제거하고 사전 순서로 정렬한 결과값 sliced에 대해 점수를 매기기 위해 사용하였다.
  • 예를들어, 문제의 예시 처럼 a,ab,b,bc…가 있을 경우 a에 1점,ab에 2점 b에 3점을 매기는 식이다.

느낀점

• 문제를 이해하고 푸는데 한시간이 넘게 걸려서 쉽지않았다.
• 내가 짠 코드보다 더 좋은 풀이가 있을것같아서 정해코드를 기다려봐야겠다.
• 완전탐색의 심화문제를 푸는 느낌이었다.