Yang Gyeong Jin

Yang Gyeong Jin

I am korean univ-student…

암호 만들기 문제 풀어보기

[백준] 1759 암호 만들기Permalink

문제Permalink

문제

풀이Permalink

이 문제는 조건이 2개로 이루어져 있는데,

  1. 사전순으로 이루어진 l의 길이의 문자열인지?
  2. 모음이 1개이상 자음이 2개 이상으로 이루어져있는지?

아래의 풀이의 경우에는 먼저 1번 조건을 부합하는 문자열들을 저장해 놓고, 2번의 조건을 부합하는지를 확인해서 가능한 경우만 출력하는 방식으로 풀었다.

조건 1Permalink

사전순으로 이루어진 l의 길이의 문자열인지?

  • 주어진 문자 배열을 사전 순으로 정렬한다.
  • queue에 시작가능한 문자를 넣는다.
  • queue에서 꺼낸 문자보다 사전순의 뒤에 있는 문자들을 넣는다.
  • 만들어진 문자열이 l의 길이가 되면 저장한다.

조건 2Permalink

모음이 1개이상 자음이 2개 이상으로 이루어져있는지?

  • 만들어진 문자열을 순서대로 돌면서 모음이라면 모음에 cnt, 자음이라면 자음에 cnt
  • 모음이 1개이상 && 자음이 2개이상인 경우만 정답으로 출력한다.

코드Permalink

Copy 
package Java.baekjoon.gold.BOJ1759;
 
import java.util.*;
 
public class Main {
  static class Password {
    String pw;
    int index;
 
    public Password(String pw, int index) {
      this.pw = pw;
      this.index = index;
    }
  }
 
  static void solution(int l, int c, String[] arr) {
    // 결과를 저장할 list
    List<String> answer = new ArrayList<>();
    Arrays.sort(arr);
    // queue
    Queue<Password> q = new LinkedList<>();
    // 시작할 문자 큐에 추가
    for (int i = 0; i <= c - l; i++)
      q.add(new Password(arr[i], i));
    while (!q.isEmpty()) {
      Password cur = q.poll();
      // 선택한 문자보다 사전순으로 뒤에 있는 문자열 추가
      for (int i = cur.index + 1; i < c; i++) {
        Password next = new Password(cur.pw + arr[i], i);
        // 만들어진 문자열의 길이가 l과 같으면 결과에 저장
        if (next.pw.length() == l) {
          answer.add(next.pw);
          continue;
        }
        q.add(next);
      }
    }
    for (String result : answer) {
      // 모음이 1개이상 자음이 2개이상인지 확인후 출력
      if (isPossible(result))
        System.out.println(result);
    }
  }
 
  static boolean isPossible(String pw) {
    char[] gather = { 'a', 'e', 'i', 'o', 'u' };
    boolean isGather = false;
    int cntGather = 0;
    int cntConsonant = 0;
    // 문자열에 모음개수 자음개수 세기
    for (int i = 0; i < pw.length(); i++) {
      isGather = false;
      for (int j = 0; j < gather.length; j++) {
        if (pw.charAt(i) == gather[j]) {
          isGather = true;
          break;
        }
      }
      if (isGather)
        cntGather++;
      else
        cntConsonant++;
    }
    // 조건에 부함하면 true 아니면 false
    return cntGather >= 1 && cntConsonant >= 2;
  }
 
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int l = sc.nextInt();
    int c = sc.nextInt();
    String[] arr = new String[c];
    for (int i = 0; i < c; i++)
      arr[i] = sc.next();
    sc.close();
    solution(l, c, arr);
  }
}
view raw Java/baekjoon/gold/BOJ1759/Main.java delivered with ❤ by emgithub

참고자료Permalink

백준 문제 링크백준 암호 만들기 풀러가기

댓글남기기

참고