✅ 문제 소개
✅ 실패한 이유 - 시간초과
원인으로 두가지가 있습니다.
- ArrayList의 contains는 O(n)의 시간복잡도가 발생합니다.
사용한 숫자인지 확인하는 과정에서 contains를 사용하는데 여기서도 최대10!*10만큼의 시간 복잡도가 발생합니다.
if(!answer.contains(target)){
answer+=target;
dfs(location+1, level, answer);
answer = answer.substring(0,answer.length()-1);
}- ArrayList의 indexOf는 O(n)의 시간복잡도가 발생합니다.
만든 경우의 수에 해당 단어의 알파벳이 어떤 가중치를 가지고 있는지 찾는 과정에서 indexOf를 사용했는데 최대10!*10만큼의 시간 복잡도가 발생합니다.
for(String str : word.split("")){
String indexNumber = answer.charAt(alphabetList.indexOf(str))+"";
changedNumber += indexNumber;
}따라서 제 풀이는 여러 곳에서 많은 곳에서 시간 초과를 발생할 수 있는 부분이 발견되었습니다.
이 문제의 경우 시간 제한이 2초이며 그러면 최대 2억번의 연산이 발생할 수 있습니다. 그러나 저는 이미 3억을 2번이나 사용하고 있는 상황이라서 이 부분을 고쳐야겠다고 생각했습니다.
✅ 본인의 접근방법
일단 위 문제에 따라서 ArrayList를 사용하지 않기로 했습니다.
- ArrayList의 contains를 통해서 들렸던 숫자인지 확인하지 않고 boolean 형태의 상태 배열을 만들어 확인했습니다.
for(int i=0;i<10;i++){
if(!visited[i]){
visited[i]=true;
map.put(usedAlphabet[location],i);
dfs(location+1, level,map);
map.remove(usedAlphabet[location]);
visited[i]=false;
}
}- 중복된 알파벳이 등장하지 않도록 Set을 이용하였고, 그 Set을 String 배열로 바꿔 index로 접근이 가능한 상태로 만들었습니다.
이 index에 대한 접근은 dfs가 몇번 진행되었는지를 나타내는 location이라는 매개변수를 통해서 가능합니다.
Set<String> set = new HashSet<>();
Map<String,Integer> map = new HashMap<>();
int wordCount = Integer.parseInt(br.readLine());
for(int i=0;i<wordCount;i++){
wordTokenList.add(br.readLine().split(""));
Arrays.stream(wordTokenList.get(i)).forEach(v->set.add(v));
}
int level = set.size();
usedAlphabet = set.toArray(String[]::new);
dfs(0,level,map); static void dfs(int location , int level, Map<String , Integer> map){
if(level==location){
int sumResult = makeSum(map);
if(max<sumResult){
max = sumResult;
}
return;
}
for(int i=0;i<10;i++){
if(!visited[i]){
visited[i]=true;
map.put(usedAlphabet[location],i);
dfs(location+1, level,map);
map.remove(usedAlphabet[location]);
visited[i]=false;
}
}
}- ArrayList의 indexOf를 사용하지 않도록 Map을 사용하여 등장한 알파벳을 key로 그리고 거기에 부여된 가중치 숫자를 value로 넣어 만들었습니다. 그래서 다음과 같이 Map의 get() 메서드를 통해서 접근이 가능합니다.
static int makeSum(Map<String,Integer> map){
int sum =0;
for(String[] tokens : wordTokenList){
int wordNum = 0;
for(String token : tokens){
wordNum*=10;
wordNum += map.get(token);
}
sum+= wordNum;
}
return sum;
}✅ 새롭게 알게된 사실
ArrayList의 시간복잡도
add : O(1)
remove : O(n)
get : O(1)
Contains : O(n)
iterator.remove : O(n)
나의 틀린 풀이
import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
static List<String> wordList = new ArrayList<>();
static List<String> alphabetList = new ArrayList<>();
static Integer max = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// N개의 단어로 이루어져 있다
// 각 단어 알파벳 대문자
// 대문자를 0부터9까지의 숫자 하나로 바꿔서 N개의 수를 합하는 문제
// 같은 알파벳은 같은 숫자로
// 두 개 이상의 알파벳이 같은 숫자로 바뀌어서는 안된다
// 주어진 단어
// 몇 개의 알파벳이 등장하는가?
// 각 알바펫에 숫자를 부여하고
// 그 합을 최대로 하는 그 값을 정하기
int wordCount = Integer.parseInt(br.readLine());
Set<String> wordSet = new HashSet<>();
for(int i=0;i<wordCount;i++){
String enterWord = br.readLine();
wordList.add(enterWord);
// 알파벳이 들어가는 과정
for(String c : enterWord.split("")){
wordSet.add(c);
}
}
int level = wordSet.size();
alphabetList = new ArrayList<>(wordSet);
dfs(0,level,"");
System.out.println(max);
}
static void dfs(int location , int level, String answer){
if(level==location){
int sumResult = makeSum(answer);
if(max<sumResult){
max = sumResult;
}
return;
}
for(int i=0;i<10;i++){
String target = Integer.toString(i);
if(!answer.contains(target)){
answer+=target;
dfs(location+1, level, answer);
answer = answer.substring(0,answer.length()-1);
}
}
}
static int makeSum(String answer){
int sum =0;
for(int i=0;i<wordList.size();i++){
// 단어 꺼내기
String word = wordList.get(i);
String changedNumber = "";
// 단어 알파벳으로 분리
for(String str : word.split("")){
String indexNumber = answer.charAt(alphabetList.indexOf(str))+"";
changedNumber += indexNumber;
}
sum+= Integer.parseInt(changedNumber);
}
return sum;
}
}
나의 맞춘 풀이
import java.io.*;
import java.util.*;
public class Main {
static List<String[]> wordTokenList = new ArrayList<>();
static String[] usedAlphabet ;
static boolean[] visited = new boolean[10];
static Integer max = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// N개의 단어로 이루어져 있다
// 각 단어 알파벳 대문자
// 대문자를 0부터9까지의 숫자 하나로 바꿔서 N개의 수를 합하는 문제
// 같은 알파벳은 같은 숫자로
// 두 개 이상의 알파벳이 같은 숫자로 바뀌어서는 안된다
// 주어진 단어
// 몇 개의 알파벳이 등장하는가?
// 각 알바펫에 숫자를 부여하고
// 그 합을 최대로 하는 그 값을 정하기
Set<String> set = new HashSet<>();
Map<String,Integer> map = new HashMap<>();
int wordCount = Integer.parseInt(br.readLine());
for(int i=0;i<wordCount;i++){
wordTokenList.add(br.readLine().split(""));
Arrays.stream(wordTokenList.get(i)).forEach(v->set.add(v));
}
int level = set.size();
usedAlphabet = set.toArray(String[]::new);
dfs(0,level,map);
bw.write(Integer.toString(max));
bw.flush();
bw.close();
}
static void dfs(int location , int level, Map<String , Integer> map){
if(level==location){
int sumResult = makeSum(map);
if(max<sumResult){
max = sumResult;
}
return;
}
for(int i=0;i<10;i++){
if(!visited[i]){
visited[i]=true;
map.put(usedAlphabet[location],i);
dfs(location+1, level,map);
map.remove(usedAlphabet[location]);
visited[i]=false;
}
}
}
static int makeSum(Map<String,Integer> map){
int sum =0;
for(String[] tokens : wordTokenList){
int wordNum = 0;
for(String token : tokens){
wordNum*=10;
wordNum += map.get(token);
}
sum+= wordNum;
}
return sum;
}
}
꾸준하게 Ready, Set, Go!