[백준] 색종이 10163번 (PYTHON,JAVA)

✔ 문제 10163 색종이

문제 바로가기 💨 

10163번: 색종이

핵심 아이디어

먼저 색종이 번호를 해당하는 색종이 영역에 표시한다. 그리고 count를 이용해 빈도수를 세어준다.

이때 풀이시간을 단축하고 코드를 최적화해보자.먼저 빈도수 체크를 할때 처음에는 for 각 번호들에 대해, 전체 배열에서 각 번호수를 count했다.하지만 빈도수 체크 배열을 만들면 전체 배열 탐색을 한번만 탐색해도 된다.

또한,배열 초기화를 for j (sj, sj + w) : arr[i][j] = [n] * w으로 바꿔 슬라이싱을 사용해 좀 더 효율적인 코드를 만들 수 있다.

PYTHON

N = int(input())
arr = [[0] * 1001 for _ in range(1001)]
for n in range(1, N + 1):
    sj, si, w, h = map(int, input().split())
    for i in range(si,si + h):
        for j in range(sj, sj + w):
            arr[i][j] = n # 해당 번호 색종이 숫자를 영역에 표시

for n in range(1, N + 1): # 색종이 번호별 카운트
    cnt = 0
    for lst in arr:
        cnt += lst.count(n)
    print(cnt)

 

개선 풀이

N = int(input())
arr = [[0]*1001 for _ in range(1001)]
for n in range(1, N+1):
    sj, si, w, h = map(int, input().split())
    for i in range(si, si+h):
        arr[i][sj:sj+w] = [n]*w

cnts = [0]*(N+1)
for lst in arr:
    for n in lst:
        cnts[n] += 1
print(*cnts[1:], sep='\n')

JAVA

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] arr = new int[1001][1001];
        
        for (int n = 1; n <= N; n++) {
            int sj = sc.nextInt();
            int si = sc.nextInt();
            int w = sc.nextInt();
            int h = sc.nextInt();
            for (int i = si; i < si + h; i++){
                for (int j = sj; j < sj + w; j++){
                    arr[i][j] = n;
                }
            }
        }
        
        int[] cnts = new int[N + 1]; // [색종이번호] = 카운팅
        for(int[] row : arr) {
            for (int n : row) {
                cnts[n]++;
            }
        }
        for (int i = 1; i < cnts.length; i++){
            System.out.println(cnts[i]);
        }
    }
}