오늘의 커밋을 대체할 단어 수학 질문 #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;
}
} |
Beta Was this translation helpful? Give feedback.
Replies: 2 comments 5 replies
-
|
우선, 인찬님 풀이방식으로 푸신것같은데.. 저는 인찬님 풀이를 정확히 이해하진 못해서 답변이 도움되지 않을수도있습니다..! 말씀해주신게 자릿수로 비교를 하신다고 하셨는데.. 문제에서 자릿수도 중요하지만 결국 중요한건 계수의 총 합이 가장 중요해요! 그래서 자릿수로 그리디를 적용하는게 아니라, 계수자체를 그리디로 적용해야합니다! |
Beta Was this translation helpful? Give feedback.
-
|
우선 문제에서 주어진 예제는 모두 통과 합니다! 최대자릿수로 하려고 한게 문제 인가 싶어서 나름 최적화라고 생각한 부분을 뺐더니 정훈님 예제로 말하면 B는 최고자릿수 3 A는 최고자릿수 2 이런식으로 입력받으면서 저장했고, |
Beta Was this translation helpful? Give feedback.
-
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;
}
}통과한 코드는 위와 같은데 비교하는 부분을 뺐더니 됐어요! |
Beta Was this translation helpful? Give feedback.
-
|
위 답변과 같은말이지만... 제가 말씀드린 입력 예에서는 A가 B보다 최고자릿수는 낮지만 A가 높은 수를 배정받아야만 하는 경우입니다. |
Beta Was this translation helpful? Give feedback.
-
|
정훈님 예시를 오해했었네요 이해했어요 감사합니다! |
Beta Was this translation helpful? Give feedback.
-
|
저 비교하는 부분 코드를 보면 최고 높이가 같은 경우를 2가지로 제한하고 있지 않나하는 의문이 들긴 했습니다! 또 정훈님이 말씀해주신 것처럼 최고자릿수만으로 판단하기에는 반례가 상당히 많습니다. |
Beta Was this translation helpful? Give feedback.
-
|
제가 최고 자릿수라고 적긴했었지만 계수를 최고자릿수로 저장했어요. 좋은 반례 감사합니다! |
Beta Was this translation helpful? Give feedback.
우선, 인찬님 풀이방식으로 푸신것같은데.. 저는 인찬님 풀이를 정확히 이해하진 못해서 답변이 도움되지 않을수도있습니다..!
말씀해주신게 자릿수로 비교를 하신다고 하셨는데.. 문제에서 자릿수도 중요하지만 결국 중요한건 계수의 총 합이 가장 중요해요!
극단적인 예이긴 하지만 예를 들어 입력으로 다음과 같이 들어온다면
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을 대입해줘야합니다!