코딩 테스트/Level 2
2017 카카오코드 예선카카오프렌즈 컬러링북
컴닥
2022. 8. 21. 09:53
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/1829
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
파이썬
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)};
}
}
반응형