오늘의 커밋을 대체할 단어 수학 질문 #115
|
인찬님 풀이 보고나니까 이런 질문 하기 머쓱하긴 하지만...! 저는 최고 자릿수 비교하고, import java.io.*;
public class Main {
static int N; // 단어의 개수 - 최대 10
static int alphabetCount = 0; // 총 사용된 알파벳 수
static String[] words;
static int[] top; // 각 알파벳별 최고 자릿수
static int[] check; // 최종 매칭 저장
public static void main(String[] args) throws IOException{
System.setIn(new FileInputStream("input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
words = new String[N];
top = new int[26];
check = new int[26];
for(int i = 0 ; i < 26 ; i++){
top[i] = -1;
check[i] = -1;
}
for(int i = 0 ; i<N ; i++){
String word = br.readLine();
words[i] = word;
for(int j = 0 ; j< word.length(); j++){
// 사용한적 없는 알파벳이 사용되면 알파벳수 추가
int index = word.charAt(j)-'A';
int position = word.length() - j - 1;
if(top[index]==-1) alphabetCount++;
if(top[index]<position) top[index] = position;
}
}
// 가장 높은 자릿수 위치의 알파벳 구해서 9부터 차례로 대입
int biggest = 0 ;
int num = 9;
while(alphabetCount -- > 0){
for(int i = 0 ; i<26; i++){
// 이미 알파벳을 배정받았으면 넘어가기
if(check[i] != -1) continue;
// 최고 높이 비교후 교체
if(top[i]>top[biggest]){
biggest = i;
// 최고 높이가 같을때
}else if(top[i]== top[biggest] && i!=biggest){
check[i] = num;
int num_i = getResult(); // i 에 num이 들어간다면
check[i] = -1;
check[biggest] = num;
int num_biggest = getResult(); // biggiest에 num이 들어간다면
check[biggest] = -1;
if(num_i>num_biggest) biggest = i;
}
}
check[biggest] = num --;
// 다음 biggest 설정
for(int i = 0 ; i<26; i++){
if(check[i]==-1) {
biggest = i;
break;
}
}
}
int sum = getResult();
System.out.println(sum);
br.close();
}
// 현재까지 설정된 알파벳의 값을 이용하여 결과 계산
static int getResult(){
int sum = 0;
for(int i = 0 ; i<N ; i++){
for(int j = 0; j<words[i].length(); j++){
char temp = words[i].charAt(j) ;
// 배정받은 숫자가 없으면 넘어간다
if(check[temp- 'A']==-1) continue;
int num = check[temp - 'A'];
sum += Math.pow(10, words[i].length()-j -1)* num;
}
}
return sum;
}
} |
Replies: 2 comments 5 replies
|
우선, 인찬님 풀이방식으로 푸신것같은데.. 저는 인찬님 풀이를 정확히 이해하진 못해서 답변이 도움되지 않을수도있습니다..! 말씀해주신게 자릿수로 비교를 하신다고 하셨는데.. 문제에서 자릿수도 중요하지만 결국 중요한건 계수의 총 합이 가장 중요해요! 그래서 자릿수로 그리디를 적용하는게 아니라, 계수자체를 그리디로 적용해야합니다! |
|
우선 문제에서 주어진 예제는 모두 통과 합니다! 최대자릿수로 하려고 한게 문제 인가 싶어서 나름 최적화라고 생각한 부분을 뺐더니 정훈님 예제로 말하면 B는 최고자릿수 3 A는 최고자릿수 2 이런식으로 입력받으면서 저장했고, |
import java.io.*;
public class Main {
static int N; // 단어의 개수 - 최대 10
static int alphabetCount = 0; // 총 사용된 알파벳 수
static String[] words;
static int[] top; // 각 알파벳별 최고 자릿수
static int[] check; // 최종 매칭 저장
public static void main(String[] args) throws IOException{
System.setIn(new FileInputStream("input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
words = new String[N];
top = new int[26];
check = new int[26];
for(int i = 0 ; i < 26 ; i++){
top[i] = -1;
check[i] = -1;
}
for(int i = 0 ; i<N ; i++){
String word = br.readLine();
words[i] = word;
for(int j = 0 ; j< word.length(); j++){
// 사용한적 없는 알파벳이 사용되면 알파벳수 추가
int index = word.charAt(j)-'A';
int position = word.length() - j - 1;
if(top[index]==-1) alphabetCount++;
if(top[index]<position) top[index] = position;
}
}
// 가장 높은 자릿수 위치의 알파벳 구해서 9부터 차례로 대입
int num = 9;
while(alphabetCount -- > 0){
int[] temp = {0,0};
for(int i = 0 ; i<26; i++){
// 이미 알파벳을 배정받았으면 넘어가기
if(check[i] != -1) continue;
check[i] = num;
int result = getResult();
if(temp[0]<result){
temp[0] = result;
temp[1] = i;
}
check[i] = -1;
}
check[temp[1]] = num--;
}
System.out.println(getResult());
br.close();
}
// 현재까지 설정된 알파벳의 값을 이용하여 결과 계산
static int getResult(){
int sum = 0;
for(int i = 0 ; i<N ; i++){
for(int j = 0; j<words[i].length(); j++){
char temp = words[i].charAt(j) ;
// 배정받은 숫자가 없으면 넘어간다
if(check[temp- 'A']==-1) continue;
int num = check[temp - 'A'];
sum += Math.pow(10, words[i].length()-j -1)* num;
}
}
return sum;
}
}통과한 코드는 위와 같은데 비교하는 부분을 뺐더니 됐어요! |
|
위 답변과 같은말이지만... 제가 말씀드린 입력 예에서는 A가 B보다 최고자릿수는 낮지만 A가 높은 수를 배정받아야만 하는 경우입니다. |
|
정훈님 예시를 오해했었네요 이해했어요 감사합니다! |
|
저 비교하는 부분 코드를 보면 최고 높이가 같은 경우를 2가지로 제한하고 있지 않나하는 의문이 들긴 했습니다! 또 정훈님이 말씀해주신 것처럼 최고자릿수만으로 판단하기에는 반례가 상당히 많습니다. |
|
제가 최고 자릿수라고 적긴했었지만 계수를 최고자릿수로 저장했어요. 좋은 반례 감사합니다! |
우선, 인찬님 풀이방식으로 푸신것같은데.. 저는 인찬님 풀이를 정확히 이해하진 못해서 답변이 도움되지 않을수도있습니다..!
말씀해주신게 자릿수로 비교를 하신다고 하셨는데.. 문제에서 자릿수도 중요하지만 결국 중요한건 계수의 총 합이 가장 중요해요!
극단적인 예이긴 하지만 예를 들어 입력으로 다음과 같이 들어온다면
BAAA
AAA
AAA
AAA
AAA
AAA
AAA
AAA
AAA
AAA
B=9, A=8 일때는 17880이지만
A=9, B=8 일때는 17990이 나와서 더 큰값이됩니다.
그래서 자릿수로 그리디를 적용하는게 아니라, 계수자체를 그리디로 적용해야합니다!
BAAA 는 1000B + 100A + 10A + 1A이고
AAA 는 100A + 10A + 1A 이므로,
위 입력의 총 합은 1110A + 1000B 가 됩니다. 따라서 A에 가장 큰수인 9를 대입해야하고 B에 8을 대입해줘야합니다!