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

개요

이번 알고리즘 스터디가 시작되면서 처음 회차로 해당 4개의 문제를 풀어보았습니다.

 

package sujeong.bruteforce;

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

public class BOJ15649 {
    private static int n,m;
    private static StringBuilder sb;

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

    private static void func(String str, int index){
        if(index==m){
            sb.append(str).append("\n");
            return;
        }
        for(int i=1;i<=n;i++) {
            if (str.equals("")){
                func(str+i,index+1);
            }else if(!str.contains(""+i)){
                func(str+" "+i,index+1);
            }
        }
    }

    private static void output(){
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb.toString());
    }
    public static void main(String[] args) throws IOException {
        input();
        func("",0);
        output();
    }

}

위의 코드는 이번에 풀었던 백준의 brutefoce 유형의 15649번 문제입니다.

 

저는 코드의 재활용성을 조금이나마 높이고자 유저에게 input으로 2개의 숫자를 입력받고, output을 string형태로 출력한다는 점이 공통으로 들어간다는 점을 이용하여 main에서 input(), func("",0), output()의 함수를 공통적으로 실행하도록 하였습니다. input함수와 output함수의 내용은 모든 문제에서 동일하게 사용되었고, func(String str, int index)함수의 내용 중 for문만 다르게 구성하였습니다. 때문에 먼저 input함수와 output함수의 내용을 살펴보고 각 번호에 따라 func함수를 설명하도록 하겠습니다.

 

 

본문

 

1) input

 

input함수는 숫자를 입력받아 n과 m에 각 숫자를 저장하고, 숫자를 담을 StringBuilder를 생성하는 역할을 수행합니다.

input을 받는 것 뿐만 아니라 StringBuilder를 만든다는 점에서 보면 단지 input의 이름을 사용하는 것보단 initialize라는 명칭의 함수를 사용해 initialize, recursion, finalize으로 구성하는 것이 조금 더 알맞겠지만 입력과 출력에 조금 더 초점을 맞추고 싶어 input과 func, output으로 구성하였습니다.

 

 

그리고 최근엔 tui보다 gui를 사용하는 경우가 많았어서 어떤 함수로 숫자를 받아와야할지 고민하다 아래 링크의 글을 보고 아래 사진처럼 정리해 공부해보았습니다.

BufferedReader는 사용자로부터 콘솔로 숫자를 입력받기 위해 사용된 것으로, 특징은 버퍼가 있는 스트림이고 별다른 정규식 검사를 하지 않아 성능이 비교적(ex. Scanner) 좋습니다. 때문에 온전한 문자열을 읽어오지 못하는 InputStream과 InputStreamReader만을 사용하는게 아닌 BufferedReader와 InputStreamReader를 함께 사용하여 사용자로부터 값을 받아왔습니다. 자세한 내용은 원본 정보 링크를 확인해주시기 바랍니다.

 

https://st-lab.tistory.com/41

JAVA [자바] - 입력 뜯어보기 [Scanner, InputStream, BufferedReader]

 

 

2) output

output은 Stringbuilder클래스의 객체인 sb에 담아온 글자를 출력하는 공간입니다.  func함수에서 함수를 빠져나오기 직전에도 \n을 사용하여 줄바꿈을 하기 때문에 이를 삭제해주는 sb.deleteCharAt(sb.length()-1)을 한번 불러주었고, sb.toString()을 통해 객체의 고유아이디가 출력되는 것이 아닌 객체가 담고있는 string의 값을 출력해 주었습니다.

 

3) func (공통)

 

자세한 설명을 하기 전에 재귀에 대한 보충설명을 해주는 링크를 소개드리고자 합니다.

 

recursion을 사용하고 싶어 검색하다가 해당 링크에서 재귀를 위한 3개 조건을 알게되었습니다.

알고리즘 - 완전탐색(Exhaustive Search)

 

 

recursion을 사용하기 위해 주의해야할 3가지의 조건은 다음과 같습니다.

1. 재귀를 탈출하기 위한 탈출 조건이 필요하다

2. 현재 함수의 상태를 저장하는 파라미터가 필요하다.

3. Return문을 신경써야한다.

 

 

private static void func(String str, int index){
        if(index==m){
            sb.append(str).append("\n");
            return;
        }
        for(int i=1;i<=n;i++) {
            if (str.equals("")){
                func(str+i,index+1);
            }else if(!str.contains(""+i)){
                func(str+" "+i,index+1);
            }
        }
    }

15649번의 func 함수

 

이를 적용하여 각 func 함수들은 탈출 조건이 되는 if문과 함께 str로 row안에 저장되는 값들을 저장하며 재귀가 모두 종료되고 출력할 값을 sb(Stringbuilder)에 저장하고, index는 해당 줄의 몇번째 숫자를 담는 것인지 나타내 현재 함수의 상태를 저장하는 파라미터로 사용하였습니다.

 

그리고 각 문제마다 for문에서 적용되는 값만을 다르게 하여 문제를 해결하였습니다.

 

3-1) 15649번 문제

문제링크 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

15649번의 input과 output은 다음과 같습니다.

 

 

15649번의 규칙은 input으로 받은 첫번째 값을 n 두번째 값을 m이라고 할때, 오름차순으로 숫자를 나열해 n으로 시작하는 내림차순으로 숫자를 나열하되 그 값을 m개만 보여주는 것입니다.

 

private static void func(String str, int index){
        if(index==m){
            sb.append(str).append("\n");
            return;
        }
        for(int i=1;i<=n;i++) {
            if (str.equals("")){
                func(str+i,index+1);
            }else if(!str.contains(""+i)){
                func(str+" "+i,index+1);
            }
        }
    }

15649번의 func 함수

 

때문에 i=1부터 n까지 for문을 돌며 하나의 row에 아직 값이 쌓이지 않았을 경우(str.equals("")) 앞부분에 공백을 두지 않기 위해 func함수로 기존에 쌓아둔 str(= "")에 i를 넣어 str파라미터로 넘겨주고, 다음 index에서 같은 작업을 반복하라고 index+1을 해줍니다.

 

그리고 하나의 row에서 각 수는 같은 수는 반복되지 않고 내림차순으로 나열되는 방향이 되기 때문에, !str.contains(""+i)일 경우에만 func함수로 기존에 쌓아둔 str에 공백(" ")을 추가하고 i를 넣어 str파라미터로 넘겨주고, 다음 index에서 같은 작업을 반복하라고 index+1을 해줍니다.

 

조금 더 알기 쉽게 설명을 드리고자 func함수의 맨 앞에 출력물을 넣어 확인해본 결과 다음과 같습니다.

(출력물 : System.out.println("str : "+str+", "+"index : "+index+"\n"+"sb=\n"+sb.toString()))

 

=> 3 2를 인풋으로 넣었을 때, 결과는 다음과 같습니다.

str : , index : 0
sb=

str : 1, index : 1
sb=

str : 1 2, index : 2
sb=

str : 1 3, index : 2
sb= 1 2

str : 2, index : 1
sb=
1 2
1 3

str : 2 1, index : 2
sb=
1 2
1 3

str : 2 3, index : 2
sb=
1 2
1 3
2 1

str : 3, index : 1
sb=
1 2
1 3
2 1
2 3

str : 3 1, index : 2
sb=
1 2
1 3
2 1
2 3

str : 3 2, index : 2
sb=
1 2
1 3
2 1
2 3
3 1

 

15649번 문제는 여기까지 다루도록 하고 다음에는 15650~15652문제를 포스팅하도록 하겠습니다.

 

 

15650 : https://codingjerk-diary.tistory.com/30

[알고리즘풀이]백준 15650: N과 M(2) 스터디 (15649와 함께 보면 좋음)

 

15651 : https://codingjerk-diary.tistory.com/29

[알고리즘풀이]백준 15650 스터디 (15649와 함께 보면 좋음)

 

15652 : https://codingjerk-diary.tistory.com/31

[알고리즘풀이]백준 15652: N과 M(4) 스터디 (15649와 함께 보면 좋음)

 

 

깃 주소 : https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/bruteforce/BOJ15649.java

Park1122/Algorithm-Study