프로그래머스 고득점 Kit 하루만에 뽀개기 - 5. 완전탐색(Java, C++) 풀이

https://programmers.co.kr/learn/courses/30/parts/12230

프로그래머스

- 알고리즘 풀이로 C++를 주로 사용하다가 기업 코딩테스트를 위해 java 풀이를 학습하는 사람에게 도움이 될만한 포스트입니다. 알고리즘 적인 해설내용은 줄이고 C++에 익숙한 사람들이 Java 사용시 놓칠만한 내용 위주로 작성하고 있습니다.

- C++에서는 <algorithm> 헤더에 있는 next_permutation, prev_permutation도 이용할 수 있지만, 이게 없어도, 방문여부를 체크하는 배열을 이용한 DFS를 이용하거나 비트마스킹 등을 이용해서 부분집합을 만들어서 완전탐색을 할 수 있다.

1. 모의고사

https://programmers.co.kr/learn/courses/30/lessons/42840

코딩테스트 연습 - 모의고사

// java
import java.util.*;

class Solution {
    public List<Integer> solution(int[] answers) {
        List<Integer> ans = new ArrayList<>();
        int N = answers.length;        
        int[] cnt = new int[3];
        int[] a = {1, 2, 3, 4, 5}; // 5 
        int[] b = {2, 1, 2, 3, 2, 4, 2, 5}; // 8
        int[] c = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; // 10
        
        for(int i = 0; i < N; ++i) {
            if(a[i % 5] == answers[i]) ++cnt[0];
            if(b[i % 8] == answers[i]) ++cnt[1];
            if(c[i % 10] == answers[i]) ++cnt[2];
        }
        
        int max = Arrays.stream(cnt).max().getAsInt();
        for(int i = 0; i < 3; ++i) {
            if(cnt[i] == max) ans.add(i+1);
        }

        return ans;
    }
}

 

- 정답 배열의 크기가 변하는 문제의 경우 ArrayList에 담은 뒤에 stream을 이용해서 기본타입으로 형변환 뒤에 배열로 바꿔준다

 

2. 소수 찾기

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

코딩테스트 연습 - 소수 찾기

- 종이조각으로 만들 수 있는 모든 경우의 수를 다 만들어서 중복처리를 위해 선언한 set에 넣어준다. 소수인지도 검사해준다.
- numbers 문자열의 길이가 7밖에 안되서 간단하게 제곱근 범위까지 검사하는 소수 판별 로직을 쓴다.
- 소수 검사시에 for문 종료조건을 i * i <= n 혹은 i <= sqrt(n)으로 해주면 된다. i*i로 처리시에 overflow가 나지 않도록 주의한다.

// C++
#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;

bool isPrime(int n) {
    if(n < 2) return false;
    for(int i = 2; i * i <= n; ++i) {
        if(n % i == 0) return false;
    }
    return true;
}

int solution(string numbers) {
    int N = numbers.length();
    unordered_set<int> uset;
    sort(numbers.begin(), numbers.end());
    
    do {
        for(int i = 0; i < N; ++i) {
            int mk = stoi(numbers.substr(0, i+1));
            if(isPrime(mk)) uset.insert(mk);
        }
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    return uset.size();
}

// java
import java.util.*;

class Solution {
    Set<Integer> set = new HashSet<>();
    boolean[] check = new boolean[7];
    
    public int solution(String numbers) {
        go(0, "", numbers);
        return set.size();
    }
    
    void go(int idx, String s, String numbers) {
        if(!s.isEmpty()) {
            int n = Integer.parseInt(s);
            if(isPrime(n)) set.add(n);
        }
        if(idx == numbers.length()) return;
        
        for(int i = 0 ;i < numbers.length(); ++i) {
            if(check[i]) continue;
            check[i] = true;
            go(idx+1, s + numbers.charAt(i), numbers);
            check[i] = false;
        }
    }
    
    boolean isPrime(int n) { 
        if(n < 2) return false;
        for(int i = 2; i*i <= n; ++i) {
            if(n % i == 0) return false;
        }
        return true;
    }
}

- java에서 String은 불변객체이고, []연산자가 없다. charAt(idx)로 접근해야한다. 
- string 연산이 많아지면 java.lang의 StringBuilder를 사용할 수 있지만 여기서는 굳이 사용하지 않는다

 

3. 카펫

https://programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

- 가운데가 노란색인 카펫 패턴을 보면 테두리 1줄만 갈색이므로 (가로 -2) * (세로 - 2) = 노란색 갯수 이다
노란색+갈색 갯수의 최대값이 200만이므로 가로 길이 1에서부터 가로*가로 <= 전체갯수일 때까지 가로크기를 증가시키면서 노란색갯수가 이 케이스에 맞는지 탐색해나간다

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[] {0, 0};
        int n = brown + yellow;
        for(int i = 1; i * i <= n; ++i) {
            int x = n / i, y = i;
            if((x - 2) * (y - 2) == yellow) {
                answer[0] = x;
                answer[1] = y;
                break;
            }
        }
        return answer;
    }
}