문제

풀이

문제 분석

• k명의 참가자들이 순서를 결정
• 참가자들은 알파벳 대문자 첫 k개로 표현됨
• 순서는 알파벳 순서대로 사다리를 탄다
• 세로 막대를 타고 내려오던 중에 가로 막대를 만나면 그 쪽으로 옮겨가면서 끝까지 내려가는 과정
• 그 줄의 각 칸에 가로막대를 적절히 넣어서 참가자들이 최종 순서가 원하는 순서대로 나오도록 만들려고 함

입력

• 각 줄에 가로막대가 없으면 *

• 각 줄에 가로막대가 있으면 -

• 감추어진 특정 가로 줄은 길이 k-1인 ? 문자열

• 첫 줄은 참가한 사람의 수 k

• 가로 막대가 놓인 전체 가로 줄의 수 n

• 결정된 참가자들의 최종 순서 k 길이의 대문자 문자열

• 사다리를 나타내는 문자열 (감추어진 가로줄은 길이가 k-1인 ? 문자열)

출력

• 감추어진 가로 줄의 상태를 재구성하여 * 또는 - 문자로 구성된 길이 k-1인 문자열
• 어떻게 구성해도 원하는 순서를 얻을 수 없는 경우 x로 구성된 길이 k-1인 문자열

풀이

ABCDE... 라는 character 형 배열 그 자체를 사다리타고 내려왔을 때의 위치로 생각한다!!!!
즉, (i, j)의 -를 만났을 때에는 i+1번째 알파벳과 j+1번째 알파벳을 바꿔준다
만약 (i,j)의 *을 만난다면 그대로 둔다

그리고 ?인 줄이 될 때까지
위에서 아래로 알파벳이 내려오고
아래에서 위로 알파벳이 올라간다
?인 줄을 만났을 때 위에서 아래로 내려온 알파벳과 아래에서 위로 올라간 알파벳 배열 위치를 비교한다

• 비교했을 때 위치가 바뀌어있는 알파벳이 있다면 -> 위에서 내려오는 알파벳의 위치를 아래에서 올라오는 알파벳 배열의 위치처럼 바꿔줌
  if(start[i] == target[i+1])
  tmp = start[i]
  start[i] = start[i+1]
  start[i+1] = tmp
• 위치가 바뀌지 않은 알파벳이라면 *
• 그 외의 경우 x

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class boj2469 {


public static void main(String[] args) throws IOException{

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				
		int k = Integer.parseInt(br.readLine()); // 알파벳 개수
		int n = Integer.parseInt(br.readLine()); // 사다리 길이
		
		// 시작 알파벳 배열
		char[] startChar = new char[k];
		// A, B, C... 배열 만들기 !!
		for(int i=0; i<k; i++) {
			startChar[i] = (char)('A'+i);
		}
		
		// 최종 도착 알파벳 배열
		char[] finalChar = br.readLine().toCharArray();
		char[][] ladder = new char[n][k-1]; // 가로 줄은 길이 k-1인
		int index = 0; // ?가 있는 위치의 행
		
		// 사다리 완성
		for(int i=0; i<n; i++) {
			ladder[i] = br.readLine().toCharArray();
			
			if(ladder[i][0] == '?') {
				index = i;
			}
		}
		
		//위에서 아래로 시작
		for(int i=0; i<index; i++) {
			for(int j=0; j<k-1; j++) {
				if(ladder[i][j] == '-') {
					// 가로 사다리 만나면 바꿔줌!
					char tmp = startChar[j];
					startChar[j] = startChar[j+1];
					startChar[j+1] = tmp;
				}
			}
		}
		
		//아래에서 위로 시작
		for(int i=n-1; i>index; i--) {
			for(int j=0; j<k-1; j++) {
				
				if(ladder[i][j] == '-') {
					// 가로 사다리 만나면 바꿔줌
					char tmp = finalChar[j];
					finalChar[j] = finalChar[j+1];
					finalChar[j+1] = tmp;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		// 위에서 시작한 배열과 아래에서 시작한 배열 비교
		for(int i=0; i<k-1; i++) {
			if(startChar[i] == finalChar[i]) {
				sb.append("*");
			}
			else if(startChar[i] == finalChar[i+1] || finalChar[i] == startChar[i+1]) {
				char tmp = startChar[i];
				startChar[i] = startChar[i+1];
				startChar[i+1] = tmp;
				sb.append("-");
			} else {
				// 모든 경우에 해당되지 않은 경우
				sb = new StringBuilder();
				for(int j=0; j<k-1; j++) {
					sb.append("x");
				}
				break;
			}
		}
		
		System.out.println(sb);
		
	}

}