1. 문제에 대하여 📦
(1) 조건 분석 📊
- 영어 단어가 n개 주어짐.
- 하나의 영어 단어마다 거기서 나올 수 있는 글자조합을 사전순으로 나타내기
- 중복 제외
2. 코드가 나오기까지 🛠️
KEY WORD
: 순열
, np (next permutation)
(1) 순열로 푸는 법
인수로 받은 문자열의 각 자리마다 방문배열을 두는 순열 풀이는 '메모리 초과'가 난다.
메모리 초과가 나는 이유는4. 트러블 슈팅
에 기록해두었으니 참고하길 바란다.
해당 풀이에서 주의해야할 점은 서로 다른 글자간에는 순서가 있지만, 같은 글자간에는 순서가 없다는 것이다. 예를 들어 aba
를 차례대로 두는 경우의 수에서
경우의 수 별 각 글자의 순서 | a | b | a |
---|---|---|---|
1회 | 1 | 2 | 3 |
2회 | 3 | 2 | 1 |
위의 두 경우는 분명 글자간의 순서는 다르지만 나타내는 글자 조합은 같을 수 있다. 따라서 해당 문제의 순열 풀이법에서 중요한 점은 같은 글자 사이에 순서는 지우는 것이다.
이걸 할 수 있는 가장 쉬운 방법은 INDEX = 글자
, VALUE = 글자가 나온 횟수
로 방문 배열 대신 횟수 배열을 활용하는 것일 거다. 다음과 같이 진행한다.
- 횟수 배열(이하 이름
alphabet
)을 만든다.
( alphabet[0] 는 a가 나온 횟수, alphabet[25]는 b가 나온 횟수) - 횟수 배열 업데이트하고, 횟수 배열 상대로 순열을 돌린다.
(횟수 배열 카운트 하나 줄이고, 현재 순서에 문자 하나 넣기 -> 재귀) - 나온 결과들을 출력한다.
이렇게 풀면 같은 문자들은 동일 횟수 배열에 들어가있는 관게로 그들간의 순서가 사라진다. 따라서 필요없는 중복 없이 오직 답만 구할 수 있게 된다.
(2) Next Permutation (이하 NP)로 푸는 법
해당 문제는 사전 순 정렬
을 원하는 시점에서 NP 풀이를 쓰라고 한 게 아닌가 싶다.
그냥 NP 풀이를 정석대로 구현해서 하나 하나 출력하면 된다.
(맨 처음 문자열 값을 오름차순으로 정렬 후 출력을 한 번 해야함을 잊지말자. NP 함수 태우면, 바로 그 다음 순 사전 순 글자 조합만 나온다.)
(1) 시간복잡도 분석 ⏳
단어 크기는 20이하이며, 하나의 단어 당 나올 수 있는 애너그램(문제에서 말하는 단어에서 파생되는 글자조합)이 최대 100,000개로 정해져 있다.
즉 중복된 단어들을 많이 포함해서 나온다는 것이고, 중복을 세지 않는다면 최대 100,000 번의 연산 횟수만 필요하므로, 따로 시간복잡도를 생각할 필요가 없는 문제이다.
3. 코드 🌐
(1) 순열 풀이 CODE 💬
import java.util.*;
import java.io.*;
public class Main {
static int [] alphabet;
static StringBuilder ans = new StringBuilder ();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for(int i = 0; i < N; i ++){
String word = br.readLine();
alphabet = new int [26];
for(int j = 0; j < word.length(); j++){
alphabet[word.charAt(j) - 'a']++;
}
permutation(0, new char [word.length()], alphabet);
}
System.out.println(ans.toString());
}
public static void permutation(int depth, char [] answer, int [] alphabet) {
if(depth == answer.length){
ans.append(String.valueOf(answer)).append("\n");
return;
}
for(int i = 0; i < alphabet.length; i++){
if(alphabet[i] == 0) continue;
alphabet[i]--;
answer[depth] = (char)(i + 'a');
permutation(depth+1, answer, alphabet);
alphabet[i]++;
}
}
}
(2) NP 풀이 CODE ☕
import java.util.*;
import java.io.*;
public class Main {
static int [] alphabet;
static StringBuilder ans = new StringBuilder ();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for(int i = 0; i < N; i ++){
char [] arr = br.readLine().toCharArray();
Arrays.sort(arr);
ans.append(String.valueOf(arr)).append("\n");
while(np(arr)){};
}
System.out.println(ans.toString());
}
public static boolean np (char [] prev) {
// 1. 꼭대기 값 찾기
int peak = prev.length - 1;
while (peak > 0 && prev[peak - 1] >= prev[peak]) peak--;
if(peak == 0) return false;
// 2. left보다 큰 최소값 right 찾아서 둘이 자리 바꾸기
int left = peak - 1;
int right = prev.length - 1;
while(left < right && prev[left] >= prev[right]) right--;
char temp = prev[right];
prev[right] = prev[left];
prev[left] = temp;
// 3. 꼭대기의 오른편 오름차순 정렬
left = peak;
right = prev.length -1;
while(left < right) {
char temp2 = prev[right];
prev[right] = prev[left];
prev[left] = temp2;
left++;
right--;
}
ans.append(String.valueOf(prev)).append("\n");
return true;
}
}
4. 트러블 슈팅 or 배운 점
(1) 첫 번째 풀이 (메모리 초과)
처음 문제를 풀 때는, 주어진 단어의 글자마다 방문 배열을 만들었다.
즉 String s = abca
로 주어지면 s.charAt(0) ~ s.charAt(3)
까지에 해당하는 방문 배열을 만들었던 것이다. 하지만 이러면 메모리 초과가 난다. 이유는 해당 방문 배열은 중복 체크가 되지 않기 때문이다.
예를 들어 abca
라는 문자열이 들어왔다면, 다음과 같이 순서가 짜질 수 있다.
경우의 수 별 각 글자의 순서 | a | b | c | a |
---|---|---|---|---|
1번 | 1 | 2 | 3 | 4 |
2번 | 1 | 3 | 2 | 4 |
3번 | 4 | 2 | 3 | 1 |
4번 | 4 | 3 | 2 | 1 |
… | … | … | … | … |
위의 에시를 보면 1번과 3번, 2번과 4번은 나타내는 글자 조합이 같다. 즉 문자열의 위치마다 방문 배열을 나타내 재귀하는 풀이는 중복 제거를 하지 못하기 때문에, 불 필요한 재귀가 반복되고, 이로 인해 메모리 초과가 난다.
(2) String <-> char [] 변환
A. String.toCharArray()
String s1 = "Hello World";
char [] charArr = s1.toCharArray();
위와 같이 쓰면 s1의 문자열이 char형 배열로 바뀐다.
B. String.valueOf(char[])
String s2 = String.valueOf(charArr);
이렇게 쓰면 위에서 char 형 배열로 바뀐 charArr을 다시 문자열로 바꿀 수 있다.