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

문제

---

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

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

 

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

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

 

나의 접근 방식

---

1. 3개의 부분 문자열을 만들어서 배열에 push

2. 각각의 배열을 다시 배열에 push(2차원 배열 생성)

3. Set 함수 생성하여 중복 제거 후 모든 문자열 사전순으로 나열

4. 2차원 배열을 순회하면서 사전순으로 몇 번째 인덱스인지 확인 후 해당 인덱스 모두 더하기

5. 더한 인덱스 값이 가장 큰 값이 정답

 

나의 코드

---

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', () => {
  // 3개의 부분 문자열을 만들어서 []에 push
  function getAllSubstrings(input) {
    const substrings = [];

    for (let i = 1; i < input.length - 1; i++) {
      for (let j = i + 1; j < input.length; j++) {
        substrings.push([input.slice(0, i), input.slice(i, j), input.slice(j)]);
      }
    }

    return substrings;
  }

  const combinations = getAllSubstrings(input[1]);
  let list = [];

  // list에 모든 값 push
  for (let i = 0; i < combinations.length; i++) {
    list.push(...combinations[i]);
  }

  // P: arr에서 중복 제거 후 모든 문자열 사전순으로 정렬
  let sortedList = [...new Set(list)].sort();
  let scoreArr = [];

  // arr을 순회하면서 각각의 배열 안에 있는 값의 인덱스를 모두 더하기
  for (let i = 0; i < combinations.length; i++) {
    let score = 0;

    for (let j = 0; j < 3; j++) {
      score += sortedList.indexOf(combinations[i][j]) + 1;
    }
    scoreArr.push(score);
  }

  // 문자열을 나눠서 얻을 수 있는 최대 점수
  console.log(Math.max(...scoreArr));

  rl.close();
});

 

알아두면 좋은 팁

---

1. 조합을 사용하기

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

예륻 들어 [1, 2, 3]에서 2개를 고른다면, [[1, 2], [1, 3], [2, 3]]을 고를 수 있다. 

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

 

참고자료

---

• 구름톤 프로젝트 매니징 자료