[백준 / JAVA] [S4 / 3048] 개미

Question

문제 보기

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

서로 반대 방향으로 이동하던 두 개미 그룹이 좁은 길에서 만났을 때, 개미는 어떻게 지나갈까?
최근 연구에 의하면 위와 같은 상황이 벌어지면 개미는 서로를 점프해서 넘어간다고 한다.
즉, 두 그룹이 만났을 때, 1초에 한번씩 개미는 서로를 뛰어 넘는다.
(한 개미가 다른 개미를 뛰어 넘고, 다른 개미는 그냥 전진한다고 생각해도 된다)
하지만 모든 개미가 점프를 하는 것은 아니다.
자신의 앞에 반대 방향으로 움직이던 개미가 있는 경우에만 점프를 하게 된다.
첫 번째 그룹이 ABC로 움직이고, 두 번째 그룹의 개미가 DEF순으로 움직인다고 하자.
그럼, 좁은 길에서 만났을 때, 개미의 순서는 CBADEF가 된다.

1초가 지났을 때는 자신의 앞에 반대방향으로 움직이는 개미가 있는 개미는 A와 D다. 따라서, 개미의 순서는 CBDAEF가 된다.
2초가 되었을 때, 자신의 앞에 반대 방향으로 움직이는 개미는 B,D,A,E가 있다. 따라서, 개미의 순서는 CDBEAF가 된다.
T초가 지난 후에 개미의 순서를 구하는 프로그램을 작성하시오.

Answer

💡 main 안에서 호출하는 함수는 static 추가

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {

    static char[] group1;
    static char[] group2;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    // 두 그룹의 개미 수
        String inputValues = br.readLine();
        StringTokenizer st = new StringTokenizer(inputValues);
        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());

        group1 = br.readLine().toCharArray();    // 첫 번째 그룹의 개미 배열
        group2 = br.readLine().toCharArray();    // 두 번째 그룹의 개미 배열

        char[] ants = new char[n1 + n2];    // 하나의 배열에 넣기
        int index = 0;
        for (int i = n1 - 1; i >= 0; i--) {    // 첫 번째 그룹 역순으로 저장
            ants[index++] = group1[i];
        }
        for (int i = 0; i < n2; i++) {        // 두 번째 그룹 순서대로 저장
            ants[index++] = group2[i];
        }
        int time = Integer.parseInt(br.readLine());    // 시간
        for (int i = 0; i < time; i++) {    // 시간만큼 반복
            int changeNum;    // 교환 수
            if (n1 == 1) {
                changeNum = n1;
            } else if ((i + 1) <= n1) {
                changeNum = i + 1;
            } else {
                changeNum = Math.abs(2 * n1 - (i + 1));
            }

            int changeNumCheck = 0;    // 실제 교환 수
            for (int j = 0; j < ants.length - 1; j++) {
                if (changeNumCheck >= changeNum) {
                    break;
                }
                if (check(ants[j], ants[j + 1])) {
                    char temp = ants[j];
                    ants[j] = ants[j + 1];
                    ants[j + 1] = temp;
                    changeNumCheck++;
                    j++; // 다음 개미는 이미 바뀐 상태이므로 건너뛰기
                }
            }
            if (changeNumCheck <= 0) {    // 교환이 하나도 발생하지 않았으면 종료
                break;
            }
        }
        System.out.println(new String(ants));
    }
    // 교환할 개미인지 확인
    public static boolean check(char antA, char antB) {
        boolean isInGroup1 = false;
        boolean isInGroup2 = false;

        for (char c : group1) {
            if (c == antA) {
                isInGroup1 = true;
                break;
            }
        }
        for (char c : group2) {
            if (c == antB) {
                isInGroup2 = true;
                break;
            }
        }
        return isInGroup1 && isInGroup2; // antA가 group1이고 그 다음 값이 group2인 antB이면 교환
    }
}

Result

메모리(KB)	시간(ms)
11508	64