2017 카카오코드 예선카카오프렌즈 컬러링북

https://school.programmers.co.kr/learn/courses/30/lessons/1829

프로그래머스

 

파이썬

def solution(m: int, n: int, picture: list):
    def visit(x, y, start, prev_color):
        if (x, y) in visited:
            return
        if picture[x][y] == prev_color:
            visited.add((x, y))
            counters[start] += 1
            if x + 1 < m:
                visit(x + 1, y, start, prev_color)
            if x - 1 >= 0:
                visit(x - 1, y, start, prev_color)
            if y + 1 < n:
                visit(x, y + 1, start, prev_color)
            if y - 1 >= 0:
                visit(x, y - 1, start, prev_color)
        return

    def find_start_xy():
        for x in range(m):
            for y in range(n):
                if (x, y) not in visited:
                    counters[(x, y)] = 0
                    return x, y

    def init_visited():
        for x in range(m):
            for y in range(n):
                if picture[x][y] == 0:  # 0인 원소들을 방문한 것으로 처리하면, 나중에 카운트 되지 않는다. 
                    visited.add((x, y))  

    visited = set()
    counters = {}
    init_visited()
    while len(visited) < m * n:
        start_x, start_y = find_start_xy()
        visit(start_x, start_y, (start_x, start_y), picture[start_x][start_y])
    return len(counters), sorted(counters.values())[-1]


print(solution(6, 4, [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]))

set의 차집합으로 ...

def solution(m: int, n: int, picture: list):
    def visit(x, y, start, prev_color):
        if (x, y) in visited:
            return
        if picture[x][y] == prev_color:
            visited.add((x, y))
            counters[start] += 1
            if x + 1 < m:
                visit(x + 1, y, start, prev_color)
            if x - 1 >= 0:
                visit(x - 1, y, start, prev_color)
            if y + 1 < n:
                visit(x, y + 1, start, prev_color)
            if y - 1 >= 0:
                visit(x, y - 1, start, prev_color)
        return

    def find_start_xy():
        # for 문은 O(N**2). 
        # set의 차집합 연산은 O(len(table) + len(visited)).
        nonlocal table     
        table -= visited
        x, y = table.pop()
        counters[(x, y)] = 0
        return x, y

    def init_table_visited():
        for x in range(m):
            for y in range(n):
                table.add((x, y))  # 추가
                if picture[x][y] == 0:
                    visited.add((x, y))

    table = set()  # 추가
    visited = set()
    counters = {}
    init_table_visited()
    while len(visited) < m * n:
        start_x, start_y = find_start_xy()
        visit(start_x, start_y, (start_x, start_y), picture[start_x][start_y])
    return len(counters), sorted(counters.values())[-1]


print(solution(6, 4, [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]))

차집합보다는...
not_visited set을
만드는 것이
더 좋은 방법이다. 

def solution(m: int, n: int, picture: list):
    def visit(x, y, start, prev_color):
        if (x, y) not in not_visited:
            return
        if picture[x][y] == prev_color:
            not_visited.remove((x, y))
            counters[start] += 1
            if x + 1 < m:
                visit(x + 1, y, start, prev_color)
            if x - 1 >= 0:
                visit(x - 1, y, start, prev_color)
            if y + 1 < n:
                visit(x, y + 1, start, prev_color)
            if y - 1 >= 0:
                visit(x, y - 1, start, prev_color)
        return

    def get_start_xy():
        # set에서 하나의 원소만 검색하는 방법은?
        # 1. 가장 느림
        # start_xy = not_visited.pop()
        # not_visited.add(start_xy)
        # 2. 중간
        start_xy = next(iter(not_visited))
        # 3. 가장 빠름
        # start_xy = tuple()
        # for each in not_visited:
        #     start_xy = each
        #     break
        counters[start_xy] = 0
        return start_xy

    def init_not_visited():
        for x in range(m):
            for y in range(n):
                if picture[x][y] != 0:
                    not_visited.add((x, y))

    not_visited = set()
    counters = {}
    init_not_visited()
    while len(not_visited) > 0:
        start_x, start_y = get_start_xy()
        visit(start_x, start_y, (start_x, start_y), picture[start_x][start_y])
    return len(counters), sorted(counters.values())[-1]


print(solution(6, 4, [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]))

[참고] set의 열거 방식에 따른 퍼포먼스 차이.
https://www.geeksforgeeks.org/iterate-over-a-set-in-python/

여기에 추가로 pop, add 를 같은 방식으로 테스트 해보니.. 

 

자바

import java.util.*;

class Solution {
    boolean[][] visited;
    int visited_count = 0;
    HashMap<int[], Integer> counters = new HashMap<>();

    void init_visited(int m, int n, int[][] picture) {
        for (var x = 0; x < m; x++)
            for (var y = 0; y < n; y++)
                if (picture[x][y] == 0) {
                    visited[x][y] = true;
                    visited_count++;
                }
    }

    int[] get_start_xy(int m, int n) {
        for (var x = 0; x < m; x++) {
            for (var y = 0; y < n; y++) {
                if (!visited[x][y]) return new int[]{x, y};
            }
        }
        return null;
    }

    void visit(int x, int y, int[] start, int prev_color, int m, int n, int[][] picture) {
        if (visited[x][y]) return;
        if (picture[x][y] == prev_color) {
            visited[x][y] = true;
            visited_count++;
            counters.put(start, counters.get(start) + 1);
            if (x + 1 < m) visit(x + 1, y, start, prev_color, m, n, picture);
            if (x - 1 >= 0) visit(x - 1, y, start, prev_color, m, n, picture);
            if (y + 1 < n) visit(x, y + 1, start, prev_color, m, n, picture);
            if (y - 1 >= 0) visit(x, y - 1, start, prev_color, m, n, picture);
        }
    }

    public int[] solution(int m, int n, int[][] picture) {
        visited = new boolean[m][n];
        init_visited(m, n, picture);

        while (visited_count < m * n) {
            var start = get_start_xy(m, n);
            counters.put(start, 0);
            visit(start[0], start[1], start, picture[start[0]][start[1]], m, n, picture);
        }

        return new int[]{
                counters.size(),
                counters.values().stream().max(Comparator.naturalOrder()).get()
        };
    }
}

import java.util.*;

class Solution {
    boolean[][] visited;
    int[][] starts;

    int visited_count = 0, start_count = 0;

    void init_visited(int m, int n, int[][] picture) {
        for (var x = 0; x < m; x++)
            for (var y = 0; y < n; y++)
                if (picture[x][y] == 0) {
                    visited[x][y] = true;
                    visited_count++;
                }
    }

    int[] get_start_xy(int m, int n) {
        for (var x = 0; x < m; x++) {
            for (var y = 0; y < n; y++) {
                if (!visited[x][y]) return new int[]{x, y};
            }
        }
        return null;
    }

    void visit(int x, int y, int[] start, int prev_color, int m, int n, int[][] picture) {
        if (visited[x][y]) return;
        if (picture[x][y] == prev_color) {
            visited[x][y] = true;
            visited_count++;
            starts[start[0]][start[1]] += 1;
            if (x + 1 < m) visit(x + 1, y, start, prev_color, m, n, picture);
            if (x - 1 >= 0) visit(x - 1, y, start, prev_color, m, n, picture);
            if (y + 1 < n) visit(x, y + 1, start, prev_color, m, n, picture);
            if (y - 1 >= 0) visit(x, y - 1, start, prev_color, m, n, picture);
        }
    }

    int find_max(int[][] arrays) {
        int max = 0;
        for (var array : arrays)
            for (var element : array)
                if (element > max) max = element;
        return max;
    }

    public int[] solution(int m, int n, int[][] picture) {
        visited = new boolean[m][n];
        starts = new int[m][n];
        init_visited(m, n, picture);

        while (visited_count < m * n) {
            var start = get_start_xy(m, n);
            starts[start[0]][start[1]] = 0;
            start_count++;
            visit(start[0], start[1], start, picture[start[0]][start[1]], m, n, picture);
        }
        return new int[]{start_count, find_max(starts)};
    }
}