개수 구성 최대, 최소 정수

3445 단어 알고리즘
[최대 정수] n 개의 정수 가 설치 되 어 있 고 이 를 한 줄 로 연결 하여 가장 큰 여러 개의 정 수 를 구성한다.예 를 들 어 n = 3 시 에 3 개의 정수 13, 312, 343 이 고 연 결 된 최대 정 수 는 34331213 이다.또한 n = 4 시, 4 개의 정수 7, 13, 4, 246, 연 결 된 최대 정 수 는 7424613 이다.입력: n N 개 수 출력: 연 결 된 여러 비트 알고리즘 분석: 이 문 제 는 욕심 법 을 사용 하 는 것 을 쉽게 생각 할 수 있 습 니 다. 시험 을 볼 때 많은 학생 들 이 정 수 를 큰 것 에서 작은 것 으로 연결 하고 테스트 문제 의 예 도 모두 일치 하지만 마지막 테스트 결 과 는 모두 맞지 않 습 니 다.이런 기준 에 따 르 면 우 리 는 쉽게 반 례 를 찾 을 수 있다. 12, 121 은 12112 가 아니 라 12121 을 구성 해 야 한다. 그러면 서로 포함 할 때 어 릴 때 부터 어른 이 되 어야 하 는 것 이 아 닐 까?꼭 12, 123 이 12123 이 아니 라 12312 인 것 은 아니다. 이런 상황 은 여러 가지 가 있다.이 문 제 는 욕심 법 을 쓰 면 안 되 는 거 아 닙 니까?사실 이 문 제 는 욕심 법 으로 풀 수 있 습 니 다. 다만 방금 기준 이 틀 렸 습 니 다. 정확 한 기준 은 정 수 를 문자열 로 바 꾼 다음 에 a + b 와 b + a 를 비교 하 는 것 입 니 다. 만약 에 a + b > = b + a 라면 a 를 b 의 앞 에 놓 고 반대로 a 를 b 의 뒤에 놓 습 니 다.자바 원본 프로그램:
public static void main(String[] args){
  String str = "";
  ArrayList<String> array = new ArrayList<String>();
  Scanner in = new Scanner(System.in);
  System.out.println("Please input the number of data:");
  int n = in.nextInt();
  System.out.println("Please input the data:");
  while (n-- > 0) {
   array.add(in.next());   
  }
  for(int i = 0; i < array.size(); i ++)
   for(int j = i + 1; j < array.size(); j ++){
    if((array.get(i) + array.get(j)).compareTo(array.get(j) + array.get(i)) < 0){
     String temp = array.get(i);
     array.set(i, array.get(j));
     array.set(j, temp);
    }
   }  
  for(int i = 0; i < array.size(); i ++){
   str += array.get(i);
  }
  System.out.println("str=:"+str);  
 }
}

좋은 웹페이지 즐겨찾기