[백준] code.plus(브루트 포스 Part 1,JAVA)16936번, 나3곱2

문제 링크

16936번: 나3곱2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 나3곱2을 진행한 결과를 토대로 진행된 순서를 결과로 출력해야 합니다.

2. 나누기는 항상 3으로, 곱하기는 항상 2로 진행됩니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 입력받은 수열을 토대로 나3곱2를 진행되는 경우의 수를 찾습니다.

 

3. 찾은 경우의 수에 수열을 결과로 출력합니다.

 

 

정렬

 

이 문제에서 정렬을 사용하면 시간 복잡도가 효율적으로 바뀝니다.

 

입력받은 모든 숫자를 오름차순으로 정렬한 뒤에 나3곱2을 진행하게 된다면

 

나3을 진행할 때에는 현재 값에 작은 값만 탐색하여 존재하는지 확인

 

곱2을 진행할 때에는 현재 값에 큰 값만 탐색하여 존재하는지 확인

 

모든 값을 탐색하지 않고 범위를 정해서 탐색이 가능하기 때문에 시간 복잡도가 효율적으로 바뀌기 때문에

 

오름차순 정렬을 진행합니다.

 

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 6

수열 = {4, 8, 6, 3, 12, 9}

오른차순 정렬한 수열 = {3, 4, 6, 8, 9, 12}

 

2.  입력받은 수열을 토대로 나3곱2를 진행되는 경우의 수를 찾습니다.

 

시작 값이 3일 때

 

3 × 2 = 6 : O

3 ÷ 3 = 1 : X(입력받은 수열에 존재하지 않습니다.)

 

6 × 2 = 12 : O

6 ÷ 3 = 2 : X(입력받은 수열에 존재하지 않습니다.)

 

12 × 2 = 24 : X(입력받은 수열에 존재하지 않습니다.)

12 ÷ 3 = 4 : O

 

4 × 2 = 8 : O

4 ÷ 3 = ? : X(나누어지지 않습니다.)

 

8 × 2 = 16 : X(입력받은 수열에 존재하지 않습니다.)

8 ÷ 3 = ? : X(나누어지지 않습니다.)

 

입력받은 수열에 9를 사용하지 못하였기 때문에 실패!

 

시작 값이 4일 때

 

4 × 2 = 8 : O

4 ÷ 3 = ? : X(나누어지지 않습니다.)

 

8 × 2 = 16 : X(입력받은 수열에 존재하지 않습니다.)

8 ÷ 3 = ? : X(나누어지지 않습니다.)

 

입력받은 수열에 {3, 6, 9, 12}를 사용하지 못하였기 때문에 실패!

 

시작 값이 6일 때

 

6 × 2 = 12 : O

6 ÷ 3 = 2 : X(입력받은 수열에 존재하지 않습니다.)

 

12 × 2 = 24 : X(입력받은 수열에 존재하지 않습니다.)

12 ÷ 3 = 4 : O

 

4 × 2 = 8 : O

4 ÷ 3 = ? : X(나누어지지 않습니다.)

 

8 × 2 = 16 : X(입력받은 수열에 존재하지 않습니다.)

8 ÷ 3 = ? : X(나누어지지 않습니다.)

 

입력받은 수열에 {3, 9}를 사용하지 못하였기 때문에 실패!

 

시작 값이 8일 때

 

8 × 2 = 16 : X(입력받은 수열에 존재하지 않습니다.)

8 ÷ 3 = ? : X(나누어지지 않습니다.)

 

입력받은 수열에 {3, 4, 6, 9, 12}를 사용하지 못하였기 때문에 실패!

 

 

시작 값이 9일 때

 

9 × 2 = 18 : X(입력받은 수열에 존재하지 않습니다.)

9 ÷ 3 = 3 : O

 

3 × 2 = 6 : O

3 ÷ 3 = 1 : X(입력받은 수열에 존재하지 않습니다.)

 

6 × 2 = 12 : O

6 ÷ 3 = 2 : X(입력받은 수열에 존재하지 않습니다.)

 

12 × 2 = 24 : X(입력받은 수열에 존재하지 않습니다.)

12 ÷ 3 = 4 : O

 

4 × 2 = 8 : O

4 ÷ 3 = ? : X(나누어지지 않습니다.)

 

8 × 2 = 16 : X(입력받은 수열에 존재하지 않습니다.)

8 ÷ 3 = ? : X(나누어지지 않습니다.)

 

입력받은 수열을 모두 사용하였기 때문에 성공

 

 

3. 찾은 경우의 수에 수열을 결과로 출력합니다.

 

순서 : 9 -> 3 -> 6 -> 12 -> 4 -> 8을 결과로 출력!

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 입력된 값을 띄어쓰기 기준 나누었습니다.
• Collections.sort를 이용하여 입력받은 수열에 대하여 오름차순 정렬을 하였습니다.
• cal을 실행하여 입력받은 수열에 대한 나3곱2의 올바른 순서를 구하였습니다.
• 나3곱2의 올바른 순서를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 모든 경우의 나3곱2을 진행하여 수열의 올바른 순서를 찾았습니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static boolean[] visited;	//방문 확인 배열
    static boolean complete = false;	//완성 확인 변수
    static ArrayList<Long> num = new ArrayList<>();	//수열 정보 저장 리스트
    static long[] answer;	//결과가 되는 순서 저장 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        answer = new long[N];
        visited = new boolean[N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력받은 수열값 저장
        for(int i=0;i<N;i++)
            num.add(Long.parseLong(st.nextToken()));
        Collections.sort(num);	//오름차순 정렬
        
        //입력 받은 수열로 모든 경우의 나3곱2 게임 진행
        for(int i=0;i<N;i++){
            if(complete)	//나3곱2로 순서 완성시
                break;
            cal(0, i);
        }

        //결과로 얻은 순서 BufferedWriter 저장
        for(int i=0;i<N;i++)
            bw.write(answer[i] + " ");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //모든 경우 나3곱2 진행하여 올바른 순서 찾는 함수
    static void cal(int count, int index){
        if(answer[N-1]!=0){		//올바른 순서 찾았을 때
            complete = true;		//완성!
            return;
        }
        //탐색 진행
        if(!visited[index]) {
            visited[index] = true;
            answer[count] = num.get(index);
            if (num.get(index)%3 == 0) {	//나3 진행
                //오름차순 정렬로 나누기를 진행해서 현재 값보다 작은 수만 탐색
                for (int i = index - 1; i >= 0; i--) {
                    if(num.get(index)/3==num.get(i)){
                        cal(count+1, i);
                        break;
                    }
                }
            }
            long temp = num.get(index) * 2;	//곱2 진행
            //오름차순 정렬로 곱하기를 진행해서 현재 값보다 큰 수만 탐색
            for(int i=index+1;i<N;i++){
                if(temp == num.get(i)){
                    cal(count+1, i);
                    break;
                }
            }
        }
        visited[index] = false;
    }
}