20047번 동전 옮기기

문제:

• 문제 링크

100 원짜리 동전과 10 원짜리 동전이 임의의 순서로 한 선 위에 나열되어 있다고 하자. 이제 여기서 ‘두 손가락 이동’ 을 아래와 같이 정의하자.

• 단계 1: 임의의 두 동전을 선택한다.
• 단계 2: 단계 1 에서 선택한 두 동전을 둘의 순서를 유지한 채 임의의 위치로 이동한다. (두 동전 모두 제자리에 있거나 두 동전의 순서를 유지한다면 하나만 이동해도 된다.)

‘두 손가락 이동’ 후에도 다른 동전들 간의 순서는 그대로 유지된다. 예를 들어 100 원을 o, 10 원을 x 라 했을 때, 초기에 동전이 oxoxoxxxoo 와 같이 나열되어 있다 하자. 이제 이들 중 굵게 표시된 두 동전을 선택하여 두 손가락 이동을 한번 한 경우, 나올 수 있는 여러 결과들 중에서 네 가지 결과만 아래에 표시했다 (아래 예시에 없는 다른 결과들 또한 나올 수 있음에 유의하자).

• oxoxoxxxoo
• oxooxxxxoo
• oxoxoxxoxo
• oxoxoxxxoo

n 개의 동전이 나열되어 있는 두 상태 S, T와 함께 두 손가락 이동을 위해 선택할 두 동전의 위치가 주어졌을 때, 한번의 두 손가락 이동을 통해 S에서 T로의 변환이 가능한지 결정하는 프로그램을 작성하시오.

입력:

입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T 는 o 와 x 로 이루어진 길이가 n 인 문자열로 표현된다 (o 와 x 는 모두 소문자이다). 동전의 위치는 왼쪽에서 오른쪽으로 0부터 n − 1까지 차례대로 번호를 매겨 구분한다. 마지막 줄에는 두 손가락 이동을 위해 선택할 두 동전의 위치 i와 j가 주어지며, i는 j 보다 작다 (0 ≤ i < j ≤ n − 1).

출력:

출력은 표준출력을 사용한다. 한번의 두 손가락 이동을 통해 S 에서 T로의 변환이 가능한 경우 YES 를, 그렇지 않은 경우 NO 을 출력한다.

접근 방법

시작 문자열과 종료 문자열 2개의 입력을 받는데 시작문자열을 두 손가락 이동으로 종료 문자열 만들기

1. 시작 문자열을 두 동전을 따로 분리시켜 동전 문자열과 분리된 문자열 2개로 분리한다.
2. 종료 문자열에 값이 무엇인지 확인하면서 동전문자열과 분리된 문자열 중 사용할 수 있는 문자열의 값을 사용해 종료 문자열을 만든다.

말이 어려워 보이는데 그냥 문자열을 분해시켜서 결과에 맞는 답이 나오는지 확인하는 과정을 거쳤다.
예를 들어
oxoxoxxxo 문자열을 4 번 5 번 인덱스를 따로 분리시켜
동전 문자열 (ox)
분리된 문자열(oxoxxxo)
두개로 oxoxoxxox를 만들어서 가능하면 YES 불가능하면 NO

동전문자열과 분리된문자열 두개다 사용가능할때 처리만 잘해주면 쉽게 풀 수 있는 문제인 것같다.

코드

접기/펼치기

import java.util.Scanner;

public class 동전_옮기기
{
    public static void main(String [] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        char[] start = sc.nextLine().toCharArray();
        char[] end = sc.nextLine().toCharArray();
        int x = sc.nextInt();
        int y = sc.nextInt();

        char[] newStr = new char[n-2];
        char[] subStr = new char[]{start[x],start[y]};
        for(int i = 0,j=0 ; i <n-2 ; j++)
        {
            if(j == x || j == y) continue;
            newStr[i++] = start[j];
        }

        int index = 0;
        int subIndex = 0;

        boolean isFind = true;
        for(int i = 0 ; i < n ; i++)
        {
            if(index < n-2 && end[i] == newStr[index] && subIndex < 2 && end[i] == subStr[subIndex]){

                if(index +1 < n-2 && subIndex +1 < 2)
                {

                    if (end[i+1] != newStr[index+1] && end[i+1] == subStr[subIndex+1]) {
                        subIndex++;
                    }
                    else index++;
                }
                else if(subIndex+1 < 2)
                {
                    if(subStr[subIndex+1] == end[i+1]) subIndex++;
                    else index++;
                }
                else
                {
                    index++;
                }

            }

            else if(index < n-2 &&end[i] == newStr[index])
            {
                index ++;
            }
            else if(subIndex < 2 && end[i] == subStr[subIndex])
            {
                subIndex++;
            }
            else
            {
                isFind = false;
                break;
            }
        }
        if(isFind)
        System.out.println("YES");
        else 
        System.out.println("NO");

    }
}