백준 2469[자바] java 사다리 타기

 

문제 링크: https://www.acmicpc.net/problem/2469

2469번: 사다리 타기

▶문제

k명의 참가자들이 사다리 타기를 통하여 어떤 순서를 결정한다. 참가자들은 알파벳 대문자 첫 k개로 표현되며, 사다리 타기를 시작할 때의 순서는 아래 그림과 같이 항상 알파벳 순서대로이다.

k=10 인 예를 들어 보자. 10명의 A, B, C, D, E, F, G, H, I, J 참가자들이 사다리 타기를 준비한다. 아래 그림은 10개의 세로줄과 5개의 가로 줄을 가지고 있는 사다리의 한 예를 보여주고 있다.  

이 사다리에서 점선은 가로 막대가 없음을, 굵은 가로 실선은 옆으로 건너갈 수 있는 가로 막대가 있음을 나타내고 있다.  

따라서 위에 제시된 사다리를 타면 그 최종 도달된 순서는 왼쪽으로부터 A, C, G, B, E, D, J, F, I, H 가 된다. 

사다리 타기는 세로 막대를 타고 내려오는 중에 가로막대를 만나면 그쪽으로 옮겨 가면서 끝까지 내려가는 과정이다.  따라서 사다리 타기의 규칙 특성상 아래 그림과 같이 두 가로 막대가 직접 연결될 수는 없으므로 이 상황은 이 문제에서 고려할 필요가 없다.

우리는 하나의 가로 줄이 감추어진 사다리를 받아서 그 줄의 각 칸에 가로 막대를 적절히 넣어서 참가자들의 최종 순서가 원하는 순서대로 나오도록 만들려고 한다.  

입력에서 사다리의 전체 모양은 각 줄에 있는 가로 막대의 유무로 표현된다. 각 줄에서 가로 막대가 없는 경우에는 ‘*’(별) 문자, 있을 경우에는 ‘-’(빼기) 문자로 표시된다. 그리고 감추어진 특정 가로 줄은 길이 k-1인 ‘?’ (물음표) 문자열로 표시되어 있다.   

▶입력

첫 줄에는 참가한 사람의 수 k가 나온다(3 ≤ k ≤ 26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3 ≤ n ≤ 1,000). 그리고 세 번째 줄에는 사다리를 타고난 후 결정된 참가자들의 최종 순서가 길이 k인 대문자 문자열로 들어온다.

k와 n, 그리고 도착순서 문자열이 나타난 다음, 이어지는 n개의 줄에는 앞서 설명한 바와 같이 ‘*’와 ‘-’ 문자로 이루어진 길이 k-1인 문자열이 주어진다. 그중 감추어진 가로 줄은 길이가 k-1인 ‘?’ 문자열로 표시되어 있다.

▶출력

입력 파일 세 번째 줄에서 지정한 도착순서가 해당 사다리에서 만들어질 수 있도록 감추어진 가로 줄을 구성해야 한다.

여러분은 감추어진 가로 줄의 상태를 재구성하여 이를 ‘*’(별) 문자와 ‘-’(빼기) 문자로 구성된 길이 k-1인 문자열로 만들어 출력하면 된다.

그런데 어떤 경우에는 그 감추어진 가로 줄을 어떻게 구성해도 원하는 순서를 얻을 수 없는 경우도 있다.  이 경우에는  ‘x’(소문자 엑스)로 구성된 길이 k-1인 문자열을 출력해야

▶해설

단순한 구현 문제입니다. 사다리 타기가 무엇인지는 생략하고, 조건을 살펴보겠습니다. 

 

1. '*' 다리가 없는 것

2. '-' 이어지는 다리가 있는 것

3. 만들 수 없을 경우 x를 출력

 

문제를 나눠서 구현할 필요가 있습니다.

 

'???'이 존재하는 row와 사다리의 구성을 2차원 배열에 저장합니다. 

for (int i = 0; i < k; i++) {
    String s = br.readLine();
    for (int j = 0; j < s.length(); j++) {
        if (s.charAt(j) == '?') {
            targetLayer = i;
            Arrays.fill(map[i], '?');
            continue;
        }
        map[i][j] = s.charAt(j);
    }
}

 

'???' row 이전까지 위 아래를 구합니다. 구하는 이유는 '???' 이전의 위의 값이 '???'를 통해 변한 '???'의 아래 값이기 때문입니다. 말이 어려우니 그림으로 보겠습니다. 

 

A B C D E F G H I ->  A C B D E F G I H를 비교하여 '???'를 도출할 수 있기 때문입니다. 위의 그림에선 B와 C I와 H가 바뀌었으니 *-*****-으로 답이 됩니다. 

 

 

위에서 내려오는 것 구하기

private static void makeNext ( int index){
    for (int i = 0; i < n - 1; i++) {
        char now = map[index][i];
        if (now == '-') {
            char prev = top[i + 1];
            top[i + 1] = top[i];
            top[i] = prev;
        }
    }
}

 

아래에서 올라가는 것 구하기

private static void makePrev ( int index){
    for (int i = 0; i < n - 1; i++) {
        char now = map[index][i];
        if (now == '-') {
            char prev = want[i];
            want[i] = want[i + 1];
            want[i + 1] = prev;
        }
    }
}

 

마지막으로 비교를 왼쪽에서 오른쪽으로 진행합니다. 하지만 주의할 점이 있습니다. 

1. i 인덱스의 값이  다를 경우 '-' 추가하고, '*'을 추가해줘야 합니다. 그 이유는 딱 붙어서 변한 경우 다음 값도 영향이 가기 때문입니다. 

2. i가  i+1과도 다르다면? '???' 한층으로는 만들 수 없는 것이므로 'x'로 만듭니다. 

3. i인덱스가 마지막 인덱스이며, 다른 경우는 '-'만 추가하고 끝내야합니다. 

for (int i = 0; i < n - 1; i++) {
    // i 인덱스 비교
    if (top[i] != want[i]) {
        // i+1인덱스와 비교 다른 경우 x로 채운다.
        if(top[i]!=want[i+1]){
            sb.delete(0,sb.length());
            for(int j=0; j<n-1; j++){
                sb.append("x");
            }
            break;
        }
        // 같은 경우 '-'을 추가하고 i+1하여 중복을 방지한다. 
        sb.append("-");
        i+=1;
        // i가 마지막 인덱스에서 다른 경우 추가하지 않는다. 
        if(i<n-1){
            sb.append("*");
        }
        continue;
    }
    // i 인덱스가 같은 경우
    sb.append("*");
}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.lang.*;


public class Main {

    static int n, k;
    static char[][] map;
    static char[] top;
    static int targetLayer;
    static char[] want;

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

        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());

        map = new char[k][n - 1];
        want = new char[n];
        top = new char[n];


        String s1 = br.readLine();


        for (int i = 0; i < s1.length(); i++) {
            want[i] = s1.charAt(i);
            top[i] = (char) ('A' + i);
        }

        for (int i = 0; i < k; i++) {
            String s = br.readLine();
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == '?') {
                    targetLayer = i;
                    Arrays.fill(map[i], '?');
                    continue;
                }
                map[i][j] = s.charAt(j);
            }
        }
        for (int i = 0; i < targetLayer; i++) {
            makeNext(i);
        }

        for (int i = k - 1; i > targetLayer; i--) {
            makePrev(i);
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n - 1; i++) {
            if (top[i] != want[i]) {
                if(top[i]!=want[i+1]){
                    sb.delete(0,sb.length());
                    for(int j=0; j<n-1; j++){
                        sb.append("x");
                    }
                    break;
                }
                sb.append("-");
                i+=1;
                if(i<n-1){
                    sb.append("*");
                }
                continue;
            }
            sb.append("*");
        }
        System.out.println(sb.toString());

    }

        private static void makePrev ( int index){
            for (int i = 0; i < n - 1; i++) {
                char now = map[index][i];
                if (now == '-') {
                    char prev = want[i];
                    want[i] = want[i + 1];
                    want[i + 1] = prev;
                }
            }
        }

        private static void makeNext ( int index){
            for (int i = 0; i < n - 1; i++) {
                char now = map[index][i];
                if (now == '-') {
                    char prev = top[i + 1];
                    top[i + 1] = top[i];
                    top[i] = prev;
                }
            }
        }
    }