[백준 알고리즘] 백준 20937번 떡국 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 20937번 떡국 자바(Java)

1) 문제번호 : 20937번

 

2) 문제 출처

www.acmicpc.net/problem/20937

20937번: 떡국

 

2. 문제

Naver D2를 아시나요? D2는 For Developers, By Developers의 약자로, 개발자들을 위해 개발자들이 직접 만들어 가고 있는 네이버 개발자 지원 프로그램입니다. 네이버가 축적한 기술과 지식을 공유하고, 외부 개발자들을 지원해 대한민국 개발자 역량 강화를 이끌고, 이를 통해 업계 전체와 네이버가 함께 성장하는 선순환 구조를 만들고자 합니다.

사실 네이버의 개발자 지원은 오랜 기간 꾸준히 이어져 왔습니다. 개발자 컨퍼런스 DEVIEW를 비롯, 오픈 소스와 개발 도구 공개, 학회 및 커뮤니티 지원 등 여러 지원 프로그램이 있었습니다. 이런 다양한 프로그램을 하나로 통합한 것이 바로 Naver D2입니다.

함께 성장하는 개발자 지원 프로그램인 NAVER D2에서는 매년 개발자 컨퍼런스 DEVIEW를 개최한다.

2021년 DEVIEW에도 다양한 주제를 선보이기 위한 발표 준비 작업이 한창이다. 그런데 아주 큰 문제가 생겼다. 책상 위에 다 먹고 남은 떡국 그릇이 너무 많이 쌓여 작업을 진행할 수가 없다. 우연히 옆을 지나가던 당신이 이를 도와주기로 했다!

떡국 그릇 위에는 크기가 더 작은 떡국 그릇 하나를 쌓을 수 있다. 쌓은 떡국 그릇 위에 같은 방법으로 떡국 그릇을 또 쌓을 수 있다. 예를 들어, 크기가 4, 2, 3, 1인 떡국 그릇에 대해 4−3−2−1 순서로 쌓을 수 있지만 3−4−2−1 순서로는 쌓을 수 없다. 이렇게 쌓은 한 개 이상의 떡국 그릇들을 떡국 그릇 탑이라고 하자.

당신은 떡국 그릇 탑의 개수를 최소로 만들어 책상 위의 공간을 확보하려고 한다.

다음은 4, 2, 3, 1, 2인 떡국 그릇으로 쌓을 수 있는 떡국 그릇 탑의 개수의 예시이고, 최소 개수는 2개이다.

• 5개 : [4,2,3,1,2]
• 4개 : [4−2,3,1,2] 또는 [4−3,2,1,2] 또는 [4,3−2,1,2] 또는 ⋯
• 3개 : [4−2,3−1,2] 또는 [4−1,3−2,2] 또는 [4−3,2−1,2] 또는 ⋯
• 2개 : [4−2,3−2−1] 또는 [4−2−1,3−2] 또는 [4−3−2,2−1] 또는 ⋯
• 1개의 떡국 그릇 탑으로 만들 수 없다.

떡국 그릇들의 크기가 주어졌을 때, 떡국 그릇 탑의 최소 개수를 구해주자. 당신에게 감사의 표시로 NAVER D2에서 후원하는 SUAPC 2021w의 한 문제를 정답 처리해줄 것이다.

 

3. 제약사항

- 

4. 입력

다음과 같이 입력이 주어진다.

N

c1 c2 ... cN

• N은 떡국 그릇의 개수이다. (1≤N≤500000)
• ci는 i번째 떡국 그릇의 크기이다. (1≤ci≤50000)
• 입력으로 주어지는 모든 수는 정수다.

 

5. 출력

떡국 그릇 탑의 최소 개수를 출력한다.

 

6. 풀이

- 풀이 내용은 소스코드에 주석을 참고하면 된다.

7. 소스 코드

1) 맞은 소스 코드

- 오름차순으로 정렬해서, 앞에 값이 뒤의 값과 같으면 count를 1씩 증가시켜서 최대값이 결국엔 떡국 탑의 개수가 된다.

- 예를 들어, 1 2 3 4 1 2 3 4 1 2 3 4가 있으면 정렬하면 111222333444가 있어서 중복값이 각 숫자마다 3이 된다.

- count는 3이 되어 아무리 최대값을 비교해도 result는 3이된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
   public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(br.readLine()); //떡국 그릇의 개수
      
      int[] arr = new int[N]; //떡국 크기 입력 배열
      
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      //떡국 크기 입력
      for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
      
      //오름차순 정렬
      Arrays.sort(arr);
      
      int result = 1;
      int count = 1;
      
      //앞에 것이 뒤에 것과 같으면 count를 1씩 증가하고, 중복되는 것이 결국 떡국 탑 개수
      for(int i=1;i<N;i++) {
    	  if(arr[i]==arr[i-1]) {
    		  count++;
    		  result = Math.max(result, count);
    	  }
    	  //앞에 것과 뒤가 다르면 count는 1로 초기화
    	  else count = 1;
      }
      
      System.out.println(result);
   }
}

 

2) 틀린 소스 코드

- 떡국 크기 ArrayList를 오름차순으로 정렬을 해서, 뒤에서부터 리스트에 맨 뒤에 가장 큰 떡국 크기를 버리고, 그 값을 num에 저장한 다음, 반복문을 돌려 그 전의 값들이 num보다 작으면 그 값도 삭제를 하고, 삭제한 값을 다시 num에 넣어 떡국 한 층을 증가하는 걸로 설계를 했었다.

- 하지만, 시간초과와 떡국은 1그릇으로 탑을 이룰 수 없기에 틀린 소스 코드가 되었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N =Integer.parseInt(br.readLine());
		ArrayList<Integer> List = new ArrayList<>();
		int result = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
        
		//떡국 크기 입력
		for(int i=0;i<N;i++) List.add(Integer.parseInt(st.nextToken()));
		
		//떡국 크기 오름차순으로 정렬
		Collections.sort(List);
		
		//List가 빌 때까지 반복
		while(!List.isEmpty()) {
			//리스트에서 맨 뒤에 가장 큰 떡국 크기를 버린 값을 num에 저장
			int num = List.remove(List.size()-1);
			
			//맨 뒤에서부터 0까지 반복을 하는데
			for(int i=List.size()-1;i>=0;i--) {
				//i번째에 있는 List의 값이 num보다 작으면 그 i번째 List의 값을 삭제한다
				if(List.get(i)<num) {
					num = List.remove(i);
				}
			}
			//다 삭제되면 떡국 탑의 개수 1개 증가
			result++;
		}
		System.out.println(result);
		
		
	}
}

---