[구름톤 챌린지] 알고리즘 챌린지 Week2Day1 학습일기

[ 목차 ]

1. 구름톤 챌린지 2주차 개요

2. 문자열 나누기 문제

3. 문자열 나누기 풀이

4. 느낀점

개요

원래는 구름톤 챌린지 때문에 블로그 글 작성했는데 매일 문제 풀고 정리하니 복습할 수 있어서 챌린지 상관없이 블로그 글 작성하기 시작했습니다. 그럼 완전탐색 Week2Day1 문제 접근 방법 및 풀이에 대해서 정리하겠습니다.
 

☁️ 문제 ☁️

 

제한사항

 

풀이

문제에서 구해야 될 부분은 총 2가지 입니다.
첫째 조건에 따라 나눴을 때 나오는 모든 부분 문자열의 사전 순으로 정렬 된 값
둘째 나누어진 3개의 문자열의 index+1 위치를 더했을 때 가장 큰 점수 구하기
 
문제에서 나왔듯이
abcd 문자열을 3개의 부분 문자열로 나눴을때 가장 큰 점수는 {ab,c,d} 2 + 5 + 7 => 14가 제일 큰 점수입니다.
 
시간초과 날만한 사항도 없기 때문에 완전탐색의 주제처럼
효율성을 따지기보다는 이중for문을 이용해서 푸는 방법을 택했습니다. 
 

조건에 따라 문자열을 나눠서 배열에 추가

선언한 arrayList 배열에 조건에 따라 자른 문자열을 모두 추가해줍니다.

List<String> arrayList = new ArrayList<>();
for (int i = 1; i < n - 1; i++) {
    arrayList.add(s.substring(0, i));
    for (int j = i + 1; j < n; j++) {
        arrayList.add(s.substring(i, j));
        arrayList.add(s.substring(j));
    }
}

 

중복제거 후 정렬

중복제거 후 정렬해 새로운 배열에 할당해줬습니다.

List<String> sortedUniqueSubStrings = arrayList.stream().distinct().sorted().toList();

 

이중 for문을 통해 가장 큰 점수 구하기

맨처음 조건에 따라 문자열을 나누기 위해 사용했던 이중for문을 다시 사용해 first, second, third의 index값을 구합니다. 그 뒤 구한 값이 가장 큰 값인지 확인해줍니다.

int max = 0;
for (int i = 1; i < n - 1; i++) {
    String first = s.substring(0, i);
    for (int j = i + 1; j < n; j++) {
        String second = s.substring(i, j);
        String third = s.substring(j);
        int compare = sortedUniqueSubStrings.indexOf(first) + sortedUniqueSubStrings.indexOf(second) + sortedUniqueSubStrings.indexOf(third);
        max = Math.max(max, compare);
    }
}

 

return max + 3

최종값 max + 3 한 값이 최종적으로 구해지는 최대점수 입니다. 여기서 +3하는 이유는 배열의 index값의 시작은 0이기 때문입니다. 그러므로 각 숫자위치(index)에 +1을 해줘야됩니다.
 

🧐 느낀점

이번문제는 이중for문을 사용하지 않고 해결할 방법을 찾다가 시간이 좀 걸렸네요 ㅠㅠ
저번 1주차 마지막 날 문제도 별2개 수준의 문제였는데 같은 별2개인데 난이도는 좀 다르게 느껴졌습니다. 
 
다른사람들은 어떻게 풀었는지 보고싶은데 그런 커뮤니티는 없어서 좀 아쉽네요 🥲
 
최종코드는 github에서 볼 수 있습니다 :)
 
https://github.com/algorithm-cote-study/goormthon_challenge

GitHub - algorithm-cote-study/goormthon_challenge: 구름톤 알고리즘 챌린지