글 읽기 - 반례 좀 부탁드립니다

han03092 3년 전 0

바로 밑에 질문하신 분과 비슷한 방법으로 구현하였습니다.

1. 36진수의 각 알파벳에 해당하는 객체배열 생성 alphabets[i];

2. input을 순서대로 더하고, input에 해당 알파벳이 나타나면 자릿수 기록 alphabets[i].cnt[idx]

3. 알파벳을 Z로 바꾸었을 때 차이를 Amount라는 36진수 string배열로 저장

4. Amount가 큰것부터 K개를 골라 더함

게시판의 반례는 전부 맞았는데 바로 틀렸습니다가 나옵니다.

import java.util.*;
import java.io.*;
class Alphabet implements Comparable{
	Alphabet(int id){
		this.id = id;
	}
	int id;
	int cnt[] = new int[51];//자릿수표시
	String Amount;//해당 자리를 z로 바꿨을 때 차이를 36진수 string 배열로 저장.
	
	public char intToChar(int num) {
		char cur;
		if(num <= 9) {
			cur = (char) (num + 48);
		}
		else {
			cur = (char) (num + 55);
		}
		return cur;
	}// 번호를 알파벳으로 변환
	
	@Override
	public int compareTo(Object obj) {
		Alphabet a = (Alphabet) obj;
		if(this.Amount.length()==a.Amount.length()) {
			for(int i = 0; i < this.Amount.length(); i++) {
				if(this.Amount.charAt(i) == a.Amount.charAt(i))
					continue;
				else 
					return a.Amount.charAt(i) - this.Amount.charAt(i) ;
			}
		}
		
		return a.Amount.length() - this.Amount.length();
	}//compareTo -> amount가 클수록 앞에 와야됨, 길이가 길면 큰것
	//길이가 같으면 같은자리의 숫자를 비교, 같으면 continue 후 다음자리 비교.
	
	public void getSub() {//Z로 바꿧을 때 차이 구하기
		StringBuilder sb = new StringBuilder();
		int next = 0;//다음자리로 올라가는 값, 초깃값 0
		for(int i = 1; i < 51; i++) {
			int m = cnt[i]*(35-id);//Z - 현재 알파벳 * 갯수
			int left = (m+next)%36;//현재 자리에 남는 나머지
			next = (m+next)/36;//다음자리로 올라가는 값
			char x = this.intToChar(left);// 숫자를 36진수로 바꿔서 저장 
			sb.append(x);//
		}
		
		while(next>0) {
			int left = next%36;
			sb.append(this.intToChar(left));
			next = next/36;
		}//마지막으로 올려준 값은 아직 append안됬으니까 마무리해줌.
		
		sb.reverse().toString();
		//값이 거꾸로 저장되어있기때문에  reverse
		
		int cutAt = 0;
		for(int i = 0; i < sb.length(); i++) {
			if(sb.charAt(i)!='0') {
				cutAt= i;
				break;
			}
		}
		if(cutAt==0) this.Amount = "0";
		else
			this.Amount = sb.substring(cutAt, sb.length());
		//앞의 쓸데없는 0 지우기. 000000000111 -> 111
	}
}

public class Main {
	static int N,K;
	static ArrayList <String> nums = new ArrayList<String>();
 	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		Alphabet alphabets[] = new Alphabet[36];
		
		for(int i = 0; i <36; i++) {
			alphabets[i] = new Alphabet(i);
		}
		
		for(int i = 0; i < N; i++) {
			String t = br.readLine();
			int idx = 1;
			for(int j = t.length()-1; j >= 0; j--) {
				char cur = t.charAt(j);
				int a = 0;
				if(cur >= 'A') {
					a = cur-'A'+10;
				}
				else {
					a = cur -'0';
				}
				alphabets[a].cnt[idx]++; //해당 알파벳의 자리 갯수 ++, 편의를 위해 순서를 거꾸로 뒤집음, 1의자리가 cnt의 첫번째
				idx++;
			}
			nums.add(t);
		}
		
		StringBuilder init = new StringBuilder("0");//처음 숫자와 더할 값 = 0
		for(int i = 0; i < N; i++) {
			init = new StringBuilder(Sum(init.toString(),nums.get(i)));
		}//기존 input의 총합.
		
		for(int i = 0; i < 36; i++) {
			alphabets[i].getSub();
		}//각 알파벳을 Z로 바꿧을 때 차이를 구함.
		
		Arrays.sort(alphabets);
		K = Integer.parseInt(br.readLine());
		for(int i = 0; i < K; i++) {
			String right = alphabets[i].Amount;
			init = new StringBuilder(Sum(init.toString(),right));
		}//Z로 바꿧을때 차이가 큰 것 부터 순서대로 K개를 더하면 정답.
		
		System.out.println(init);
 	}
 	
 	static int charToInt(char c) {
 		if(c <='9')
 			return c-'0';
 		else 
 			return c - 55;
 	}
 	
 	static char intToChar(int num) {
		char cur;
		if(num <= 9) {
			cur = (char) (num + 48);
		}
		else {
			cur = (char) (num + 55);
		}
		return cur;
	}//int to char
 	
 	static String Sum(String l, String r) {//36진수 덧셈
		StringBuilder result = new StringBuilder();
		int lL = l.length();
		int lR = r.length();
		StringBuilder longer = new StringBuilder();
		StringBuilder shorter = new StringBuilder();
		if(lL < lR) {
			while(true) {
				if(lL == lR) break;
				shorter.append(0);
				lL++;
			}
			longer.append(r);
			shorter.append(l);
		}
		else {
			while(true) {
				if(lL == lR) break;
				shorter.append(0);
				lR++;
			}
			longer.append(l);
			shorter.append(r);
		}//길이가 다르면 불편하니까 짧은 숫자 앞에 00000을 붙여줘서 길이를 맞춤

		int next = 0;
		//String longer + String shorter
		for(int i = longer.length()-1; i >= 0; i--) {
			int left = charToInt(longer.charAt(i)); // longer의 해당 자리 값을 int로 변환
			int right = charToInt(shorter.charAt(i)); // shorter의 해당 자리 값을 int로 변환
			int cur = (left+right+next)%36; //자리에 남는거
			result.append(intToChar(cur)); // 결과에 append
			next = (left+right+next)/36; //다음 자리 올라갈 값
		}
		
		//마지막 올라간 자리 덧셈
		while(next > 0) {
			int left = next%36;
			result.append(intToChar(left));
			next = next/36;
		}
		
		return result.reverse().toString();
		
	}
}

han03092 3년 전 0

해결했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 좀 부탁드립니다

han03092 3년 전 0

han03092 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말