SseopE
SseopE
SseopE
전체 방문자
오늘
어제
  • 분류 전체보기 (44)
    • Programming (3)
      • JAVA (3)
    • Spring (7)
      • 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (5)
      • Spring 공부 (0)
    • Infra (6)
      • Docker (3)
      • Kubernetes (3)
      • Kafka (0)
    • Machine Learning (2)
      • Scikit-Learn (1)
      • MLOps (1)
      • BentoML (0)
      • Kubeflow (0)
    • OS (2)
      • Linux (2)
    • Algorithm (23)
      • Sorting (7)
      • BOJ (15)
      • Programmers (0)
      • Data Structure (1)
    • 특강 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 2981번
  • 1541번
  • 도커
  • container
  • 자바
  • 백준
  • Kubernetes
  • scikit learn
  • docker
  • resource
  • Spring
  • BaseEstimator
  • 2580번
  • boj
  • TransformMixin
  • 1931번
  • java
  • 스웜 모드
  • Spring boot
  • 2275번

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
SseopE
Algorithm/BOJ

[BOJ] 15649번 : N과 M (1) (JAVA/자바)

[BOJ] 15649번 : N과 M (1) (JAVA/자바)
Algorithm/BOJ

[BOJ] 15649번 : N과 M (1) (JAVA/자바)

2022. 3. 11. 01:40

문제


알고리즘 고민

1부터 N 까지의 수를 M 개를 나열한 조합을 출력하는 문제이다. 처음에 바로 든 생각은 DFS 였다. 재귀형식의 DFS 를 사용하였는데 visited를 만들어 방문지를 숫자로 하여 중복되지 않도록 하였고, 합계 대신 String 으로 숫자를 만들며 다음 dfs에게 넘겨주었다. String에 넣어준 숫자의 개수가 M이 될때 최종적으로 출력할 정답 StringBuffer에 넣어주면서 return 하였다. 문자열은 만들어서 넘겨주게 되면 새로운 객체가 생성되기 때문에 Call by Reference 의 문제가 생기지 않을거라고 생각했다.


JAVA Code

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

public class Main {
    static StringBuffer sb;
    static int N, M;
    static boolean[] visited;

    public static void dfs(String num) {
        if (num.length() / 2 + 1 == M) {
            sb.append(num).append('\n');
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(num + " " + i);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visited = new boolean[N + 1];

        sb = new StringBuffer();

        for (int i = 1; i <= N; i++) {
            visited[i] = true;
            dfs(String.valueOf(i));
            visited[i] = false;
        }

        System.out.print(sb.toString().strip());
    }
}

'Algorithm > BOJ' 카테고리의 다른 글

[BOJ] 2580번 : 스도쿠 (JAVA/자바)  (0) 2022.04.06
[BOJ] 9663번 : N-Queen (JAVA/자바)  (0) 2022.03.11
[BOJ] 10757번 : 큰 수 A+B (JAVA/자바)  (0) 2022.03.11
[BOJ] 2839번 : 설탕 배달 (JAVA/자바)  (0) 2022.03.11
[BOJ] 2775번 : 부녀회장이 될테야 (JAVA/자바)  (0) 2022.03.11
  • 문제
  • 알고리즘 고민
  • JAVA Code
'Algorithm/BOJ' 카테고리의 다른 글
  • [BOJ] 2580번 : 스도쿠 (JAVA/자바)
  • [BOJ] 9663번 : N-Queen (JAVA/자바)
  • [BOJ] 10757번 : 큰 수 A+B (JAVA/자바)
  • [BOJ] 2839번 : 설탕 배달 (JAVA/자바)
SseopE
SseopE

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.