Java 코딩테스트 치트시트

Об этом предложении

평소 Python으로 문제를 풀다가 Java로 코딩테스트를 봐야 할 때, 손에서 바로 나와야 하는 것들만 모았다. 알고리즘 이론보다 "Java로 생각을 코드로 옮기는 속도"에 초점을 맞췄다. (Java 17 기준) 1. 기본 템플릿과 입출력 오프라인 IDE 테스트는 채점기가 없으므로 main 에서 직접 함수를 호출해 결과를 출력하는 형태가 기본이다. 입력이 주어지는 경우엔 BufferedReader 가 안전하다. import java.util.*; import java.io.*; import java.util.stream.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] arr = Arrays.stream(br.readLine().split(" ")) .mapToInt(Integer::parseInt).toArray(); StringBuilder sb = new StringBuilder(); for (int x : arr) sb.append(x).append('\n'); System.out.print(sb); } } 상황 쓰는 것 비고 입력 적음, 빨리 짜기 Scanner sc = new Scanner(System.in); sc.nextInt() , sc.next() , sc.nextLine() nextInt() 뒤 nextLine() 은 개행 하나 먹으니 한 번 더 호출 입력 10만 줄 이상 BufferedReader + StringTokenizer readLine() 은 String 반환, 파싱 필요 출력 많음 StringBuilder 에 모아 마지막에 한 번 출력 System.out.println 반복은 느림 한 줄 정수 여러 개 Arrays.stream(line.split(" ")).mapToInt(Integer::parseInt).toArray() 문자열 → 숫자 Integer.parseInt(s) , Long.parseLong(s) , Double.parseDouble(s) 숫자 → 문자열 String.valueOf(n) , Integer.toString(n) , "" + n 진법 변환 Integer.toBinaryString(n) , Integer.toString(n, 2) , Integer.parseInt("1011", 2) 포맷 출력 String.format("%.2f", d) , System.out.printf("%d %s%n", a, b) 과제형(플레이리스트 만들기 등)이면 입력 파싱 대신 main 에 테스트 데이터를 직접 만들어 호출하고, 결과를 println 으로 보여주면 된다. 클래스 여러 개는 한 파일에 class Song {} 처럼 public 없이 두면 된다. 2. String / StringBuilder / char String은 불변이라 반복 += 는 O(n2)다. 문자열을 만들거나 바꿀 땐 무조건 StringBuilder . 할 일 코드 길이 s.length() (배열은 arr.length , 리스트는 list.size() ) i번째 문자 s.charAt(i) → char 부분 문자열 s.substring(from, to) (to 미포함), s.substring(from) 문자 배열로 s.toCharArray() / 다시 문자열로 new String(chars) 분리 s.split(" ") , s.split(",") — 정규식이라 \\. , `\ 합치기 String.join(",", list) , String.join(" ", arr) 포함·위치 s.contains("ab") , s.indexOf("ab") (없으면 -1), s.startsWith , s.endsWith 바꾸기 s.replace("a", "b") (전부), s.replaceAll("[0-9]", "") (정규식) 대소문자 s.toUpperCase() , s.toLowerCase() 공백 제거 s.trim() , s.strip() 비교 s.equals(t) (절대 == 금지), s.equalsIgnoreCase(t) , s.compareTo(t) (사전순, 음수/0/양수) 비었는지 s.isEmpty() , s.isBlank() 반복 "ab".repeat(3) 문자 판별 Character.isDigit(c) , isLetter(c) , isUpperCase(c) , isAlphabetic(c) 문자 ↔ 숫자 c - '0' (숫자 문자→int), (char)(n + '0') , c - 'a' (알파벳 인덱스) 문자 변환 Character.toUpperCase(c) , Character.toLowerCase(c) StringBuilder sb = new StringBuilder(); sb.append("abc").append(1).append('x'); sb.insert(0, "z"); // 앞에 삽입 sb.deleteCharAt(sb.length() - 1); sb.setCharAt(0, 'q'); sb.reverse(); // 뒤집기 — 팰린드롬 판별에 바로 쓰임 sb.setLength(0); // 비우기 String result = sb.toString(); 문자열 뒤집기는 new StringBuilder(s).reverse().toString() . 문자 정렬은 char[] c = s.toCharArray(); Arrays.sort(c); new String(c) . 아스키 연산은 char 가 정수로 자동 승격되니 (char)(c + 1) 처럼 캐스팅 필요. 3. 배열과 Arrays 유틸 크기가 고정이면 배열, 늘어나면 ArrayList . int[] 와 Integer[] 는 다른 타입이라 Comparator 정렬은 Integer[] 에만 된다. int[] a = new int[n]; // 0으로 초기화 int[] b = {3, 1, 2}; int[][] grid = new int[r][c]; boolean[][] visited = new boolean[r][c]; Arrays.fill(a, -1); // 전체 채우기 for (int[] row : grid) Arrays.fill(row, Integer.MAX_VALUE); // 2차원은 행별로 Arrays.sort(a); // 오름차순 (기본형은 역순 직접 불가) Integer[] boxed = {3, 1, 2}; Arrays.sort(boxed, Collections.reverseOrder()); Arrays.sort(a, from, to); // 구간 정렬 int[] copy = Arrays.copyOf(a, a.length); int[] part = Arrays.copyOfRange(a, 1, 4); // [1,4) int[] c2 = a.clone(); Arrays.toString(a); // 디버그 출력 "[1, 2, 3]" Arrays.deepToString(grid); // 2차원 Arrays.equals(a, b); Arrays.stream(a).sum(); .max().getAsInt(); .min().getAsInt(); Arrays.asList(boxed); // 고정 크기 List (add 불가) List<Integer> list = new ArrayList<>(Arrays.asList(boxed)); // 수정 가능 List<Integer> li = Arrays.stream(a).boxed().collect(Collectors.toList()); // int[] → List int[] back = li.stream().mapToInt(Integer::intValue).toArray(); // List → int[] int idx = Arrays.binarySearch(a, key); // 정렬된 배열만, 없으면 음수 2차원 배열 정렬은 Arrays.sort(arr, (x, y) -> x[0] - y[0]) (int[][] 은 객체 배열이라 가능). 방향 배열은 int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; 로 두고 범위 검사 if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue; 를 반드시 먼저. 4. 컬렉션 핵심 과제형 문제의 8할은 ArrayList + HashMap 으로 끝난다. 선언은 인터페이스 타입으로, 제네릭은 래퍼 타입( Integer , Long , Character )만 가능. List List<Integer> list = new ArrayList<>(); list.add(x); list.add(0, x); list.get(i); list.set(i, x); list.remove(i); // 인덱스로 삭제 list.remove(Integer.valueOf(x)); // 값으로 삭제 (int면 인덱스로 오해함) list.size(); list.isEmpty(); list.contains(x); list.indexOf(x); Collections.sort(list); list.sort(null); list.sort(Comparator.reverseOrder()); Collections.reverse(list); Collections.max(list); Collections.min(list); Collections.swap(list, i, j); list.subList(from, to); // 뷰(복사 아님) new ArrayList<>(list); // 복사 List.of(1, 2, 3); // 불변 Map Map<String, Integer> map = new HashMap<>(); map.put(k, v); map.get(k); // 없으면 null → int에 넣으면 NPE map.getOrDefault(k, 0); map.put(k, map.getOrDefault(k, 0) + 1); // 카운팅 기본 map.merge(k, 1, Integer::sum); // 카운팅 한 줄 map.computeIfAbsent(k, x -> new ArrayList<>()).add(v); // 그룹핑 한 줄 map.containsKey(k); map.containsValue(v); map.remove(k); map.size(); for (Map.Entry<String, Integer> e : map.entrySet()) { e.getKey(); e.getValue(); } for (String k : map.keySet()) {} for (int v : map.values()) {} TreeMap<Integer, String> tm = new TreeMap<>(); // 키 정렬 유지 tm.firstKey(); tm.lastKey(); tm.floorKey(x); tm.ceilingKey(x); tm.headMap(x); tm.tailMap(x); LinkedHashMap<> // 삽입 순서 유지 Set Set<Integer> set = new HashSet<>(); set.add(x); set.contains(x); set.remove(x); set.size(); new HashSet<>(list).size(); // 중복 제거 개수 TreeSet<Integer> ts = new TreeSet<>(); // 정렬 유지 ts.first(); ts.last(); ts.floor(x); ts.ceiling(x); ts.pollFirst(); Deque (스택·큐 둘 다) Deque<Integer> dq = new ArrayDeque<>(); // 큐: offer / poll / peek (뒤에 넣고 앞에서 뺀다) // 스택: push / pop / peek (앞에 넣고 앞에서 뺀다) dq.offerFirst(x); dq.offerLast(x); dq.pollFirst(); dq.pollLast(); dq.peekFirst(); dq.peekLast(); dq.isEmpty(); // Stack 클래스는 느리고 권장 안 함. ArrayDeque는 null 불가. PriorityQueue PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소 힙 PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder()); PriorityQueue<int[]> pq2 = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 배열 우선순위 pq.offer(x); pq.poll(); pq.peek(); pq.size(); pq.isEmpty(); 자료구조 언제 주요 연산 비용 ArrayList 순서 있는 목록, 인덱스 접근 get O(1), 중간 삽입/삭제 O(n) HashMap / HashSet 카운팅, 중복 체크, 키→값 조회 O(1) TreeMap / TreeSet 정렬 상태 유지, 범위 검색 O(log n) LinkedHashMap 삽입 순서 유지하는 Map (LRU 등) O(1) ArrayDeque 큐, 스택, BFS O(1) PriorityQueue 항상 최소/최대 꺼내기, 다익스트라 O(log n) 5. 정렬과 Comparator 람다 (a, b) -> a - b 는 오름차순, b - a 는 내림차순. 값이 클 수 있으면 뺄셈 대신 Integer.compare(a, b) 를 써야 오버플로우를 피한다. // 기본 Collections.sort(list); list.sort(Comparator.reverseOrder()); Arrays.sort(arr2d, (a, b) -> a[0] - b[0]); // 다중 조건: 점수 내림차순, 같으면 이름 오름차순 list.sort((a, b) -> { if (a.score != b.score) return Integer.compare(b.score, a.score); return a.name.compareTo(b.name); }); // 같은 것을 Comparator 체이닝으로 (면접에서 더 좋아 보임) list.sort(Comparator.comparingInt((Song s) -> s.score).reversed() .thenComparing(s -> s.name)); // 문자열 길이 순, 같으면 사전순 words.sort(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder())); // Map을 값 기준으로 정렬해 상위 N개 List<Map.Entry<String, Integer>> entries = new ArrayList<>(map.entrySet()); entries.sort((a, b) -> b.getValue() - a.getValue()); 객체가 기본 정렬 기준을 가지게 하려면 Comparable 구현: class Song implements Comparable<Song> { String title; int plays; Song(String title, int plays) { this.title = title; this.plays = plays; } @Override public int compareTo(Song o) { return Integer.compare(o.plays, this.plays); } // 재생수 내림차순 @Override public String toString() { return title + "(" + plays + ")"; } } Collections.sort 와 Arrays.sort(객체) 는 안정 정렬(TimSort)이라 같은 키는 원래 순서 유지. Arrays.sort(int[]) 는 듀얼 피벗 퀵소트로 최악 O(n2)가 있으나 실무 테스트에선 신경 안 써도 됨. 6. Stream 핵심 패턴 과제형에서 "필터링해서 정렬해서 상위 N개" 같은 요구는 Stream 한 줄이 가장 읽기 좋다. 다만 성능 질문이 나오면 "반복문과 동일한 O(n), 가독성 때문에 썼다"고 답하면 된다. import java.util.stream.*; // 필터 + 변환 + 수집 List<String> titles = songs.stream() .filter(s -> s.plays > 100) .map(s -> s.title) .collect(Collectors.toList()); // Java 16+ 면 .toList() // 정렬 + 상위 N List<Song> top3 = songs.stream() .sorted(Comparator.comparingInt((Song s) -> s.plays).reversed()) .limit(3) .collect(Collectors.toList()); // 그룹핑: 아티스트별 곡 목록 / 개수 / 합계 Map<String, List<Song>> byArtist = songs.stream().collect(Collectors.groupingBy(s -> s.artist)); Map<String, Long> countByArtist = songs.stream().collect(Collectors.groupingBy(s -> s.artist, Collectors.counting())); Map<String, Integer> playsByArtist = songs.stream().collect(Collectors.groupingBy(s -> s.artist, Collectors.summingInt(s -> s.plays))); // 집계 int total = songs.stream().mapToInt(s -> s.plays).sum(); Optional<Song> best = songs.stream().max(Comparator.comparingInt(s -> s.plays)); double avg = songs.stream().mapToInt(s -> s.plays).average().orElse(0); boolean any = songs.stream().anyMatch(s -> s.plays == 0); // allMatch, noneMatch long cnt = songs.stream().filter(s -> s.plays > 0).count(); // 중복 제거, 문자열 합치기 List<String> artists = songs.stream().map(s -> s.artist).distinct().collect(Collectors.toList()); String joined = titles.stream().collect(Collectors.joining(", ")); // 범위 반복, 문자열 문자 순회 IntStream.range(0, n).forEach(i -> ...); // 0..n-1 IntStream.rangeClosed(1, n).sum(); s.chars().filter(Character::isDigit).count(); // List → Map (키 중복 시 터짐, 세 번째 인자로 병합 규칙) Map<String, Song> byTitle = songs.stream().collect(Collectors.toMap(s -> s.title, s -> s, (a, b) -> a)); Optional 은 .orElse(기본값) , .orElseThrow() , .isPresent() , .get() 로 꺼낸다. Collectors.toList() 로 만든 리스트는 수정 가능, .toList() (Java 16+)는 불변이라 add 하면 예외. 7. 자주 나오는 알고리즘 패턴 1시간 오프라인 테스트에서 실제로 나오는 건 이 여섯 개가 거의 전부다. 각각 손에서 바로 나와야 한다. 완전탐색 (순열·조합·부분집합) // 조합: n개 중 r개 고르기 static void comb(int[] arr, int start, int r, List<Integer> cur, List<List<Integer>> out) { if (cur.size() == r) { out.add(new A