백준 12904번 A와 B

문제

나의 풀이

import java.util.*;
public class Main {
    public static String pop_back(String s) {
        return s.substring(0, s.length() - 1); // 마지막 글자 삭제
    }
    public static String reverse(String s) {
        return new StringBuilder(s).reverse().toString(); // 문자열 뒤집기
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        while(t.length() > s.length()) {
            if(t.charAt(t.length() - 1) == 'A') { // 마지막 글자가 A일 때
                t = pop_back(t); // A 삭제
            } else { // 마지막 글자가 B일 때
                t = pop_back(t); // B 삭제
                t = reverse(t); // 문자열 뒤집기
            }
        }
        
        if(s.equals(t)) { // t로 s를 만들 수 있는 경우
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}

맨 마지막 글자가 A라는 것은 A연산을 수행한 것이고, 맨 마지막 글자가 B라는 것은 B연산을 수행한 것이다.
T를 S로 만들 수 있는지 보는 문제로 변경해서 해결할 수 있다. 즉, 맨 마지막 글자가 A라면 A 글자를 삭제한다. 맨 마지막 글자가 B라면 B를 삭제하고 뒤집는다. 이렇게 길이가 S와 같아질 때 까지 반복하다가 S와 길이가 같아졌을 때 S와 T가 같은지 비교해보고 같으면 1, 다르면 0을 출력하게 하면 된다.

결과

백준 12919번 A와 B 2

문제

나의 풀이

import java.util.*;

public class Main {
    public static String cut(String s) {
        return s.substring(0, s.length() - 1); // 마지막 글자 제거
    }
    public static String rev(String s) {
        return new StringBuilder(s).reverse().toString(); // 문자열 뒤집기
    }
    public static boolean can(String s, String t) {
        if(s.equals(t)) {
            return true;
        }
        if(t.length() > 0) {
            if(t.charAt(t.length() - 1) == 'A' && can(s, cut(t))) {
                return true;
            }
            if(t.charAt(0) == 'B' && can(s, cut(rev(t)))) {
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String t = sc.nextLine();
        System.out.println(can(s, t) ? 1 : 0);
    }
}

T의 마지막 문자가 A라면, A 연산을 사용해서 T를 만든 것이다. T의 첫 문자가 B라면, B연산을 사용해서 T를 만든 것이다.
A...A와 B...A인 경우가 첫번째 경우고, B...A와 B...B인 경우가 두번째 경우에 해당한다. 즉, A...B인 경우는 불가능한 경우다.
즉, A...A는 A연산을 수행하면 되고 B...B는 B연산을 수행하면 된다. T의 첫 문자가 B이고 마지막 문자가 A이면 두 경우 모두 조사하면 된다.

결과

인프런 비밀 번호

문제

나의 풀이

import java.util.Arrays;

public class Password {
    static public int solution(int[] keypad, String password) {
        int answer = 0;
        int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
        int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
        int pad[][] = new int[3][3];
        int dist[][] = new int[10][10];
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                pad[i][j] = keypad[i * 3 + j];
            }
        }
        for(int i = 0; i < 10; i++) {
            Arrays.fill(dist[i], 2); // 2로 초기화
        }
        for(int i = 0; i < 10; i++) {
            dist[i][i] = 0; // 자기 자신은 0초로
        }
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                int from = pad[i][j];
                for(int k = 0; k < 8; k++) { // 8방향 탐색
                    if(i + dx[k] >= 0 && i + dx[k] < 3 && j + dy[k] >= 0 && j + dy[k] < 3) { // 범위 안인 경우
                        int to = pad[i + dx[k]][j + dy[k]];
                        dist[from][to] = 1; // 걸리는 시간 1초로 업데이트
                    }
                }
            }
        }
        for(int i = 1; i < password.length(); i++) {
            int from = (int) password.charAt(i - 1) - 48;
            int to = (int) password.charAt(i) - 48;
            answer += dist[from][to];
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(Password.solution(new int[]{2, 5, 3, 7, 1, 6, 4, 9, 8}, "7596218"));
    }
}

이동 시간은 0초 아니면 1초, 2초 밖에 없다.
dist 배열을 처음에 모두 2로 초기화하고 자기 자신일 경우엔 0으로 초기화한다.
그뒤 키패드마다 이중 for문으로 8방향을 탐색하면서 dist 배열의 값을 업데이트한다. 다하고 나서 password를 선형탐색하면서 answer에 해당하는 dist값들을 더해준다. 만약 7596218이라면 선형탐색을 하면서 7->5는 dist배열의 7행5열 값을 answer에 더해주는 형식으로 진행한다.

결과