백준 1339번 단어 수학

domybest·2021년 4월 10일
0

백준

목록 보기
23/36
post-thumbnail

문제
풀이 코드

알고리즘

ABC를 십진수로 본다면 100A + 10B + C로 표현할 수 있을 것이다. 이를 이용하여 문제를 해결한다. 예시로 주어진 GCF + ACDEB 같은 경우는 10000A + 1010C + 100D + 100G + 10E + B + F이다. 계수가 큰 곳에 순서대로 9 8 7 .. 을 대입 해주면 가장 큰 수가 만들어 질 수 있겠다. 그럼 이 과정을 어떻게 구현할 수 있을까?

알파벳 별 카운트를 계산할 수 있는 count 배열을 만든다. 알파벳은 26개가 있으므로 배열의 크기는 26이다. 그리고 A는 0, B는 1, C는 2의 인덱스와 연결 될 수 있도록 한다.
A가 입력 되면 count[입력된 A - 'A'] 를 하면 count[0]에 저장이 되고 B가 입력이 되면 count[입력된 B - 'A'] 로 count[1]에 저장이 된다. 따라서 뒤에 'A'를 빼주면 성공적으로 연결이 가능하다. 그 후 그 인덱스에 저장할 값은 pow(10, 주어진 문자열 길이 - 1) 이다.

저장이 모두 끝난 후에는 내림차순으로 정렬하여 순서대로 9 8 7 6.. 을 곱한 후 모두 더해 최종 결과를 출력한다.

오름차순 정렬은 Arrays.sort(array) 한 줄로 O(nlogn)을 보장하는 정렬이 가능하다. 내림차순은 어떻게 할까? Arrays.sort(array, Collections.reverseOrder()) 과 같이 뒤에 내림차순 정렬 Comparator를 인자로 넘겨준다. 다만 Collections 클래스의 메소드이기 때문에 Wrapper 클래스가 아닌 단순 int 배열 등은 이런식으로 내림차순이 불가능하다는 것을 기억하자.

Integer[] arr = new Integer[n]; 과 같은 Wrapper 클래스 배열은 int[] 배열처럼 자동으로 0 초기화가 되지 않는다. 따라서 초기화를 해 주어야 사용할 수 있고 그렇지 않고 사용하게 되면 NullPointerException을 발생시키는 현상을 확인할 수 있었다.

int 형에서 compare 메소드나 compareTo 메소드를 구현할 때 return 값은 a - b 혹은 Integer.compare(a, b) 로 해주면 된다. String 형은 어떻게 할까?
a.compareTo(b) 로 리턴해 주면 된다. 물론 내림차순 기준이다.

profile
기억할 때 까지 반복!

0개의 댓글