[BOJ] 백준 2661. 좋은 수열

2024. 5. 9. 14:19· 카테고리 없음

문제

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

 


풀이

백트래킹을 활용한 문제입니다. 

 

 처음에 문제를 보고 정말 많이 헤맸는데, 숫자형으로 표현해야한다는 무의식적인? 고집이 있었습니다. 수열이다보니 숫자로 어떻게 조합을 잘 해야겠다라고 생각한 것이 시간을 많이 잡아먹었습니다.

 

 

  이 문제에서 포인트가 두 가지가 있다고 생각합니다.  첫 번째는 나타낼 수열을 String으로 받는 것, 그리고 좋은 수열인지 아닌지를 어떻게 판단할지입니다.

 

 전체적인 구조는 백트래킹 메서드의 매개변수를 String 형의 수열로 받아, 좋은 수열이 맞다면 다시 재귀를 돌려주는 방식입니다.

 

 좋은 수열인지를 판단하는 메서드는 String을 subString으로 나누어 반복문을 돌며 구간 검사를 진행하면 됩니다. 만약 반복되는 순열 부분이 있다면 false를 리턴해줍니다.

 

 

 아래는 소스 코드입니다.


소스 코드

import java.util.Scanner;

public class B2661_좋은수열 {
    static int N;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        backTracking("");
    }
    
    static void backTracking(String str){
        if(str.length() == N){
            System.out.println(str);
            System.exit(0);
        }
        else{
            for(int i = 1; i<=3;i++){
                if(isNice(str+i)) backTracking(str+i);
            }
        }
    }

    static boolean isNice(String str){
        for(int i = 1; i<=str.length()/2;i++) {
            String front = str.substring(str.length()-2*i,str.length()-i);
            String back = str.substring(str.length()-i, str.length());
            if(front.equals(back)) return false;
        }
        return true;
    }
}

 

 

 

 

동구름이
동구름이
동구름이
동구름
동구름이
전체
오늘
어제
  • 분류 전체보기 (178)
    • Java (63)
      • Java 를 파헤쳐보자 (13)
      • BOJ (45)
      • 프로그래머스 (3)
      • SWEA (1)
      • Java GUI (1)
    • JavaScript (17)
      • JS를 파헤쳐보자 (7)
      • 프로그래머스 (7)
      • JS 학습 정리 (1)
    • Backend (33)
      • Spring (3)
      • HTTP (7)
      • 프로젝트 (10)
      • MySQL (6)
      • Redis (3)
      • Elastic Search (1)
      • 인증, 인가 (3)
    • CS (57)
      • 운영체제 (35)
      • Network (22)
    • Git (2)
    • 개발 관련 이것저것 (2)
    • etc (1)
    • 독서 (0)
    • 사설 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 자바
  • JCF
  • 프로그래머스
  • 큐
  • 백준
  • 인프런
  • 레디스
  • Java
  • 스택
  • 반효경
  • 한양대
  • 운영체제
  • 네트워크
  • OS
  • BOJ
  • 이석복
  • 김영한
  • 모든 개발자를 위한 HTTP 웹 기본 지식
  • 구현
  • 자바스크립트

최근 글

hELLO · Designed By 정상우.v4.2.2
동구름이
[BOJ] 백준 2661. 좋은 수열
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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