BOJ_15652 : N과 M (4)

👉 문제링크

15652번: N과 M (4)

---

---

🔸 문제 분석 🔸

• 1부터 N까지의 수 중에서 M을 선택할 수 있는 경우의 수를 출력한다.
• 같은 수를 골라도 되지만 출력은 오름차순이어야 한다. ( == 비내림차순)
• 재귀형식으로 백트래킹이 필요한데, 스택으로 구현할 수 있다.

🔸 코드 🔸

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Stack<Integer> stack = new Stack<>();
        stack.push(1);

        while (!stack.isEmpty()) {
            if (stack.size() == m) {
                for (int i : stack) {
                    System.out.print(i + " ");
                }
                System.out.println("");

                while (!stack.isEmpty()) {
                    int temp = stack.pop();
                    if (temp + 1 <= n) {
                        stack.push(temp + 1);
                        break;
                    }
                }
            }
            else stack.push(stack.peek());
        }
    }
}

🔸 코드 해석 🔸

• 재귀형식으로 수를 선택하는 것을 스택으로 구현했다.
• 스택의 원소가 m개가 되지 않았다면, 스택의 마지막 원소와 같은 값을 push한다.
• 스택의 원소가 m개라면, 원소를 출력한다.
  • 출력 후 pop한 원소에 +1 하고 push한다.
  • +1 한 수가 m을 넘으면 다음 원소를 pop한다.
  • pop할 원소가 남지 않았다면 프로그램을 종료한다.

---

🔸 end 🔸

• N과 M 시리즈를 풀며 재귀 메소드에 익숙해져서 이번엔 스택으로 풀고자 했는데, 접근 방식을 달리하니 조금 어렵게 느껴졌다.
• 스택의 원소를 바로 출력할 수 없어서 출력을 위한 다른 ArrayList를 만들어서 값을 주고받고 해야하는 줄 알았는데, 시험삼아 for-each문으로 스택 원소를 출력해보니 가능해서 이 방법을 선택했다.
• java의 Stack클래스는 원소를 꺼내거나 넣을때 사용하는 메소드가 여러 이름이 있는 것 같아 알아보았다.
  • 포스팅 내용 
    • push()는 stack에서 제공, add()는 List에서 제공하는 메서드이다.
    • push()의 리턴값은 <E>이고, add()의 리턴값은 boolean이다.
  • <E>는 무엇인가 다시 찾아보았다. (포스팅)
    • Generic형태 : 가상의 타입으로 선언하는 것
    • 따라서 Stack<E>에서 선언한 자료형을 반환하는 것
  • 코드의 psuh를 println()으로 감싸보니, 스택에 psuh()로 넣은 값을 다시 반환해서 출력되었다.

​