백준12919 : A와 B 2

2024. 2. 27. 18:43·알고리즘/문제풀이
728x90

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

 

12919번: A와 B 2

수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈

www.acmicpc.net

어제 재귀를 풀고 맛이 들렸다.

첨엔 S에 문자열을 붙여가면서 T를 찾아갔는데, 시간초과가 났다.
A개수 B개수 세가면서 플래그를 주다가,,
그냥 T에서 조건절에 따라서 문자열을 제거하며 S를 찾아주면 불필요한 문자열의 탐색 없이 빠르게 찾을 수 있겠구나를 깨달았다.

package BOJ;

import java.util.*;

public class BOJ12919 {
    private static String S;
    private static boolean flag;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        S = sc.nextLine();
        String T = sc.nextLine();
        go(T);
        System.out.println(flag ? 1 : 0);
    }

    private static void go(String T) {
        if (T.length() < S.length() || flag) return;
        flag = S.equals(T);

        int tl = T.length();
        if (T.lastIndexOf('A') == tl - 1) {
            go(T.substring(0, tl - 1));
        }
        if (T.charAt(0) == 'B') {
            go(reverseString(T.substring(1, tl)));
        }
    }

    private static String reverseString(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}
저작자표시 (새창열림)

'알고리즘 > 문제풀이' 카테고리의 다른 글

백준6593: 상범 빌딩(Java)  (0) 2024.03.13
백준9934 - 완전 이진 트리(Java)  (1) 2024.03.01
백준9184: 신나는 함수 실행(Java)  (0) 2024.02.27
백준4179 : 불!  (0) 2023.09.19
백준17106 : 빙고  (0) 2023.06.20
'알고리즘/문제풀이' 카테고리의 다른 글
  • 백준6593: 상범 빌딩(Java)
  • 백준9934 - 완전 이진 트리(Java)
  • 백준9184: 신나는 함수 실행(Java)
  • 백준4179 : 불!
kkap999
kkap999
IT에 관심 가득한 갑갑이의 개발&스터디 블로그
  • kkap999
    갑갑이의 개발세상
    kkap999
    • 분류 전체보기 (95)
      • Backend (1)
        • Java&Spring&Servlet (8)
        • DB (0)
      • 알고리즘 (78)
        • 문제풀이 (70)
        • 자료구조 (6)
        • 그 외 (2)
      • App&FE (3)
        • FE (1)
        • Flutter (2)
      • Computer Science (0)
        • 네트워크 (0)
        • 컴퓨터기초 (0)
      • Cloud (0)
        • AWS (0)
        • Azure (0)
        • gcp (0)
      • 잡담&일상 (4)
        • 일상 (1)
        • 잡담 (2)
        • 음악 (1)
  • 태그

    N과M(1)
    BOJ15649
    BOJ
    알고리즘
    백준
  • 링크

    • github
  • 인기 글

  • 최근 글

  • 07-12 20:35
  • 전체
    오늘
    어제
  • 반응형
  • hELLO· Designed By정상우.v4.10.3
kkap999
백준12919 : A와 B 2

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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