백준 30823 건공문자열 Java

: ) YOUNG·2023년 12월 26일
1

알고리즘

목록 보기
285/417
post-thumbnail

백준 30823번
https://www.acmicpc.net/problem/30823

문제



생각하기


  • 문자열 문제이다.

  • 뒤집기를 해야되는데, 브루트포스 문제가 아니다.

    • 브루트포스로 구현했다가 실패함..
    • 머리 잘써서 뒤집혀진 결과만 출력할 수 있도록 하는게 핵심임

동작

문제에 설명이 생각보다 복잡한 것 같은데, 사실 그냥 N길이의 문자열을 K길이 단위 부분 문자열로 나눠서 해당 부분 문자열을 뒤집어서 N길이까지 반복했을 때 나오는 결과를 출력하면 된다.

그래서 이 과정을 반복해서 뒤집어진 결과만 출력하면 된다.


        K--;
        if ((N - K) % 2 == 0) {
            sb.append(S.substring(K)).append(S, 0, K);
        } else {
            sb.append(S.substring(K)).append(new StringBuilder(S.substring(0, K)).reverse());
        }

예시를 N = 6 ,K = 3 , S = abcdef 로 만들어서 해보면,

K가 3이면 마지막 결과가 cdefab 이다.

결국 K부터 N-1길이의 부분 문자열이 가장 앞으로오는 과정이다.


반대로 K가 4로 짝수일 때는 결과가 defcba 이다.

K부터 N-1길이의 부분 문자열이 앞으로 오는 것은 같고, 나머지 0에서 K-1의 문자열이 뒤로가는데, 해당 부분이 홀수이므로 뒤집혀서 올라오게 된다.

그래서 결과를 마지막에 뒤집어서 출력만하면 부르트포스로 진행하지 않고 올바른 결과를 출력할 수 있다.


결국에 패턴을 찾아서 원하는 결과만 출력하면 됨



결과


코드



import java.io.*;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, K;
    private static String S;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        K--;
        if ((N - K) % 2 == 0) {
            sb.append(S.substring(K)).append(S, 0, K);
        } else {
            sb.append(S.substring(K)).append(new StringBuilder(S.substring(0, K)).reverse());
        }

        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        S = br.readLine();
    } // End of input()
} // End of Main class

0개의 댓글