[알고리즘풀이]백준 15663: N과 M (9) JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이전에 알고리즘 스터디에서 JAVA를 이용해 백준 15663번 N과 M (9)를 풀었습니다. 이를 정리해보고자 합니다.

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

본문

1) 문제

 

2) 과정

초반에 풀었던 거라 어느정도 시간이 걸렸는지 잘 기억은 안나지만 15649~15652와 비슷하였음에도 좀 어렵게 풀었던 문제로 기억합니다.

 

(나머지 n과 m이 연결되어있는 15649 포스트 링크는 아래와 같습니다.)

[알고리즘풀이]백준 15649: N과 M(1) 스터디 (15650, 15651, 15652와 input, output동일)

 

이 문제는 main에 input과 func, output으로 구성하여 풀었습니다.

 

2-1) main

    private static int n,m;
    private static int[] intArr;
    private static boolean[] visited;
    private static LinkedHashSet<String> stringSet;
    
    public static void main(String[] args) throws IOException {
        input();
        func("",0);
        output();
    }

main은 다음과 같이 input, func, output으로 구성했습니다.

n,m은 입력받은 자연수 n과 m을 의미하고, intArr은 n개의 자연수들을 담은 배열입니다.

visited는 방문한 적 있는 숫자인지 체크하는 데 사용했고 stringset은 출력에 쓸 값들을 담고자 사용했습니다.

 

2-2) input()

    private static void input() throws IOException {
        // Input
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] strArrFirst = reader.readLine().split(" ");
        n = Integer.parseInt(strArrFirst[0]);
        m = Integer.parseInt(strArrFirst[1]);

        String[] strArrSec = reader.readLine().split(" ");
        intArr = new int[n];
        for(int i =0;i<n;i++) intArr[i]=Integer.parseInt(strArrSec[i]);
        
        // Initialize
        Arrays.sort(intArr);
        visited = new boolean[n];
        stringSet = new LinkedHashSet<>();

    }

 

읽어오는 것 관련된 정보는 아래 링크를 확인해주세요 :)

[개념정리] System.in / InputStreamReader / BufferedReader 정리

첫번째 줄을 읽어 n과 m에 값을 넣어줍니다. 이후 두번째 줄에서 String으로 받은 배열을 intArr에 넣어주고 정렬한 뒤, visited와 stringSet을 만듭니다.

 

2-3) func("",0)

    private static void func(String str, int index){
    	// 종료조건
        if(index==m){
            stringSet.add(str);
            return;
        }
        // 수열을 만듦
        for(int i=0;i<n;i++) {
            if(visited[i]) continue;
            visited[i]=true;
            if (index==0) func(str + intArr[i], index + 1);
            else func(str+" "+intArr[i],index+1);
            visited[i]=false;
        }
    }

func("",0)로 func를 처음 불러줍니다. func는 종료 조건을 체크하는 부분과 수열을 만들어나가는 부분으로 구성되어 있습니다. 

 

먼저, 종료조건을 체크하는 부분은 index==m일 때 stringSet에 쌓아온 str을 넣어주고 종료합니다.

 

그리고 수열을 만들어나가는 부분은 방문한 적있는 인덱스라면 넘어가고, 아니라면 해당 인덱스의 visited를 true로 변경한 뒤, index가 0일 땐(처음으로 값을 쌓을 땐) 띄어쓰기 없이 해당 인덱스 값을 넣고 다음 인덱스를 넣도록 func를 호출하고, 그 이후의 인덱스에서는 띄어쓰기를 넣어 func를 호출하도록 했습니다.

 

이렇게 되면 예제 입력 2와 같은 상황(n=4, m=2, 배열={9,7,9,1})에서,

앞서 정렬된 1, 7, 9, 9가

0번째 index에 1이 str로 쌓인 상황에선 7, 9, 9를 담은 값이 stringSet에 추가되고,

0번째 index에 7이 str로 쌓인 상황에선 1, 9, 9를 담은 값이 추가되고,

0번째 index에 9가 str로 쌓인 상황에선 1, 7, 9를 담은 값이 추가됩니다.

 

LinkedHashSet은 중복은 허용하지 않기 때문에 1 7, 1 9,  7 1, 7 9, 9 1, 9 7, 9 9가 stringSet에 담겨있게 됩니다.

2-4) output()

    private static void output() {
        for(String s : stringSet) System.out.println(s);
    }

output에서는 stringSet에 저장한 수열들을 for문을 통해 출력합니다.

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.bruteforce;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedHashSet;

public class BOJ15663 {
    private static int n,m;
    private static int[] intArr;
    private static boolean[] visited;
    private static LinkedHashSet<String> stringSet;

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] strArrFirst = reader.readLine().split(" ");
        n = Integer.parseInt(strArrFirst[0]);
        m = Integer.parseInt(strArrFirst[1]);

        String[] strArrSec = reader.readLine().split(" ");
        intArr = new int[n];
        for(int i =0;i<n;i++) intArr[i]=Integer.parseInt(strArrSec[i]);
        Arrays.sort(intArr);

        visited = new boolean[n];
        stringSet = new LinkedHashSet<>();

    }

    private static void func(String str, int index){
        if(index==m){
            stringSet.add(str);
            return;
        }
        for(int i=0;i<n;i++) {
            if(visited[i]) continue;
            visited[i]=true;
            if (index==0) func(str + intArr[i], index + 1);
            else func(str+" "+intArr[i],index+1);
            visited[i]=false;
        }
    }

    private static void output() {
        for(String s : stringSet) System.out.println(s);
    }


    public static void main(String[] args) throws IOException {
        input();
        func("",0);
        output();
    }

}

 

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/bruteforce/BOJ15663.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비