Intro
바늘 구멍 같은 취업 시장 속 계속 코딩 테스트를 보다보니 구현하는 문제는 자바로 풀이하기 조금 힘들다는 생각이 들고 있습니다! 최근 기업 코딩 테스트 출제 경향이 주로 구현, BFS/DFS, 시뮬레이션이 강세이고 DP나 이분탐색과 같은 것이 곁들여진다 느껴지는데 이런 상황에서 자바보다 파이썬이 훨씬 구현이 빠르고 쉽다는 생각을 지울 수가 없었습니다.
물론 자바만 가능한 곳이 있으니 참고 사항으로 "파이썬을 활용하면 이런 부분이 편하다~" 정도로 생각해주시면 좋을 것 같네요.
자료구조
알고리즘을 풀다보면 주로 사용하는 자료구조로는 배열, 해시맵, 큐/스택, 인접 리스트 등이 있습니다. 자바와 파이썬이 이런 자료구조를 어떻게 다루는지 차이점을 알아보겠습니다.
Java
Queue<Integer> q = new ArrayDeque<>();
Map<Integer, Integer> cnt = new HashMap<>();
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.putIfAbsent(u, new ArrayList<>());
graph.get(u).add(v);아마 자바로 풀이하시는 분들은 작성에 어려움이 없을 것입니다.
하지만 실제 programmers에서 풀이를 하다보면 작성에 시간이 오래걸리고 그만큼 엣지를 생각할 시간이 줄어들게 됩니다. 특히 각 자료구조의 사용법이 미묘하게 비슷하면서 다르기 때문에 IDE에 익숙하신 분들은 풀이 작성에 더 오랜 시간이 걸리게 됩니다.
Python
from collections import deque, Counter, defaultdict
q = deque()
cnt = Counter(arr)
graph = defaultdict(list) 파이썬의 collections 라이브러리는 구현에 필요한 왠만한 기능이 들어있다 볼 수 있습니다. BFS를 예시로 들면 Queue 생성에 deque()를 호출하면 끝이고 빈도수 계산은 Counter()를 통해 해결할 수 있습니다. 그래프 또한 defaultdict()를 사용하면 쉽게 사용이 가능합니다.
예를 들어 Map의 원소 개수를 세야한다면
Map<Integer, Integer> cnt = new HashMap<>();
for (int n : numbers) {
cnt.put(n, cnt.getOrDefault(n, 0) + 1);
} 자바는 getOrDefault()를 통해 개수를 구하게 되고
cnt = Counter(numbers) 파이썬은 Counter()로 딸깍이 가능합니다.
defaultdict()가 편리한 이유는 없으면 만들어 준다가 기본 동작이기 때문입니다.
if (!graph.containsKey(u)) {
graph.put(u, new ArrayList<>());
}
graph.get(u).add(v);자바에서는 containsKey()를 통해 확인을 거쳐야 하는 반면에
graph = defaultdict(list)
graph[u].append(v)파이썬은 확인 없이 사용이 가능하다는 장점이 있습니다. 기본적으로 python의 dict는 해시맵 기반으로 자바의 HashMap과 동일선상에 있습니다. defaultdict는 HashMap에 putIfAbsent를 내부적으로 구현해준 것으로 키가 없으면 자동 초기화 기능, 그래프/그룹핑/카운팅 최적 등의 장점이 있습니다.
[Java ↔️ Python 자료구조 대응]
HashMap➡️dictordefaltdictTreeMap➡️ 안씀. 정렬이 필요하면sort사용PriorityQueue➡️heapqGraph..?➡️dict+list
정렬
알고리즘 풀이하며 정렬하는 경우가 굉장히 많습니다. 물론 자바도 이 정렬이 어렵지 않지만 가끔 직접 Comparator를 구현해야하는 경우가 있습니다.
- 오름차순으로 정렬하되 값이 같으면 다른 기준으로 정렬
- 우선순위가 높은 것부터 처리 (주로 PQ 문제)
Java
import java.util.*;
// 1. 일반 배열 정렬
Arrays.sort(arr);
// 2. 리스트 정렬
Collections.sort(list);
// 3. 커스텀 정렬 (예: 2차원 배열에서 첫 번째 원소 오름차순, 같으면 두 번째 원소 내림차순)
Arrays.sort(arr, (o1, o2) -> {
if (o1[0] == o2[0]) {
return o2[1] - o1[1];
}
return o1[0] - o2[0];
});자바 8부터 람다시글 지원해서 간결해졌지만, 여전히 조건이 복잡해지면 Comparator 내부 로직을 작성해야하며 부등호 방향을 헷갈리거나 Integer.compare() 등을 활용해야하는 순간이 많이 있습니다.
Python
# 1. 오름차순
arr.sort()
# 2. 내림차순
arr.sort(reverse=True)
# 3. 커스텀 정렬 (lambda 활용)
arr.sort(key=lambda x: (x[0], -x[1]))그에 반해 파이썬은 key 파라미터와 lambda의 조합을 활용합니다. 튜플 형태로 우선순위를 지정할 수 있고 -를 붙임으로써 내림차순 정렬이 가능합니다. 자바에서 if-else로 분기를 두며 작성하던 로직이 파이썬에선 단 한 줄로 정리가 됩니다. 시간 단축이 중요한 코딩 테스트에서 간결한 코드 작성이 가능해집니다.
문자열
가장 큰 분기점인 문자열입니다. 이 글을 작성하게 된 계기와 마찬가지인데 구현 문제에서 은근히 괴로운 것이 문자열 파싱과 조작입니다. 자바는 String이 불변(Immutable) 객체라 수정 시 새로운 객체가 생성되어 성능을 위해 StringBuilder를 사용해야 하고 문법도 꽤나 장황한 편입니다.
Java
String s = "Hello World";
// 문자열 뒤집기
StringBuilder sb = new StringBuilder(s);
String reversed = sb.reverse().toString();
// 문자열 자르기
String sub = s.substring(0, 5);
// 문자열 분리 및 결합
String[] parts = s.split(" ");
String joined = String.join(", ", parts);자바는 문자열을 인덱스로 접근하기 위해 charAt(i)를 사용해야 하고, 부분 문자열을 얻기 위해서는 substring을 사용해야합니다.
Python
s = "Hello World"
# 문자열 뒤집기
reversed_s = s[::-1]
# 문자열 자르기 (슬라이싱)
sub = s[:5]
# 문자열 분리 및 결합
parts = s.split()
joined = ", ".join(parts)파이썬은 슬라이싱([ : : ]) 을 통해 문자열 처리를 쉽게 다룰 수 있습니다.
s[::-1] 하나로 문자열 뒤집기를 할 수 있고 인덱스 접근도 배열처럼 s[i]로 가능해 직관적입니다.
순열과 조합
완전 탐색 혹은 백트래킹 문제를 접하면 순열 (nPr)이나 조합 (nCr)을 구현해야 할 때가 많습니다. 실제로 제가 SSAFY에서 가장 먼저 배운 알고리즘 구현 중 하나가 순조부 였습니다.
Java
자바는 라이브러리 차원에서 순열과 조합을 지원하지 않습니다. 재귀나 스왑, visited (방문 처리), next permutation 등을 활용하여 구현하게 됩니다.
// 조합(Combination) 예시 - 직접 구현 필요
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
if (r == 0) {
// 로직 수행
return;
}
for (int i = start; i < n; i++) {
visited[i] = true;
combination(arr, visited, i + 1, n, r - 1);
visited[i] = false;
}
}가장 간단하게 구현하면 위 코드와 같이 구현이 되게 되는데 매번 문제를 풀 때마다 작성해야하고 문제 조건에 맞게 인덱스 조작을 해야하기 때문에 신경을 많이 써야하는 풀이 중 하나라 생각합니다.
Python
가~~끔 쓰면 안되는 기업이 있긴 하지만 Python은 itertools 라는 라이브러리에서 순열과 조합을 지원합니다.
from itertools import permutations, combinations
arr = [1, 2, 3, 4]
# 순열
for p in permutations(arr, 2):
print(p)
# 조합
for c in combinations(arr, 2):
print(c)itertools를 통해 구현 실수가 없고 속도 또한 C로 최적화되어 있어 무지렁이인 제가 작성한 코드보다는 훨씬 빠르게 동작하게 됩니다.
[문제] 2021 kakao 순위 검색
순위 검색 문제는 효율성 테스트가 포함되어 있어 단순히 find나 contains로 접근하면 시간 초과가 나는 문제입니다.
이 문제를 통해 왜 파이썬을 고려하게 되었는지 설명해보겠습니다.
Java
자바에서는 지원자의 정보 (언어, 직군, 경력, 소울푸드)에 대해 - 조건을 포함한 모든 조합을 만들기 위해 재귀 함수(DFS)나 4중 for문을 활용해 구현해야 합니다.
[재귀 함수]
static void makeSentence(String[] p, String str, int cnt) {
if (cnt == 4) {
if (!map.containsKey(str)) {
List<Integer> list = new ArrayList<Integer>();
map.put(str, list);
}
map.get(str).add(Integer.parseInt(p[4]));
return;
}
// 해당 조건을 포함하는 경우
makeSentence(p, str + p[cnt], cnt + 1);
// 해당 조건을 '-'로 처리하는 경우
makeSentence(p, str + "-", cnt + 1);
}[4중 for문]
for (String la : langs) {
for (String jo : jobs) {
for (String ca : careers) {
for (String fo : foods) {
String key = la + jo + ca + fo;
map.computeIfAbsent(key, k -> new ArrayList<>()).add(score);
}
}
}
}또한 저장된 점수 리스트에서 특정 점수 이상인 사람의 수를 세기 위해 Collections.binarySearch를 사용하거나 직접 lowerBound를 구현해야 했스빈다. 자바의 binarySearch는 값이 없으면 음수를 반환하기 때문에 'X점 이상인 사람의 수'를 구하려면 인덱스 보정 로직을 추가로 작성해야 합니다.
[lowerBound 구현]
private int bs(List<Integer> list, int target) {
int l = 0;
int r = list.size();
while (l < r) {
int mid = (l + r) / 2;
if (list.get(mid) < target) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}그래서 전체 코드 작성을 보면 심상치 않습니다. 물론 제가 하드 코딩해서 더 더러운 것도 있습니다.
import java.util.*;
class Solution {
static Map<String, List<Integer>> map = new HashMap<>();
public int[] solution(String[] info, String[] query) {
for (String s : info) {
String[] ss = s.split(" ");
String lang = ss[0];
String job = ss[1];
String career = ss[2];
String food = ss[3];
int score = Integer.parseInt(ss[4]);
String[] langs = {lang, "-"};
String[] jobs = {job, "-"};
String[] careers = {career, "-"};
String[] foods = {food, "-"};
for (String la : langs) {
for (String jo : jobs) {
for (String ca : careers) {
for (String fo : foods) {
String key = la + jo + ca + fo;
map.computeIfAbsent(key, k -> new ArrayList<>()).add(score);
}
}
}
}
}
for (List<Integer> list : map.values()) Collections.sort(list);
int[] answer = new int[query.length];
for (int i = 0; i < query.length; i++) {
String q = query[i];
String replaced = q.replace(" and ", " ");
String[] arr = replaced.split(" ");
String key = arr[0] + arr[1] + arr[2] + arr[3];
int score = Integer.parseInt(arr[4]);
List<Integer> list = map.getOrDefault(key, Collections.emptyList());
int idx = bs(list, score);
answer[i] = list.size() - idx;
}
return answer;
}
private int bs(List<Integer> list, int target) {
int l = 0;
int r = list.size();
while (l < r) {
int mid = (l + r) / 2;
if (list.get(mid) < target) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
}Python
파이썬은 이 문제에서 압도적인 퍼포먼스를 보여줍니다.
itertools.combinations: 재귀 함수 없이 모든 조합 생성bisect.bisect_left: 직접 구현 없이 이분 탐색 수행
from itertools import combinations
from collections import defaultdict
from bisect import bisect_left
def solution(info, query):
answer = []
info_dict = defaultdict(list)
# 1. 모든 경우의 수 생성
for i in info:
temp = i.split()
conditions = temp[:-1]
score = int(temp[-1])
# 4개의 조건 중 0~4개를 선택하여 '-'가 들어갈 조합 생성 (Java의 4중 for문을 combinations로 대체)
for k in range(5):
for comb in combinations(range(4), k):
key_temp = conditions[:]
for idx in comb:
key_temp[idx] = "-" # 선택된 인덱스를 '-'로 변경
key = "".join(key_temp)
info_dict[key].append(score)
# 2. 이분 탐색을 위한 정렬
for key in info_dict:
info_dict[key].sort()
# 3. 쿼리 처리
for q in query:
q = q.replace("and ", "").split()
target_key = "".join(q[:-1])
target_score = int(q[-1])
# Lower Bound를 통해 개수 구하기
count = len(info_dict[target_key]) - bisect_left(info_dict[target_key], target_score)
answer.append(count)
return answer어 아름답다. 아름다와. 구현 코드 거의 없이 라이브러리로 딸깍 해버릴 수 있습니다.
Outro
지금까지 자바와 파이썬의 알고리즘 풀이 스타일을 비교해 보았습니다. 물론 자바에 대한 분노로 작성한 글이라 파이썬 편향적인 글이지만 파이썬이 실제로 더 간결하게 작성이 가능하다는 점에서 고려해볼만 하다 생각합니다.
자바 원툴로 살기 이전엔 파이썬을 좋아했던 사람으로써 자바 공화국인 대한민국에서 코딩 테스트에 자바만 지원한다 => 자바
파이썬과 자바를 동시 지원한다 => 파이썬
이런 식으로 활용하려 합니다. 파이썬은 짱이니까.
