구름톤 챌린지 2주 차 학습 일기 - 6일차: 문자열 나누기

지구·2023년 8월 23일

구름톤 챌린지

목록 보기

3/7

1주차 5문제는 수월하게 풀었는데 2주차 첫 문제부터 막혔다. 갑자기 어려워졌다.
그래서 당일에 해결하지 못하고 다음날 해설이 나와서야 해결할 수 있었다.

문제

길이가 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는 알파벳 소문자로만 구성되어 있다.

출력

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

입출력 예시

예시 1

입력

4
abcd

출력

예시 2

입력

3
abz

출력

나의 풀이

문자열을 3개로 나누는 방법을 고려하지 못해서 풀지 못했다. for문으로 하나씩 미뤄가면서 나누면 되지 않을까 생각은 했는데 구현하는 것을 실패했다.

해설 풀이

const readline = require('readline');

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

const input = [];
let N, Word;

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

rl.on('close', () => {
    N = parseInt(input[0]);
    Word = input[1];

    const wordList = [];
    const Score = new Set();

  	// 가능한 부분 문자열 구하기
  	// 이중 for문으로 반복하면서 가능한 부분 문자열을 Set과 배열에 추가해준다.
    for (let i = 1; i < N; i++) {
        for (let j = i + 1; j < N; j++) {
            const first = Word.substring(0, i);
            const second = Word.substring(i, j);
            const third = Word.substring(j);
            wordList.push([first, second, third]);
            Score.add(first);
            Score.add(second);
            Score.add(third);
        }
    }
	
  	// 점수 판 만들기
   	// 정렬된 임시 점수 리스트
    const tempScoreList = [...Score].sort();
  	// 부분 문자열을 key로 가지고 있는 객체
    const wordScore = {};

    for (let i = 0; i < tempScoreList.length; i++) {
      	// 점수는 1점 부터이기 때문에 +1씩 더해준다.
        wordScore[tempScoreList[i]] = i + 1;
    }

  	// 최고 점수 찾기
    let maxScore = -1;
    for (const words of wordList) {
        let tempScore = 0;
        for (const word of words) {
            tempScore += wordScore[word];
        }
        maxScore = Math.max(maxScore, tempScore);
    }

    console.log(maxScore);
});

문자열을 3개의 부분 문자열로 나눈 뒤에 Set을 사용하는 것과 최고점을 찾는 것은 생각했는데 문자열을 3개로 나누는 모든 경우의 수를 찾는 것이 어려웠다.
완전 탐색 문제로 모든 부분 문자열을 구하는 것이 중요한 문제였기 때문에 완전 탐색을 하는 중요한 방법을 놓친 것으로 이 방식을 잊지 않고 공부하고 외워야한다.

지구

프론트엔트 개발자입니다 🧑‍💻

이전 포스트

구름톤 챌린지 1주 차 학습 일기 - 2

다음 포스트

구름톤 챌린지 2주 차 학습 일기 - 6일차: 문자열 나누기