[백준] 1062번 - 가르침

1062번 - 가르침

 

 

 

1062번: 가르침

문제

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

 

 

 

문제 해석해보기

먼저 문제를 보면 다음과 같다.

• 단어가 N개 있다.
• 학생은 K개의 알파벳을 배운다.
• 단어에는 무조건 “anta”가 앞에 붙어있고 맨 뒤에 “tica”가 붙으며 끝이난다.
• K개의 알파벳을 배우는 학생이 N개의 단어 중 최대한 몇 개의 단어를 읽을 수 있겠는가?

 

결국 K개의 알파벳으로 단어를 가장 많이 읽을 수 있다면 몇 개인가? 를 구하는 문제이다.

여기서 한가지 파악할 수 있는 점이 있다.

바로 “anta”와 “tica”가 무조건적으로 존재한다는 것이다.

• 즉, a c i n t 를 먼저 뽑은 상태에서 나머지 알파벳을 선택해야한다.

 

 

그렇다면 나머지 알파벳을 선택하려면 어떻게 해야할까?

 

먼저 바로 생각해 본다면 다음과 같은 방식으로 알파벳을 K개 선택할 수 있을 것이다.

그런데 저런 식으로 알파벳을 선택한다면 중복되는 알파벳이 너무 많다.

 

 

우리는 지금 ‘중복과 순서'가 필요없다.

즉, abc를 이미 선택했다면 bca, acb, cba, … 등은 다 중복으로 처리 될 것이고

aaa와 같이 a가 3개 씩 나올 필요도 없다.

 

 

그렇다면 우리는 현재 선택한 알파벳보다 큰 값들만 골라 비교하면 된다.

 

 

 

 

 

 

[알고리즘 특강 1일차] 알고리즘이란, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 이해와 활용

[알고리즘 특강 1일차] 알고리즘이란, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 이해와 활용

위 글에 포스팅 했던 것 중에 DFS 팁 중에 6가지 단계를 주석으로 작성해 놓고 구현하는 방법을 사용해보려 한다.

 

 

 

 

 

단계별로 적용해보기

먼저 아래와 같이 dfs 메서드 코드를 작성하겠습니다.

static void dfs() {
    // 1. 체크인

    // 2. 목적지인가 ?

    // 3. 연결된 곳을 순회

        // 4. 갈 수 있는가 ?

            // 5. 간다

    // 6. 체크아웃

}

1. 체크인

• 먼저 우리가 알파벳을 몇 개 골랐는지 알려줘야 합니다.
• 어떤 알파벳을 선택했는지 알려줘야 합니다.

2. 목적지 인가 ?

• K개의 알파벳을 골랐을 때 몇 개의 단어를 읽을 수 있는지 개수를 체크합니다.
• 만약 이전 개수보다 많으면 최대값을 수정 해줍니다.

3. 연결된 곳을 순회

• [a-z]

4. 갈 수 있는가

• 이전에 선택한 알파벳보다 크며

5. 간다

• 순회합니다.

6. 체크아웃

• 선택했던 알파벳을 취소함으로써 알파벳 고른 개수와 선택값을 수정합니다.

 

 

 

 

dfs 코드로 구현하기

처음에 구현한 코드 펼쳐보기 (맞긴해요)

  package 백준.자바_특강.DAY1.가르침;

  import java.io.FileInputStream;
  import java.io.FileNotFoundException;
  import java.util.ArrayList;
  import java.util.List;
  import java.util.Scanner;

  /**
   * 아... 이거 문자로 캐스팅하면서 시간 초과.. 진작에 걍 정수로 뽑아먹을걸 바보
   * 통과는 했는데 메모리, 시간 엄청 잡아먹힘
   */
  public class Main2 {
      static int N, M, tempAnswer, answer;
      static String[] words;
      static List<List<Integer>> wordIntListList;

      public static void main(String[] args) throws FileNotFoundException {
          System.setIn(new FileInputStream("백준/자바_특강/DAY1/가르침/input.txt"));

          Scanner sc = new Scanner(System.in);

          N = sc.nextInt();
          M = sc.nextInt();
          sc.nextLine();
          wordIntListList = new ArrayList<>();
          for (int i = 0; i < N; i++) {
              wordIntListList.add(new ArrayList<>());
          }

          words = new String[N];
          for (int i = 0; i < N; i++) {
              words[i] = sc.nextLine();
              List<Integer> wordIntList = wordIntListList.get(i);
              for (char c : words[i].substring(4, words[i].length() - 4).toCharArray()) {
                  if (!wordIntList.contains(c) && c != 'a' && c != 'c' && c != 'i' && c != 'n' && c != 't') {
                      wordIntList.add((int) c);
                  }
              }
          }

          if (M >= 5) {
              List<Integer> charList = new ArrayList<>();
              dfs(0, charList, 97);
          }

          System.out.println(answer);

      }

      static void dfs(int L, List<Integer> intList, int ascii) {
          // 체크인
          // 목적지
          if (L == M - 5) {
              tempAnswer = 0;
              wordIntListList.forEach(wordCharList -> {if (intList.containsAll(wordCharList)) tempAnswer++;});
              answer = Math.max(tempAnswer, answer);
              return;
          }

          // 순회
          for (int i = ascii; i <= 122; i++) {

              // 갈 수 있는가
              if (!intList.contains(i) && i != 97 && i != 99 && i != 105 && i != 110 && i != 116) {

                  // 간다
                  intList.add(i);
                  dfs(L + 1, intList, i + 1);
                  // 체크아웃
                  intList.remove(intList.size() - 1);
              }
          }
      }
  }

 

 

 

 

다음은 다른 코드를 참조하며아래와 같이 구현할 수 있었다.

처음에 작성했던 코드와 비교해서 좀 더 효율적이다.

왜 더 효율적이었을까 ?

 

내 코드를 보면 배열의 인덱스로 해당 알파벳이 있는지 찾지않고

단어 알파벳 하나하나를 돌려가면서 비교하기 때문이다.

 

 

항상 visited[][]과 같은 배열을 이용하면 좋을지 판단하면서 구현해보자.

• 먼저 기본적으로 있어야 할 a c t i n이 이미 존재한다는 전재하에 진행한다
• 만약 K < 5라면 단어는 무조건 0개이다
• dfs(int index)의 스타트포인트는 [a-z]가 될 수 있다.

package 백준.자바_특강.DAY1.가르침;

import java.util.Scanner;

public class Main {

    static int N, K, selectedCount, answer;
    static String[] words;
    static boolean[] visited;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();

        words = new String[N];
        visited = new boolean[26];
        visited['a' - 'a'] = true;
        visited['n' - 'a'] = true;
        visited['t' - 'a'] = true;
        visited['i' - 'a'] = true;
        visited['c' - 'a'] = true;

        sc.nextLine();
        for (int i = 0; i < N; i++) {
            words[i] = sc.next().replaceAll("[antic]", "");
        }

        if (K >= 5) {
            selectedCount = 5;
            answer = countWords();

            for (int i = 0; i < 26; i++) {
                if (visited[i] == false) {
                    dfs(i);
                }
            }
        } else {
            answer = 0;
        }
        System.out.println(answer);
    }

    static void dfs(int index) {
        // 1. 체크인
        selectedCount++;
        visited[index] = true;

        // 2. 목적지인가 ?
        if (selectedCount == K) {
            answer = Math.max(answer, countWords());
        } else {
            // 3. 연결된 곳을 순회
            for (int i = index + 1; i <= 25; i++) {
                // 4. 갈 수 있는가 ?
                if (visited[i] == false) {
                    // 5. 간다
                    dfs(i);
                }
            }
        }

        // 6. 체크아웃
        selectedCount--;
        visited[index] = false;
    }

    static int countWords() {
        int count = 0;
        for (int n = 0; n < N; n++) {
            boolean isOk = true;
            String word = words[n];
            for (int i = 0; i < word.length(); i++) {
                if (visited[word.charAt(i) - 'a'] == false) {
                    isOk = false;
                    break;
                }
            }
            if (isOk) {
                count++;
            }
        }
        return count;
    }
}