[자바] 백준 28109 - 약속 장소 2 (java)

목차

문제 : boj28109

 

 

필요 알고리즘

• 문자열, 그리디
  
  • 규칙을 찾아 그리디로 해결 가능하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  규칙만 찾으면 로직은 생각보다 간단하다.

"CDD" 를 가지고 한 글자만 변경해서 사전순으로 어떻게 나타낼 수 있을지 생각해보자.

순서대로 살펴보면 아래와 같다.

// 첫번째 글자만 변경됨
ADD
BDD

// 두번째 글자만 변경됨
CAD
CBD
CCD

// 세번째 글자만 변경됨
CCA
CCB
CDC

// 자기자신
CDD

// 이제 뒤에서부터 변경됨
CDE
CDF
CDG
...
CDY
CDZ

// 뒤에서 2번째 글자
CED
CFD
CGD
...
CYD
CZD

// 첫번째 글자
DDD
EDD
FDD
...
YDD
ZDD

 

  즉 자기 자신을 기준으로 그보다 사전순으로 앞서는건

앞에서 부터 한글자씩 원래 문자보다 더 낮은 문자를 차례대로 대입하면 된다.

그리고 자기 자신이 사전순으로 나온다.

이후 자기 자신보다 사전순으로 뒤인 것은 맨 뒤 문자부터 차례대로 원래 문자보다 더 높은 문자를 차례대로 대입하면 된다.

 

  이제 이걸 구현해주면 되는데, 이하 코드에서 저런식으로 문자를 숫자로 변경해서 처리되는게 이해가 안된다면 '아스키코드표'를 검색해보자.

// 입력받은 문자열보다 사전순으로 앞서는 것 처리
for (int i = 0; i < n; i++) {
    int c = atoi(s[i]);
    if (k-c<=0) {
        s[i] = (char)('A'+k-1);
        System.out.println(s);
        return;
    }

    k-=c;
}

// 입력받은 문자열 자기자신
if (k == 1) {
    System.out.println(s);
    return;
}
k--;

// 입력받은 문자열보다 사전순으로 뒤에 있는 것 처리
for (int i = n-1; i >= 0; i--) {
    int c = 'Z'-'A'-atoi(s[i]);
    if (k-c<=0) {
        s[i] = (char)(s[i]+k);
        System.out.println(s);
        return;
    }

    k-=c;
}

 

 

 

코드 : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        char[] s = br.readLine().toCharArray();
        for (int i = 0; i < n; i++) {
            int c = atoi(s[i]);
            if (k-c<=0) {
                s[i] = (char)('A'+k-1);
                System.out.println(s);
                return;
            }

            k-=c;
        }

        if (k == 1) {
            System.out.println(s);
            return;
        }
        k--;

        for (int i = n-1; i >= 0; i--) {
            int c = 'Z'-'A'-atoi(s[i]);
            if (k-c<=0) {
                s[i] = (char)(s[i]+k);
                System.out.println(s);
                return;
            }

            k-=c;
        }

        System.out.println(-1);
    }

    private int atoi(char c) {
        return c - 'A';
    }
}