[Java] 백준 3048번 : 개미

문제

개미가 일렬로 이동할 때, 가장 앞의 개미를 제외한 나머지 개미는 모두 앞에 개미가 한 마리씩 있다. 

서로 반대 방향으로 이동하던 두 개미 그룹이 좁은 길에서 만났을 때, 개미는 어떻게 지나갈까?

최근 연구에 의하면 위와 같은 상황이 벌어지면 개미는 서로를 점프해서 넘어간다고 한다.

즉, 두 그룹이 만났을 때, 1초에 한번씩 개미는 서로를 뛰어 넘는다. (한 개미가 다른 개미를 뛰어 넘고, 다른 개미는 그냥 전진한다고 생각해도 된다)

하지만 모든 개미가 점프를 하는 것은 아니다. 자신의 앞에 반대 방향으로 움직이던 개미가 있는 경우에만 점프를 하게 된다.

첫 번째 그룹이 ABC로 움직이고, 두 번째 그룹의 개미가 DEF순으로 움직인다고 하자. 그럼, 좁은 길에서 만났을 때, 개미의 순서는 CBADEF가 된다. 1초가 지났을 때는 자신의 앞에 반대방향으로 움직이는 개미가 있는 개미는 A와 D다. 따라서, 개미의 순서는 CBDAEF가 된다. 2초가 되었을 때, 자신의 앞에 반대 방향으로 움직이는 개미는 B,D,A,E가 있다. 따라서, 개미의 순서는 CDBEAF가 된다.

T초가 지난 후에 개미의 순서를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 첫 번째 그룹의 개미의 수 N1과 두 번째 그룹의 개미의 수 N2가 주어진다.

다음 두 개 줄에는 첫 번째 그룹과 두 번째 그룹의 개미의 순서가 주어진다. 각 개미는 알파벳 대문자로 표현할 수 있으며, 두 그룹에서 중복되는 알파벳은 없다.

마지막 줄에는 T가 주어진다. (0 ≤ T ≤ 50)

출력

T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다.

예제 입력 1

3 3
ABC
DEF
0

예제 출력 1

CBADEF

예제 입력 2

3 3
ABC
DEF
2

예제 출력 2

CDBEAF

예제 입력 3

3 4
JLA
CRUO
3

예제 출력 3

CARLUJO

 

소스코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	private static int N1, N2, T;
	private static String s1;
	private static String s2;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N1=sc.nextInt();
		N2=sc.nextInt();
		
		s1=sc.next();
		s2=sc.next();
		int lenS1=s1.length();
		int lenS2=s2.length();
		
		List<Integer> arr=new ArrayList<>();	// 첫번째 개미 그룹과 두번째 개미 그룹의 순서를 저장하는 리스트
		for(int i=0;i<N1;i++) arr.add(1);	// 첫번째 개미 그룹은 1을 저장(오른쪽으로 이동)
		for(int i=0;i<N2;i++) arr.add(0);	// 두번째 개미 그룹은 0을 저장(왼쪽으로 이동)
		String result="";
		T=sc.nextInt();
		if(T>=lenS1+lenS2) {	// 두 개미 그룹의 길이보다 T가 더 클 경우, 더 이상 점프할 경우가 없기 때문에 결과를 바로 출력
			for(int i=0;i<s2.length();i++) result+=s2.charAt(i);
			for(int i=s1.length()-1;i>=0;i--) result+=s1.charAt(i);
		} else {
			for(int i=0;i<T;i++) {
				for(int start=1;start<arr.size();start++) {
					if(arr.get(start-1)>arr.get(start)) {	// 다음 인덱스에 현재보다 작은 값이 저장되어 있는 경우, 반대방향으로 움직이는 개미가 있는 것이므로 점프를 한다.
						arr.set(start-1, 0);
						arr.set(start, 1);
						start++;
					}
				}
			}
			int idxS1=lenS1-1;
			int idxS2=0;
			for(int i=0;i<arr.size();i++) {
				if(arr.get(i)==1) {
					result+=s1.charAt(idxS1--);
				} else if(arr.get(i)==0) {
					result+=s2.charAt(idxS2++);
				}
			}
		}
		System.out.println(result);
	}
}

1. 첫번째 개미 그룹은 오른쪽으로 이동하므로 1을 개미 수만큼 저장해줍니다.

2. 두번째 개미 그룹은 왼쪽으로 이동하므로 0을 개미 수만큼 저장해줍니다.

3. T가 두 개미 그룹의 합보다 크거나 같으면, 이미 모든 개미가 반대 방향으로 이동한 후이므로 최종 순서를 출력합니다.

4. T가 두 개미 그룹의 합보다 작으면, 반대 방향으로 이동할 개미가 남은 것이므로 

    4-1. 전체 순서를 순회하며 '현재 값<다음 값' 인 경우 두 값의 위치를 바꿔줍니다.

    4-2. T초까지 4-1.을 반복하고, 최종 리스트에서 값이 1인 경우 첫번째 개미 그룹, 0인 경우 두번째 개미 그룹을 순서대로 할당해줍니다.