[Java] 프로그래머스 - 소수 찾기 (백트래킹)

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

프로그래머스

 

처음 고민

 

1. 모든 길이의 순열을 생성한다.

set으로 중복을 제거해야함. 011 = 11 이기 때문

 

2. Set에 모인 정수들에 대해 sqrt(n)까지 나눠보는 방식으로 소수 여부 확인(간단하고 충분히 빠름).

n < 2는 소수가 아님.

 

 

자바 구현 포인트

• 백트래킹으로 문자열을 이어 붙이면서 매 단계마다(길이가 1 이상이면) 정수로 변환해 Set에 넣는다.
• 중복 방지를 위해 Set<Integer> 사용.
• 방문 체크는 boolean[] used.
• 문자열 누적은 StringBuilder 사용.

import java.util.*;

class Solution {
    public int solution(String numbers) {
        char[] digits = numbers.toCharArray();
        boolean[] used = new boolean[digits.length];
        Set<Integer> made = new HashSet<>();
        
        dfs(digits, used, new StringBuilder(), made);
        
        int count = 0;
        for (int x : made) {
            if (isPrime(x)) count++;
        }
        return count;
    }
    
    private void dfs(char[] digits, boolean[] used, StringBuilder cur, Set<Integer> made){
        if (cur.length() > 0) {
            made.add(Integer.parseInt(cur.toString()));
        }
        
        if (cur.length() == digits.length) return;
        
        for (int i = 0; i < digits.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            cur.append(digits[i]);
            dfs(digits, used, cur, made);
            cur.deleteCharAt(cur.length() -1);
            used[i] = false;
        }
    }
    private boolean isPrime(int n) {
        if (n < 2) return false;
        if (n % 2 == 0) return n == 2;
        for (int d = 3; d * d <= n; d += 2) {
            if (n % d == 0) return false;
        }
        return true;
    }
}

 

 

toCharArray 메서드 : String 문자열을 1개 Char단위의 배열로 만들어준다.

 

Set / HashSet

• Set: 자바에서 중복을 허용하지 않는 자료구조.
  • 배열이나 리스트와 달리, 같은 값이 두 번 들어가면 한 번만 저장.
  • 인터페이스라서 객체를 만들 수 없다. (new Set<>() 불가능)
  • 예: {1, 2, 3}에 2를 또 넣으려 해도 그대로 {1, 2, 3}
• HashSet: Set의 대표 구현체. 내부적으로 해시 테이블을 이용해서 값을 빠르게 넣고/찾는다.
  • 특징: 순서를 보장하지 않음 (넣은 순서대로 안 나올 수 있음).
  • 대신 contains, add, remove 같은 연산이 평균적으로 O(1)이라 빠름.

 

StringBuilder

• String은 불변(immutable) 객체라서, 한 번 만들면 내부 문자를 바꿀 수 없음.
  • → 그래서 문자열을 반복적으로 합치면 새로운 객체가 계속 생성되어 비효율
• StringBuilder는 가변(mutable) 문자열 클래스.
  • 문자를 추가, 삭제, 수정해도 새로운 객체를 만들지 않고 같은 버퍼에서 처리.
  • append, delete, insert, reverse 같은 메서드를 제공.

👉 백트래킹에서 조합을 만들 때 StringBuilder를 쓰면 성능이 훨씬 좋음.

 

String vs StringBuilder 메서드 차이

1. String
- substring(begin, end)
- charAt(i)
- indexOf(x)
- replace(a, b) → 결과는 새로운 문자열 반환

2. StringBuilder
- append(x) → 뒤에 붙이기
- delete(start, end) → 구간 삭제
- deleteCharAt(i) → 특정 위치 문자 삭제
- insert(i, x) → 특정 위치 삽입
- setCharAt(i, x) → 특정 문자 교체