[코드트리/INTERMEDIATE LOW] 특정 조건에 맞게 k개 중에 1개를 n번 뽑기 (JAVA)

📖 문제

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• 백트래킹 (conditional)

1. [조건] 특정 숫자를 뽑을 때, 배열의 오른쪽에 위치한 원소 2개와 해당 숫자가 같은지 확인한다.

   - 이렇게 숫자 3개가 동일하다면, 같은 숫자가 3번 이상 연달아 나오는 것이므로 pass 한다.

   - 다르다면, 다음 백트래킹을 수행한다.

 

2. 같은 숫자 3개가 연달아오지 않는 리스트의 크기가 N과 같을 때, 해당 리스트를 출력한다.

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int K, N;
    static List<Integer> list = new ArrayList<>();
    static Set<String> set = new TreeSet<>();   // 결과 출력용 집합 (중복 제거, 오름차순 정렬)
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
 
        choose(0);
 
        // 출력하기
        StringBuilder sb = new StringBuilder();
        for(String s : set) {
            sb.append(s + "\n");
        }
        System.out.println(sb);
    }
 
    private static void choose(int cnt) {
        if(cnt == N) {
            addToSet();
            return;
        }
 
        for(int i = 1 ; i <= K ; i++) {
            // 같은 숫자가 연속해서 3번 나오는 경우, pass
            if(cnt >= 2 && i == list.get(list.size() - 1) && i == list.get(list.size() - 2))    continue;
            else {
                list.add(i);
                choose(cnt + 1);
                list.remove(list.size() - 1);
            }
        }
    }
 
    private static void addToSet() {
        StringBuilder tmp = new StringBuilder();
        for(int i : list) {
            tmp.append(i + " ");
        }
        set.add(tmp.toString());
        return;
    }
}

 

 

➕ 다른 풀이 방식

결과 출력용 집합을 따로 만들 필요 없이 바로 출력해도 되더라~

- 255ms, 20MB

import java.io.*;
import java.util.*;
 
public class Main {
    public static int k, n;
    public static int n;
 
    public static List<Integer> ans = new ArrayList<>();
    public static BufferedWriter bw;
    
    public static void printAns() {
        for (int curr : ans) {
            bw.write(curr + " ");
        }
        bw.newLine();
    }
 
    public static void collect(int cnt) {
        if (cnt == n) {
            printAns();
            return;
        }
 
        for (int i = 1 ; i <= k ; i++) {
            if (ans.size() >= 2) {
                if (i == ans.get(ans.size() - 1) && i == ans.get(ans.size() - 2)) {
                    continue;
                }
            }
 
            ans.add(i);
            collect(cnt + 1);
            ans.remove(ans.size() - 1);
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
 
        collect(0);
 
        bw.flush();
        bw.close();
    }
}

 

 

---

💦 어려웠던 점

- 같은 숫자가 연달아 3개 오는 걸 어떻게 처리해야할지 고민할 때 리스트의 가장 마지막 원소와 맨 뒤에서 2번째 값을 이용할 생각은 했었다. 그런데 연속해서 같은 수의 갯수를 세는 매개변수를 새로 변수를 만들지 아님 어떻게 해야할지 난감하였다..

- 매개변수도 잘 생각해서 데리고 다니자,,,

 

🧐 새로 알게 된 내용

 > 그냥 재귀함수에 cnt를 변수로 들고 다니면 되는 것이었다~ 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[CODE TREE]특정 조건에 맞게 k개 중에 1개를 n번 뽑기