구름톤 챌린지 2주 Day1 - 이진수 정렬

이진수 정렬 (Java)

 

제출한 답 :

package week2;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();

        List<List<String>> p = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                List<Integer> a = Arrays.asList(i, j, n - 1);
                List<String> b = new ArrayList<>();
                int index = 0;
                for (int k : a) {
                    b.add(s.substring(index, k + 1));
                    index = k + 1;
                }
                p.add(b);
            }
        }

        Set<String> c = new HashSet<>();
        for (List<String> b : p) {
            c.addAll(b);
        }
        List<String> d = new ArrayList<>(c);
        Collections.sort(d);

        int answer = 0;
        for (List<String> b : p) {
            int temp = 0;
            for (String w : b) {
                temp += d.indexOf(w) + 1;
            }
            answer = Math.max(answer, temp);
        }

        System.out.println(answer);
    }
}

진짜 난이도 무엇?? 문제도 잘 이해가 안 되는데 뒤로 갈수록 풀 수 있긴 한건가?;

뭐지?? 테스트 2개다 되는거 일치되는거 보고 제출했는데 뭔 오류가?!

블록 하나 못 받음... 계속 제출 안 되서 그냥.. 내꺼에만 올린다.

 

 

이걸 쉽게 풀 수 있는 사람들이 넘 부럽다.

이제는 문제 공식을 봐도 대충 이해는 가는데 설명을 하라고 하면 못 할듯??;; 별 두개 이정도면??

알고리즘 공부를 기초부터 따로 해야 할 듯ㅠㅜ

 

완전 탐색

[알고리즘/Java] 완전탐색

 

문제 풀이

필요한 개념

• 완전 탐색

분석

길이가 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곳을 골라야 합니다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt(); 
        scanner.nextLine(); // to consume newline left by nextInt()
        String Word = scanner.nextLine();

        // 위치를 2개 정하는 모든 조합 구하기
        for (int i = 1; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
            }
        }
    }
}

자바에서 문자열을 나눌 때에는 string.substring() 을 사용합니다. 그리고 나누어진 단어는 하나의 집합으로 wordList 에 저장하면 됩니다.

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
				..code
				// 단어 집합을 저장할 wordList
				List<String[]> wordList = new ArrayList<>();
				// 부분 문자열을 저장할 Score
        Set<String> Score = new HashSet<>();

        // 위치를 2개 정하는 모든 조합 구하기
        for (int i = 1; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
				String first = Word.substring(0, i);
                String second = Word.substring(i, j);
                String third = Word.substring(j);
                wordList.add(new String[]{first, second, third});
                Score.add(first);
                Score.add(second);
                Score.add(third);
            }
        }
    }
}

점수 판 만들기

Score 변수에는 Word로 만들 수 있는 모든 부분 문자열이 중복을 제외하고 담겨져 있습니다. 이는 set 자료형의 특징입니다. Score 변수의 값을 사전 순으로 정렬한 후, 객체에 Key로 전환해주려고 합니다. ArrayList 의 정렬은 Collections.sort()를 사용합니다.

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

최고 점수 찾기

wordList 변수에는 문자열을 3개로 분리한 모든 단어 집합을 있고, wordScore에는 부분 문자열이 받을 수 있는 점수가 있습니다. 즉, 모든 단어 집합을 순회하면서 받을 수 있는 최고 점수를 구하기만 하면 최고 점수를 찾을 수 있습니다. 항상 최고 점수를 찾을 때, maxScore 를 저장하는 변수는 최저 값으로 할당해주세요.

import java.util.*;

public class Main {
    public static void main(String[] args) {
				..code
				int maxScore = -1;
        for (String[] words : wordList) {
            int tempScore = 0;
            for (String word : words) {
                tempScore += wordScore.get(word);
            }
            maxScore = Math.max(maxScore, tempScore);
        }
        
        System.out.println(maxScore);
    }
}

 

정답 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt(); 
        scanner.nextLine(); // to consume newline left by nextInt()
        String Word = scanner.nextLine();

        List<String[]> wordList = new ArrayList<>();
        Set<String> Score = new HashSet<>();

        // 위치를 2개 정하는 모든 조합 구하기
        for (int i = 1; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                String first = Word.substring(0, i);
                String second = Word.substring(i, j);
                String third = Word.substring(j);
                wordList.add(new String[]{first, second, third});
                Score.add(first);
                Score.add(second);
                Score.add(third);
            }
        }

        List<String> tempScoreList = new ArrayList<>(Score);
        Collections.sort(tempScoreList);

        Map<String, Integer> wordScore = new HashMap<>();
        for (int i = 0; i < tempScoreList.size(); i++) {
            wordScore.put(tempScoreList.get(i), i + 1);
        }

        int maxScore = -1;
        for (String[] words : wordList) {
            int tempScore = 0;
            for (String word : words) {
                tempScore += wordScore.get(word);
            }
            maxScore = Math.max(maxScore, tempScore);
        }
        
        System.out.println(maxScore);
    }
}