[SWEA] 4789 - 성공적인 공연 기획 (자바 / Java)

 

입력되는 string의 각 index는 0부터 시작해서 최소 index명 이상이 박수치고 있을 때 자신도 박수를 친다는 것을 뜻한다.

즉 string이 "110011" 일 때, 세 번째 0은 index가 2이고, 2명 이상 박수치고 있을 때 자신이 박수를 친다는 것이다.

이에 따라 문자열을 char 배열로 바꾼 후, 앞자리부터 박수를 치고 있는 사람의 수를 누적합하여 count 배열을 생성하였다.

			char[] people = sc.next().toCharArray();
			int[] count = new int[people.length];
			for (int i = 0; i < count.length; i++) {
				if (i == 0)
					count[i] = people[i] - '0';
				else {
					count[i] = count[i - 1] + people[i] - '0'; // count는 누적 합
				}
			}
			// count의 index는 i명 이상이 박수칠 때 자신도 박수를 치는 사람들
			// 누적합인 각 index의 값이 i+1 이상일 때 모든 사람이 박수칠 수 있음

각주에 설명한 것처럼, count의 각 index는 i명 이상이 박수칠 때 자신도 박수를 치는 사람들을 의미한다.

index가 i일 때, i-1까지의 누적합이 i가 되어야 하므로, 각각의 index는 i+1 이상이 되어야 한다.

			int need = 0;
			for (int i = 0; i < count.length; i++) {
				if (count[i] + need < i + 1) {
					need += (i + 1 - count[i] - need); //
				}
			}

모든 사람이 박수를 치기 위해 필요한 수를 need라고 하고, count[i]가 i+1보다 작은 만큼, need를 증가시켜주었다.

이때 need의 최종값이 답이 된다.

---

전체 코드

package SWEA0809;

import java.util.Scanner;

public class SWEA_4789_성공적인공연기획 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			char[] people = sc.next().toCharArray();
			int[] count = new int[people.length];
			for (int i = 0; i < count.length; i++) {
				if (i == 0)
					count[i] = people[i] - '0';
				else {
					count[i] = count[i - 1] + people[i] - '0'; // count는 누적 합
				}
			}
			// count의 index는 i명 이상이 박수칠 때 자신도 박수를 치는 사람들
			// 누적합인 각 index의 값이 i+1 이상일 때 모든 사람이 박수칠 수 있음
			int need = 0;
			for (int i = 0; i < count.length; i++) {
				if (count[i] + need < i + 1) {
					need += (i + 1 - count[i] - need); //
				}
			}
			System.out.println("#" + (t + 1) + " " + need);

		}

	}

}