이번 주부터 완전 탐색 알고리즘을 활용하는 문제들이 출제됩니다. 지난주보다는 난이도가 조금 올라간 것 같다는 생각이 드네요..

구름톤 챌린지

오늘의 문제는 문자열 나누기 입니다 !
주어진 문자열이 단독으로 사용되는 경우와 조합되어 상용되는 경우를 고려해서 풀어봤고, sort, 스프레드 연산자, max 등등 다양한 연산자를 사용할 수 있습니다.

풀이

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

let cnt = 0;
let N = 0;
let S = [];
let P = [];
let arr = [];
let maxSum = 0;

rl.on('line', (line) => {
  cnt++;
  if (cnt === 1) {
    N = parseInt(line);
  } else {
    S = line.trim();
  }
});

rl.on('close', () => {
   for (let i = 0; i < N-2; i++) {
        for (let j = i + 1; j < N-1; j++) {
            let s1 = S.substring(0, i + 1);
            let s2 = S.substring(i + 1, j + 1);
            let s3 = S.substring(j + 1);
            arr.push([s1, s2, s3]);
        }
    }
	
	P = [...new Set(...arr)].sort();
	
	for(let Arr of arr) {
    let sum = 0;
		
    for (let s of Arr) {
			sum += P.indexOf(s) + 1;
    }
		
    maxSum = Math.max(maxSum, sum);
  }
	
	console.log(maxSum);
});

(abcd를 예시로 진행합니다.)

1. 주어진 알파벳을 조합해서 저장하는 배열을 만들어 줍시다. 3개의 부분 문자열로 나눠줄 필요가 있기 때문에 N - 2까지 바깥 반복문을 돌려주고(처음 반복문에서 첫 번째 부분 문자열이 결정되고 이후 2가지의 부분 문자열 존재가 필요하기 때문에), 안쪽 반복문에서는 두 번째 부분 문자열을 결정하고 그 이후의 값을 세 번째 부분 문자열로 결정합니다.
   그렇게 만들어진 문자열을 arr이라는 배열에 넣어줍니다. 모든 반복이 끝나면
   arr은 [ ['a','b',cd'], ['a','bc',d'], ['ab','c',d'] ]와 같은 2차원 배열 형태로 존재하게 됩니다.

   - substring 메서드는 (start, end) 시작하는 index부터 끝나는 index까지 반복됩니다. 

2. 이제 다음으로 arr에서 중복과 정렬 작업을 진행하고 P 변수에 할당해 주면 됩니다.
   flat 메서드로 1차원 배열로 만들어주고 스프레드 연산자를 활용해 중복을 제거한 뒤에 정렬 메서드 sort를 사용해 정렬해 줍니다.

• Array.flat(): 배열의 중첩을 제거해 준다.
  (ex. 2차원 배열 속 1차원 배열이 존재한다면, 사용하면 2차원 배열을 1차원 배열로 바뀌게 된다.)

3. 마지막으로 arr 배열의 한 요소인 Arr
   => [ ['a','b',cd'], ['a','bc',d'], ['ab','c',d'] ] 이 arr 배열의 한 요소 ['a','b',cd']가 순차적으로 Arr이 된다고 생각하면 된니다.
   이제 P 안에 (a, ab, b ... 모든 배열이 중첩 없이 정렬된 상태 P) Arr의 한 요소 'a', 'b' 'cd' 등등이 몇 번 index에 존재하는지 그 값을 sum에 더하고 max로 가장 큰 sum의 값을 비교해 가장 큰 maxSum을 출력하면 해결하게 됩니다.

후기

처음 문자열을 조합하는 부분에서 많은 어려움을 겪었습니다.
자주 사용되는 substring, max, indexof 메서드를 다시금 복습하는 느낌으로 사용할 수 있었고,
flat이라는 메서드는 알고는 있었지만 실제로 사용해 본 경험은 없었는데 적용하기 적합한 문제가 나온 것 같아 사용해 볼 수 있었습니다. 앞으로도 알고리즘 지식도 중요하지만 자주 사용되고 유용한 메서드들도 공부가 필요할 것 같습니다!