문자열검사
방법
1. Character 클래스 사용
2. Stream API 사용
3. 정규표현식 사용
문자열에 숫자가 있는지 검사
Character 클래스 사용
public static boolean hasDigit(String str) {
for (char c : str.toCharArray()) {
if (Character.isDigit(c)) {
return true;
}
}
return false;
}
Stream API를 사용
public static boolean hasDigit(String str) {
return str.chars().anyMatch(Character::isDigit);
}
정규표현식 사용
public static boolean hasDigit(String str) {
return str.matches(".*\\d.*");
}
문자열에 소문자가 있는지 검사
Character 클래스 사용
public static boolean hasLowerCase(String str) {
for (char c : str.toCharArray()) {
if (Character.isLowerCase(c)) {
return true;
}
}
return false;
}
Stream API를 사용
public static boolean hasLowerCase(String str) {
return str.chars().anyMatch(Character::isLowerCase);
}
정규 표현식 사용
public static boolean hasLowerCase(String str) {
return str.matches(".*[a-z].*");
}
문자열에 대문자가 있는지 검사
Character 클래스 사용
public static boolean hasUpperCase(String str) {
for (char c : str.toCharArray()) {
if (Character.isUpperCase(c)) {
return true;
}
}
return false;
}
Stream API를 사용
public static boolean hasUpperCase(String str) {
return str.chars().anyMatch(Character::isUpperCase);
}
정규표현식 사용
public static boolean hasUpperCase(String str) {
return str.matches(".*[A-Z].*");
}
정규표현식
정규표현식(Regular Expression, Regex)은 문자열 패턴을 표현하는 형식 언어입니다.
주요 용도
- 문자열 검색 및 매칭
- 문자열 치환
- 입력값 유효성 검증 (이메일, 전화번호 등)
- 로그 파싱
- 데이터 추출
2. 기본 문법
리터럴 매칭
"hello".matches("hello") // true - 정확히 일치
"hello".matches("Hello") // false - 대소문자 구분
"hello world".matches("hello") // false - 전체 문자열 매칭 필요
와일드카드 (.)
- 모든 문자 하나와 매칭 (개행 문자 제외)
"cat".matches("c.t") // true
"cot".matches("c.t") // true
"c9t".matches("c.t") // true
"ct".matches("c.t") // false - 문자가 하나 필요
"cart".matches("c.t") // false - 전체 매칭 안됨
3. 메타 문자 상세
메타 문자는 특별한 의미를 가진 문자들입니다.
전체 메타 문자 목록
^ $ . * + ? { } [ ] \ | ( )
^ (문자열 시작)
"hello".matches("^h.*") // true
"world".matches("^h.*") // false
$ (문자열 끝)
"hello".matches(".*o$") // true
"hello".matches(".*e$") // false
. (임의의 문자 하나)
"a1b".matches("a.b") // true
"a b".matches("a.b") // true
"ab".matches("a.b") // false
* (0회 이상 반복)
"".matches("a*") // true - 0개도 가능
"a".matches("a*") // true
"aaaa".matches("a*") // true
"b".matches("a*") // false
+ (1회 이상 반복)
"".matches("a+") // false - 최소 1개 필요
"a".matches("a+") // true
"aaaa".matches("a+") // true
? (0회 또는 1회 (있거나 없거나))
"color".matches("colou?r") // true
"colour".matches("colou?r") // true
"colouur".matches("colou?r") // false
| (OR 연산자)
"cat".matches("cat|dog") // true
"dog".matches("cat|dog") // true
"bird".matches("cat|dog") // false
() (그룹화)
"gray".matches("gr(a|e)y") // true
"grey".matches("gr(a|e)y") // true
4. 문자 클래스
기본 문자 클래스 [...]
- 대괄호 안의 문자 중 하나와 매칭
"a".matches("[abc]") // true
"b".matches("[abc]") // true
"d".matches("[abc]") // false
범위 지정 [a-z]
"m".matches("[a-z]") // true - 소문자
"M".matches("[a-z]") // false
"5".matches("[0-9]") // true - 숫자
"a".matches("[a-zA-Z]") // true - 영문자
부정 문자 클래스 [^...]
- 대괄호 안의 문자를 제외한 모든 문자
"a".matches("[^0-9]") // true - 숫자가 아님
"5".matches("[^0-9]") // false
여러문자를 확인하고싶다면 메타문자를 이용한다.
"aa".matches("[a-z]") // false
"aa".matches("[a-z]+") // true
"aa".matches("[a-z]*") // true
"aa".matches("(aa)") // true
미리 정의된 문자 클래스
/w,/W에 _라는 문자가 포함되어있는걸 주의한다.
"5".matches("\\d") // true
"a".matches("\\d") // false
"_".matches("\\w") // true
" ".matches("\\s") // true
주의: Java 문자열에서는 \를 \\로 이스케이프해야 합니다!
5. 수량자
정확한 횟수 {n}
"aaa".matches("a{3}") // true
"aa".matches("a{3}") // false
"aaaa".matches("a{3}") // false
범위 지정 {n,m}
"aa".matches("a{2,4}") // true
"aaa".matches("a{2,4}") // true
"aaaa".matches("a{2,4}") // true
"a".matches("a{2,4}") // false
"aaaaa".matches("a{2,4}") // false
최소 횟수 {n,}
"aa".matches("a{2,}") // true
"aaaa".matches("a{2,}") // true
"a".matches("a{2,}") // false
특수 문자 이스케이프
메타 문자를 일반 문자로 사용하기
모든 메타 문자를 문자 그대로 매칭하려면 \를 앞에 붙입니다.
// 점(.)을 문자 그대로
"3.14".matches("3\\.14") // true
"3x14".matches("3\\.14") // false
// 별표(*)를 문자 그대로
"a*b".matches("a\\*b") // true
"aaab".matches("a\\*b") // false
// 대괄호를 문자 그대로
"[a]".matches("\\[a\\]") // true
// 백슬래시 자체를 매칭
"a\\b".matches("a\\\\b") // true
// 달러 기호
"$100".matches("\\$\\d+") // true
// 괄호
"(test)".matches("\\(test\\)") // true
Java에서 이중 백슬래시가 필요한 이유
// Java 문자열에서:
"\\" → 실제 문자: \ (백슬래시 1개)
"\\d" → 실제 문자: \d (정규표현식 엔진으로 전달)
"\\\\d" → 실제 문자: \\d (백슬래시 + d 문자)
// 예제
"5".matches("\\d") // \d (숫자 패턴)
"\\d".matches("\\\\d") // \\d (백슬래시+d 문자 그대로)
문자 클래스 내부에서는 대부분 이스케이프 불필요
// 범위 vs 리터럴 하이픈 비교
"a-b".matches("[a-b]") // false (범위: a, b 중 1글자만)
"a-b".matches("[a\\-b]") // false (문자: a, -, b 중 1글자만)
"a-b".matches("[a\\-b]+") // true ✅ (a, -, b가 1개 이상)
"-".matches("[a-b]") // false (하이픈은 a~b 범위에 없음)
"-".matches("[a\\-b]") // true ✅ (리터럴 하이픈)
"-".matches("[-]") // true ✅ (첫 위치라 리터럴)
// ^ 문자의 위치별 의미
"^".matches("[^a]") // true ✅ (부정: a가 아닌 것)
"^".matches("[\\^]") // true ✅ (리터럴 ^ 문자)
"^".matches("[a^]") // true ✅ (첫 위치 아니면 리터럴)
// 부정 문자 클래스 예제
"a".matches("[^a]") // false (a 제외)
"b".matches("[^a]") // true (a 아님)
"x".matches("[^abc]") // true (a,b,c 모두 아님)
"b".matches("[^abc]") // false (b는 제외됨)
Java에서 정규표현식 사용
방법 1: String.matches() -> 코테에서 사용
- 전체 문자열이 패턴과 일치하는지 확인
String text = "hello123";
boolean result = text.matches("[a-z]+\\d+"); // true방법 2: Pattern & Matcher (권장) -> 개발에서 사용
- 더 유연하고 성능이 좋음
String text = "Email: test@example.com, Phone: 010-1234-5678";
Pattern pattern = Pattern.compile("\\w+@\\w+\\.\\w+");
Matcher matcher = pattern.matcher(text);
// 찾기
if (matcher.find()) {
System.out.println("Found: " + matcher.group()); // test@example.com
}
// 모두 찾기
while (matcher.find()) {
System.out.println(matcher.group());
}
많이쓰이는 패턴 예시
문자열 검증 패턴
public class ValidationPatterns {
// 숫자 포함 여부
public static boolean hasDigit(String str) {
return str.matches(".*\\d.*");
// "abc123" → true, "abc" → false
// str.matches(".*[0-9].*") 와 동일하다.
// 어떤 문자든 앞뒤에 있어도 되고 없어도 되는 상태에서 숫자가 최소 하나라도 있다면 true
}
// 영문자 포함 여부
public static boolean hasLetter(String str) {
return str.matches(".*[a-zA-Z].*");
// "123abc" → true, "123" → false
// .* → 앞에 아무 문자나 0개 이상
// [a-zA-Z] → 영문자(대소문자) 1개
// .* → 뒤에 아무 문자나 0개 이상
// 문자열 어디든 영문자가 최소 하나라도 포함되면 true
}
// 특수문자 포함 여부
public static boolean hasSpecialChar(String str) {
return str.matches(".*[^a-zA-Z0-9].*");
// "hello!" → true, "hello" → false
// [^a-zA-Z0-9] → 영문자도 숫자도 아닌 문자 1개 (즉, 특수문자)
// [^...] 는 "...이 아닌 것"을 의미
// 문자열 어디든 특수문자(공백, 기호 등)가 최소 하나라도 포함되면 true
}
// 숫자로만 구성
public static boolean onlyDigits(String str) {
return str.matches("\\d+");
// "12345" → true, "123a" → false
// str.matches("[0-9]+") 와 동일하다.
// \\d+ → 숫자가 1개 이상 연속으로
// +가 없으면 \\d는 숫자 정확히 1개만 매칭 → "1"만 true, "123"은 false
// 전체 문자열이 숫자로만 이루어져 있으면 true
}
// 영문자로만 구성
public static boolean onlyLetters(String str) {
return str.matches("[a-zA-Z]+");
// "Hello" → true, "Hello123" → false
// [a-zA-Z]+ → 영문자(대소문자)가 1개 이상 연속으로
// +가 없으면 [a-zA-Z]는 영문자 정확히 1개만 매칭 → "a"만 true, "abc"는 false
// 전체 문자열이 영문자로만 이루어져 있으면 true (숫자, 공백, 특수문자 포함 시 false)
}
// 영문자+숫자로만 구성
public static boolean alphanumeric(String str) {
return str.matches("[a-zA-Z0-9]+");
// "abc123" → true, "abc_123" → false
// str.matches("\\w+")는 다르다! (\\w는 밑줄(_)도 포함)
// [a-zA-Z0-9]+ → 영문자 또는 숫자가 1개 이상 연속으로
// 전체 문자열이 영문자와 숫자의 조합으로만 이루어져 있으면 true
// 공백, 특수문자(_포함), 한글 등이 포함되면 false
}
}
문자열 치환/제거 패턴
public class ReplacePatterns {
// 모든 숫자 제거
public static String removeDigits(String str) {
return str.replaceAll("\\d", "");
// "abc123def456" → "abcdef"
// \\d → 숫자 1개를 찾아서 빈 문자열로 교체
// replaceAll이므로 모든 숫자를 각각 찾아서 전부 제거
// str.replaceAll("[0-9]", "") 와 동일
}
// 모든 공백 제거
public static String removeSpaces(String str) {
return str.replaceAll("\\s", "");
// "hello world" → "helloworld"
// \\s → 공백 문자 1개 (스페이스, 탭, 줄바꿈 등)
// 연속된 공백이든 단일 공백이든 모두 각각 찾아서 제거
// "a b" (공백 2개) → 공백 2개를 각각 제거 → "ab"
}
// 여러 공백을 하나로
public static String normalizeSpaces(String str) {
return str.replaceAll("\\s+", " ");
// "hello world" → "hello world"
// \\s+ → 연속된 공백 1개 이상을 하나의 덩어리로 매칭
// +가 없으면: 공백 하나씩 각각 처리 → 의미 없음 (그냥 공백을 공백으로 교체)
// +가 있으면: 연속된 공백 덩어리를 찾아서 → 공백 1개로 교체
// "a b" (공백 4개) → 공백 4개 덩어리를 찾아서 공백 1개로 → "a b"
}
// 영문자가 아닌 모든 것 제거
public static String keepOnlyLetters(String str) {
return str.replaceAll("[^a-zA-Z]", "");
// "Hello, World! 123" → "HelloWorld"
// [^a-zA-Z] → 영문자가 아닌 모든 문자 1개 (숫자, 공백, 특수문자 등)
// [^...] → "...이 아닌 것"을 의미
// 영문자를 제외한 나머지를 모두 찾아서 제거 → 영문자만 남음
}
// 숫자가 아닌 모든 것 제거
public static String keepOnlyDigits(String str) {
return str.replaceAll("[^0-9]", "");
// "abc-123-def-456" → "123456"
// [^0-9] → 숫자가 아닌 모든 문자 1개 (영문자, 공백, 특수문자 등)
// 숫자를 제외한 나머지를 모두 제거 → 숫자만 남음
}
// 숫자가 아닌 모든 것 제거 (간단 버전)
public static String keepOnlyDigits2(String str) {
return str.replaceAll("\\D", "");
// "abc-123-def-456" → "123456"
// \\D → 숫자가 아닌 문자 (Digit가 아닌 것)
// [^0-9]와 완전히 동일한 의미, 더 짧고 간결함
}
// 특수문자 제거 (영문자, 숫자, 공백만 남김)
public static String removeSpecialChars(String str) {
return str.replaceAll("[^a-zA-Z0-9\\s]", "");
// "Hello@World#123!" → "HelloWorld123"
// [^a-zA-Z0-9\\s] → 영문자도, 숫자도, 공백도 아닌 문자 (즉, 특수문자)
// \\s를 넣어서 공백은 유지됨
// "Hello@World #123!" → "HelloWorld 123" (공백 포함 시)
// 특수문자만 골라서 제거 → 영문자, 숫자, 공백만 남음
}
}
문자열 분리 패턴
public class SplitPatterns {
// 공백으로 분리 (여러 공백도 처리)
public static String[] splitBySpaces(String str) {
return str.split("\\s+");
// "hello world test" → ["hello", "world", "test"]
// \\s+ → 연속된 공백 1개 이상을 구분자로 사용
// +가 없으면: 공백 1개씩만 구분 → "a b"는 ["a", "", "b"] (빈 문자열 생김)
// +가 있으면: 연속된 공백을 하나의 구분자로 인식 → 빈 문자열 안 생김
// 공백이 1개든 10개든 상관없이 단어만 깔끔하게 분리됨
}
// 쉼표나 공백으로 분리
public static String[] splitByCommaOrSpace(String str) {
return str.split("[,\\s]+");
// "a,b, c d" → ["a", "b", "c", "d"]
// [,\\s] → 쉼표 또는 공백 중 하나
// [,\\s]+ → 쉼표와 공백이 섞여서 1개 이상 연속된 것을 구분자로 사용
// "a, , b" (쉼표+공백 혼합) → 전체를 하나의 구분자로 인식
// 쉼표 앞뒤 공백이나 연속 쉼표 상관없이 깔끔하게 분리
}
// 숫자로 분리
public static String[] splitByDigits(String str) {
return str.split("\\d+");
// "abc123def456ghi" → ["abc", "def", "ghi"]
// \\d+ → 연속된 숫자 1개 이상을 구분자로 사용
// 숫자 부분을 전부 제거하고 문자 부분만 분리해서 배열로 반환
// "abc1def" → ["abc", "def"]
// "abc123def" → ["abc", "def"] (숫자 개수 상관없음)
// +가 없으면: 숫자 1개씩만 구분 → "a12b"는 ["a", "", "b"]
}
// 영문자로 분리
public static String[] splitByLetters(String str) {
return str.split("[a-zA-Z]+");
// "123abc456def789" → ["123", "456", "789"]
// [a-zA-Z]+ → 연속된 영문자 1개 이상을 구분자로 사용
// 영문자 부분을 전부 제거하고 숫자 부분만 분리해서 배열로 반환
// 대소문자 구분 없이 모든 영문자를 구분자로 인식
// "123a456ABC789" → ["123", "456", "789"]
}
// 특수문자로 분리
public static String[] splitBySpecialChars(String str) {
return str.split("[^a-zA-Z0-9]+");
// "hello@world#test" → ["hello", "world", "test"]
// [^a-zA-Z0-9] → 영문자도 숫자도 아닌 문자 (즉, 특수문자와 공백)
// [^a-zA-Z0-9]+ → 연속된 특수문자/공백 1개 이상을 구분자로 사용
// 특수문자를 전부 제거하고 영문자+숫자 덩어리만 분리
// "hello@@world" → ["hello", "world"] (특수문자 개수 상관없음)
// "abc_123-def" → ["abc", "123", "def"] (밑줄, 하이픈도 특수문자로 처리)
}
}
주요 포인트:
- replaceAll: 패턴과 매칭되는 부분을 교체 (제거하려면 빈 문자열로)
- split: 패턴과 매칭되는 부분을 구분자로 사용해서 문자열 분리
- +의 중요성: 연속된 것을 하나로 처리하여 빈 문자열이나 중복 제거 방지
- [^...]: 부정 문자 클래스로 "~이 아닌 것" 표현 가능
복습문제
https://school.programmers.co.kr/learn/courses/30/lessons/72410
우선순위큐 ( PriorityQueue )
1. 기본 개념
- Min Heap: 기본 설정, 작은 값이 먼저 나옴
- 내부 구조: 완전 이진 트리 기반 힙
- 용도: K번째 값, 최대/최소 추적, 다익스트라, Top K 문제
시간복잡도
Min Heap (기본)
PriorityQueue pq = new PriorityQueue<Integer>();
Max Heap
PriorityQueue pq = new PriorityQueue<Integer>(Comparator.reverseOrder());
// 또는
PriorityQueue pq = new PriorityQueue<Integer>((o1, o2) -> o2 - o1);
커스텀 정렬
// 배열 첫 번째 요소 기준
PriorityQueue pq = new PriorityQueue<int[]>((o1, o2) -> o1[0] - o2[0]);
// 복합 조건
PriorityQueue pq = new PriorityQueue<int[]>((o1, o2) -> {
if (o1[0] != o2[0]) return o1[0] - o2[0]; // 첫 번째 오름차순
return o2[1] - o1[1]; // 두 번째 내림차순
});
// 절댓값 기준 (같으면 실제 값)
PriorityQueue pq = new PriorityQueue<Integer>((o1, o2) -> {
int abs = Integer.compare(Math.abs(o1), Math.abs(o2));
return abs != 0 ? abs : Integer.compare(o1, o2);
});
// ⚠️ Overflow 방지: (a, b) -> a - b 대신 Integer.compare(a, b) 사용!
주요 메서드
PriorityQueue<> pq = new PriorityQueue<Integer>();
// 삽입
pq.offer(5); // 권장 (실패 시 false)
pq.add(5); // 실패 시 예외
// 조회 (제거 X)
pq.peek(); // 비어있으면 null
// 삭제
pq.poll(); // 비어있으면 null
pq.remove(); // 비어있으면 예외
// 기타
pq.size();
pq.isEmpty();
pq.clear();
코딩테스트 핵심 패턴
패턴 1: K번째 최대/최소값 , Top K
언제 사용?
- "K번째로 큰/작은 값을 찾으세요"
- "상위 K개를 찾으세요"
- 배열/스트림에서 K번째 요소 찾기
핵심 아이디어: 힙 크기를 K로 제한해서 메모리 절약 + O(n log k) 시간에 해결
K번째 최솟값
public int findKthSmallest(int[] nums, int k) {
// Max Heap 사용 - 큰 값이 루트에 위치
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int num : nums) {
maxHeap.offer(num); // 일단 모든 값 추가
// 힙 크기가 k를 초과하면
if (maxHeap.size() > k) {
maxHeap.poll(); // 가장 큰 값(루트) 제거
}
// 결과: 힙에는 가장 작은 k개만 남음
}
// 힙의 루트 = 작은 k개 중 가장 큰 값 = k번째 작은 값
return maxHeap.peek();
}
/*
예시: [3, 2, 1, 5, 6, 4], k=2 (2번째 작은 값 찾기)
과정:
1. 3 추가 → [3]
2. 2 추가 → [3, 2], size=2
3. 1 추가 → [3, 2, 1], size>k → 3 제거 → [2, 1]
4. 5 추가 → [5, 2, 1], size>k → 5 제거 → [2, 1]
5. 6 추가 → [6, 2, 1], size>k → 6 제거 → [2, 1]
6. 4 추가 → [4, 2, 1], size>k → 4 제거 → [2, 1]
최종: [2, 1] → 루트 2가 정답 (2번째 작은 값)
왜 Max Heap?
- 작은 값들을 유지하면서, 그 중 가장 큰 값(루트)을 쉽게 제거하기 위해
- K개를 유지하면, 루트가 정확히 K번째 작은 값
*/
// 시간: O(n log k), 공간: O(k)
K번째 최댓값
public int findKthLargest(int[] nums, int k) {
// Min Heap 사용 - 작은 값이 루트에 위치
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num); // 일단 모든 값 추가
// 힙 크기가 k를 초과하면
if (minHeap.size() > k) {
minHeap.poll(); // 가장 작은 값(루트) 제거
}
// 결과: 힙에는 가장 큰 k개만 남음
}
// 힙의 루트 = 큰 k개 중 가장 작은 값 = k번째 큰 값
return minHeap.peek();
}
/*
예시: [3, 2, 1, 5, 6, 4], k=2 (2번째 큰 값 찾기)
과정:
1. 3 추가 → [3]
2. 2 추가 → [2, 3], size=2
3. 1 추가 → [1, 2, 3], size>k → 1 제거 → [2, 3]
4. 5 추가 → [2, 3, 5], size>k → 2 제거 → [3, 5]
5. 6 추가 → [3, 5, 6], size>k → 3 제거 → [5, 6]
6. 4 추가 → [4, 5, 6], size>k → 4 제거 → [5, 6]
최종: [5, 6] → 루트 5가 정답 (2번째 큰 값)
왜 Min Heap?
- 큰 값들을 유지하면서, 그 중 가장 작은 값(루트)을 쉽게 제거하기 위해
- K개를 유지하면, 루트가 정확히 K번째 큰 값
*/
// 시간: O(n log k), 공간: O(k)
암기 팁:
- K번째 최솟값 → Max Heap
(k개 빼고 큰 수들은 poll()로 인해 다 잘려나가서 결국 가장 작은 k개가 남고 그걸 poll()하니까 k번째 최솟값을 구할 수 있다.)
K번째 최솟값을 구하기위해 K개만 남겨두고 큰값들은 다 잘라야하니까 Max Heap - K번째 최댓값 → Min Heap
( k개 빼고 작은 수들은 poll()로 인해 다 잘려나가서 결국 가장 큰 k개가 남고 그걸 poll()하니까 k번째 최댓값을 구할 수 있다. )
K번째 최댓값을 구하기위해 K개만 남겨두고 작은값들은 다 잘라야하니까 Min Heap
응용패턴 : Top K 빈도수
"가장 많이 등장한 K개의 요소"
"빈도수 상위 K개 찾기"
빈도수 기준 Top K 문제
public int[] topKFrequent(int[] nums, int k) {
// 1단계: 빈도수 계산
// 시간: O(n)
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
// 2단계: Min Heap 생성
// [숫자, 빈도수]를 빈도수 기준으로 정렬
// 빈도수 낮은 것이 루트에 위치 (Min Heap)
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
// ↑
// a[1] - b[1]이면 빈도수 오름차순
// b[1] - a[1]이면 내림차순 (Max Heap)
// 3단계: 각 (숫자, 빈도수) 쌍을 처리
// 시간: O(n log k) - n개 요소, 힙 크기는 최대 k
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
int num = entry.getKey();
int freq = entry.getValue();
pq.offer(new int[]{num, freq});
// 힙 크기가 k를 초과하면
if (pq.size() > k) {
pq.poll(); // 빈도수가 가장 낮은 것 제거!
}
}
// 결과: 힙에는 빈도수 상위 K개만 남음
// 4단계: 결과 추출
// 시간: O(k log k)
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pq.poll()[0]; // 숫자만 추출
}
return result;
}
패턴 2: 스트림에서 중간값 찾기
언제 사용?
- 실시간으로 데이터가 들어올 때 중간값 추적
- "지금까지 들어온 수들의 중간값은?"
핵심 아이디어:
- 데이터를 절반으로 나눔
- 작은 쪽 절반은 Max Heap에
- 큰 쪽 절반은 Min Heap에
- 두 힙의 루트를 보면 중간값 계산 가능
- 작은 쪽 절반인 Max Heap의 갯수가 큰 쪽 절반인 Min Heap 갯수가 한개 더 많은경우
즉 , 전체 갯수가 홀수개인경우에는 Max Heap의 루트가 중간값이다.
작은 쪽 절반인 Max Heap의 갯수가 큰 쪽 절반인 Min Heap 갯수와 같은경우
즉 , 전체 갯수가 짝수개인경우에는 두 루트의 평균값이 중간값이다.
위의 로직처럼 동작하기 위해
그래서 Max Heap 갯수 >= Min Heap 갯수가 되게끔 유지하는 코드가 들어가있다.
class MedianFinder {
// 작은 쪽 절반 - Max Heap (가장 큰 값이 루트)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// 큰 쪽 절반 - Min Heap (가장 작은 값이 루트)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
/*
불변 조건 (Invariant):
1. maxHeap의 모든 값 ≤ minHeap의 모든 값
2. maxHeap.size() == minHeap.size() 또는 maxHeap.size() == minHeap.size() + 1
3. maxHeap의 루트 = 작은 쪽 최댓값, minHeap의 루트 = 큰 쪽 최솟값
시각화:
작은 쪽 [..... maxHeap.peek()] | [minHeap.peek() .....] 큰 쪽
↑ 중간값 ↑
*/
public void addNum(int num) {
// 1단계: 새 숫자를 일단 maxHeap에 추가
maxHeap.offer(num);
// 2단계: maxHeap의 최댓값을 minHeap으로 이동
// 목적: maxHeap의 모든 값이 minHeap의 모든 값보다 작게 유지
minHeap.offer(maxHeap.poll());
// 3단계: 크기 균형 맞추기
// maxHeap이 항상 같거나 1개 많게 유지
if (maxHeap.size() < minHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
// 홀수 개: maxHeap의 루트가 중간값
if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
}
// 짝수 개: 두 루트의 평균이 중간값
return (maxHeap.peek() + minHeap.peek()) / 2.0;
}
}
/*
==================== 홀수 개 예시: 1, 2, 3 추가 ====================
addNum(1):
1. maxHeap.offer(1)
→ maxHeap = [1]
2. minHeap.offer(maxHeap.poll())
→ maxHeap.poll() = 1
→ maxHeap = [], minHeap = [1]
3. maxHeap.size(0) < minHeap.size(1) → 균형 맞추기
→ maxHeap.offer(minHeap.poll())
→ maxHeap = [1], minHeap = []
상태: maxHeap=[1], minHeap=[]
중간값 = maxHeap.peek() = 1 ✓
---
addNum(2):
1. maxHeap.offer(2)
→ maxHeap = [2, 1] (Max Heap: 2가 루트)
2. minHeap.offer(maxHeap.poll())
→ maxHeap.poll() = 2 (최댓값)
→ maxHeap = [1], minHeap = [2]
3. maxHeap.size(1) == minHeap.size(1) → 균형 맞춤, skip
상태: maxHeap=[1], minHeap=[2]
시각화: [1] | [2]
중간값 = (1 + 2) / 2.0 = 1.5 ✓
---
addNum(3):
1. maxHeap.offer(3)
→ maxHeap = [3, 1] (Max Heap: 3이 루트)
2. minHeap.offer(maxHeap.poll())
→ maxHeap.poll() = 3 (최댓값)
→ maxHeap = [1], minHeap = [2, 3] (Min Heap: 2가 루트)
3. maxHeap.size(1) < minHeap.size(2) → 균형 맞추기
→ minHeap.poll() = 2 (최솟값)
→ maxHeap.offer(2)
→ maxHeap = [2, 1] (Max Heap: 2가 루트), minHeap = [3]
상태: maxHeap=[2, 1], minHeap=[3]
시각화: [1, 2] | [3]
↑ 2가 루트
중간값 = maxHeap.peek() = 2 ✓
실제 정렬: [1, 2, 3] → 중간값 2 맞음!
==================== 짝수 개 예시: 1, 2, 3, 4 추가 ====================
현재 상태: maxHeap=[2, 1], minHeap=[3]
addNum(4):
1. maxHeap.offer(4)
→ maxHeap = [4, 2, 1] (Max Heap: 4가 루트)
2. minHeap.offer(maxHeap.poll())
→ maxHeap.poll() = 4 (최댓값)
→ maxHeap = [2, 1], minHeap = [3, 4] (Min Heap: 3이 루트)
3. maxHeap.size(2) == minHeap.size(2) → 균형 맞춤, skip
상태: maxHeap=[2, 1], minHeap=[3, 4]
시각화: [1, 2] | [3, 4]
↑ 2 ↑ 3
중간값 = (2 + 3) / 2.0 = 2.5 ✓
실제 정렬: [1, 2, 3, 4] → 중간값 (2+3)/2 = 2.5 맞음!
==================== 또 다른 짝수 예시: 5, 15, 1, 3 ====================
addNum(5):
maxHeap=[5], minHeap=[]
중간값 = 5
addNum(15):
1. maxHeap.offer(15) → maxHeap=[15, 5]
2. minHeap.offer(maxHeap.poll()) → maxHeap=[5], minHeap=[15]
3. skip
상태: maxHeap=[5], minHeap=[15]
중간값 = (5 + 15) / 2.0 = 10.0 ✓
실제 정렬: [5, 15] → 중간값 10 맞음!
addNum(1):
1. maxHeap.offer(1) → maxHeap=[5, 1]
2. minHeap.offer(maxHeap.poll()) → maxHeap=[1], minHeap=[5, 15]
3. maxHeap.size(1) < minHeap.size(2)
→ maxHeap.offer(minHeap.poll())
→ maxHeap=[5, 1], minHeap=[15]
상태: maxHeap=[5, 1], minHeap=[15]
중간값 = 5 ✓
실제 정렬: [1, 5, 15] → 중간값 5 맞음!
addNum(3):
1. maxHeap.offer(3) → maxHeap=[5, 3, 1]
2. minHeap.offer(maxHeap.poll()) → maxHeap=[3, 1], minHeap=[5, 15]
3. skip
상태: maxHeap=[3, 1], minHeap=[5, 15]
중간값 = (3 + 5) / 2.0 = 4.0 ✓
실제 정렬: [1, 3, 5, 15] → 중간값 (3+5)/2 = 4 맞음!
==================== 왜 이 방법이 동작하는가? ====================
핵심 원리:
1. 전체 데이터를 두 그룹으로 분할
- 작은 쪽 절반 (maxHeap): 중간값보다 작거나 같은 값들
- 큰 쪽 절반 (minHeap): 중간값보다 크거나 같은 값들
2. maxHeap은 Max Heap이므로:
- 작은 쪽의 "최댓값"이 루트 = 작은 쪽 그룹의 대표값
- 홀수 개일 때 이 값이 정확히 중간값
3. minHeap은 Min Heap이므로:
- 큰 쪽의 "최솟값"이 루트 = 큰 쪽 그룹의 대표값
- 짝수 개일 때 두 루트의 평균이 중간값
4. 항상 maxHeap.size() >= minHeap.size() 유지:
- 홀수 개: maxHeap이 1개 더 많음 → maxHeap.peek()이 중간값
- 짝수 개: 크기 같음 → 두 루트 평균이 중간값
*/
// 시간: addNum O(log n), findMedian O(1)
// 공간: O(n)
N진법
[Java] 10진수 <-> 2진수, 8진수, 16진수로 변환하기
10진수 -> 2진수, 8진수, 16진수로 변환하기 java.lang.Integer의 toBinaryString(), toOctalString(), toHexaString() 메소드를 이용하여 10진수를 2진수, 8진수, 16진수 문자열로 변환할 수 있습니다. 리턴 타입 클래스
hianna.tistory.com
위 블로그있는 방식이 더간단한 방법
아래방법은 반복문으로 구현하는방법 참고용
public class DecimalToBinary {
public static String toBinary(int decimal) {
if (decimal == 0) return "0";
StringBuilder binary = new StringBuilder();
int num = decimal;
while (num > 0) {
binary.append(num % 2); // 나머지를 추가
num = num / 2; // 2로 나눈 몫
}
return binary.reverse().toString(); // 역순으로 뒤집기
}
public static void main(String[] args) {
System.out.println(toBinary(10)); // 1010
System.out.println(toBinary(25)); // 11001
System.out.println(toBinary(255)); // 11111111
}
}
'Backend > Problem Solving' 카테고리의 다른 글
| 코데 대비5 - Deque(덱),동적프로그래밍 (0) | 2025.12.31 |
|---|---|
| 코데 대비3 - 조합,소수구하기,Collection 요소 삭제시 주의점 (0) | 2025.12.12 |
| 코테 대비 2 - 약수구하기, Collection 최대값 구하기, 순열,백트래킹 (0) | 2025.12.10 |
| 코테 대비 1 - List,Map,Comparator,Stream API (0) | 2025.12.10 |
| 프로그래머스] n으로 표현 (0) | 2023.05.17 |