섹션 4. HashMap, TreeSet (해쉬, 정렬지원 Set) 5. K번째 큰 수

문제

• 현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다.
• 현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다.
• 기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하세요.
• 만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값은 22입니다.

입력

• 첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50) 입력되고, 그 다음 줄에 N개의 카드값이 입력된다.

출력

• 첫 줄에 K번째 수를 출력합니다. K번째 수가 존재하지 않으면 -1를 출력합니다.

입출력 예제

---

풀이방식

이번 문제는 TreeSet 를 사용하여 푸는 문제이다.

---

설계과정

1. TreeSet을 선언한다.

2. 3중 for문을 통해 3개 숫자의 합산값을 구한다.

3. K 번째 수를 찾아 합산값을 출력한다.

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. int 형으로 메소드를 작성한다.

 

3. 결과값을 출력할  result와 TreeSet을 선언한다.

• 이 때 result는 'K번째 수가 없으면 -1 출력' 이라는 조건을 충족하기 위해 -1로 초기화한다.
• TreeSet : 이진 탐색 트리 구조로 되어있으며, 정렬을 자동으로 해준다.
• Collections.reverseOrder() : 내림차순으로 정렬해준다. 생략하면 자동으로 오름차순 정렬이 된다.

3. 3중 for문을 작성한다. 단, 중복을 제거해야 하므로 앞 수에서 1씩 더해서 작성한다.

4. for문을 통해 뽑아낸 3개의 수를 전부 더해서 TreeSet에 넣는다.

5. K번째 수를 찾기 위해 cnt를 선언한다.

6. x와 Tset의 값을 하나씩 매칭하며 cnt 값을 증가시킨다.

• 내림차순으로 출력된 3개의 합들에 순서를 주기 위해서이다.

7. cnt와 K가 동일하면 결과를 출력한다.

---

해당 글은 인프런 >자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.