[구름톤 챌린지] 2주차_문자열 나누기

 

필요한 개념

---

• 완전 탐색

 

 

문제 분석

---

길이가 N인 문자열 S를 3개의 문자열로 나눈 후, 주어진 조건에 따라 점수를 계산하는 문제이다.

점수는 문자열의 모든 부분 문자열의 순서에 따라서 결정된다.

나눌 수 있는 모든 경우의 수 중에서 최대 점수를 얻을 수 있는 문자열을 찾는 문제이다.

더불어 문자열의 길이의 최대 100 정도로 짧기 때문에 가능한 모든 부분 문자열을 확인하는 완전 탐색으로 문제를 해결할 수 있다.

 

문제 해결을 위해서 아래 순서대로 진행한다.

1. 가능한 부분 문자열을 찾고, 정렬하여 점수 판을 만든다.
2. 완전 탐색으로 문자열을 자를 수 있는 모든 경우의 수를 찾는다.
3. 점수 판을 이용해서, 모든 경우의 수 중에서 최대 점수를 찾는다.

 

조합

---

조합은 순서를 고려하지 않고, 집합에서 일부 원소를 선택하는 방법이다.

예를 들어, [1, 2, 3]에서 2개를 고른다면, [[1, 2], [1, 3], [2, 3]]과 같이 나타낼 수 있다.

뽑는 순서를 고려하는 경우는 순열이라고 한다.

보통의 조합은 재귀 함수로 구하지만, 이 문제는 크기가 작기 때문에 반복문으로 해결할 수 있다.

 

 

가능한 부분 문자열 구하기

---

문자열을 나누었을 때, 나올 수 있는 모든 부분 문자열을 구해야 한다.

또한 구한 부분 문자열들 사이에 중복되는 값이 없어야 한다.

단어를 3개로 나누면서, 만들 수 있는 모든 부분 문자열을 조합을 활용해서 구한다.

길이가 N인 문자열을 3개로 나누기 위해서는 나눌 인덱스 2곳이 필요하다.

그리고 모든 부분 문자열 길이가 1 이상이어야 하므로, 1 ~ N-1 사이에서 2곳을 고른다.

..code 데이터 입력 부분

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

    for (let i = 1; i < N; i++) {
        for (let j = i + 1; j < N; j++) {
		    // 길이가 1 이상이 되도록 단어를 자를 수 있는 지점 2곳
        }
    }
});

 

 

자바스크립트에서 문자열을 나눌 때 string.substring()을 사용한다.

그리고 나누어진 단어는 하나의 집합으로 wordList에 저장한다.

이때 발생하는 부분 문자열은 점수 계산을 위해 Score 변수에 추가한다.

..code 데이터 입력 부분

rl.on('close', () => {
    N = parseInt(input[0]);
    Word = input[1];
		let wordList = [];
    let Score = new 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);
        }
    }
});

 

 

점수판 만들기

---

Score 변수에는 Word로 만들 수 있는 모든 부분 문자열이 중복을 제외하고 담겨져 있다.

Set을 활용해서 Score 변수의 값을 사전 순으로 정렬한 후, 객체에 Key로 전환해준다.

이렇게 하면 매번 인덱스를 찾지않고 Key 만으로 점수를 찾을 수 있다.

..code 데이터 입력 부분

rl.on('close', () => {
    N = parseInt(input[0]);
    Word = input[1];
		let wordList = [];
    let Score = new Set();
    for (let i = 1; i < N; i++) {
        for (let j = i + 1; j < N; j++) {
		..code
        }
    }
    // 정렬된 임시 점수 리스트
    const tempScoreList = [...Score].sort();
    // 부분 문자열을 Key로 가지고 있는 객체
    const wordScore = {};

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

 

 

최고 점수 찾기

---

wordList 변수에는 문자열을 3개로 분리한 모든 단어 집합이 있고, wordScore 에는 부분 문자열이 받을 수 있는 점수가 있다.

즉, 모든 단어 집합을 순회하면서 받을 수 있는 최고 점수를 구하기만 하면 최고 점수를 찾을 수 있다.

항상 최고 점수를 찾을 때, maxScore를 저장하는 변수는 최저값으로 할당한다.

 

word_list의 모든 요소를 돌면서 최고 점수를 찾으면 된다.

최고 점수를 저장할 max_score는 -1로 설정한다.

반대로 단어 집합의 점수 score는 0으로 설정한다.

단어 집합 별로 점수를 구한 뒤에, max_score 보다 크면 그때 갱신한다.

rl.on('close', () => {
		..code
    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개의 문자열로 나눠야 한다는 점, 부분 문자열을 구한 배열을 중복 없이 정렬해서 그 인덱스로 점수를 계산해야 한다는 점이 생각은 쉬웠는데 막상 코드를 작성하니 내가 생각한 대로 결과가 나오지 않았다.

오늘 다시 정리하면서, 어떤 부분에서 내 생각대로 되지 않았는지 돌아볼 수 있었다.