백준 3048 개미[Java]

https://www.acmicpc.net/problem/3048

접근

• n1이 n2보다 길거나, 같거나, 작은 경우 3가지에 대해 직접 풀어보면서 규칙을 찾아보았다.

3 3
0: CBA DEF
1: CB DA EF
2: C DB EA F
3: DC EB FA

4: DEC FBA
5: DEFCBA 


3 4
0: ALJ CRUO
1: AL CJ RUO
2: A CL RJ UO
3: CA RL UJ O

4: CRA UL OJ	
5: CRUA OLJ
6: CRUOALJ

4 3
0: ABCD EFG
1: ABC ED FG
2: AB EC FD G
3: A EB FC GD
4: EA FB GCD

5: EFA GBCD
6: EFGABCD

• n1이 t보다 크거나 같은 경우와 n1이 t보다 작은 경우 둘로 나누어서 해결한다.
• n1이 t보다 큰 경우, n1-t 만큼 ant[0]의 문자를 추가한다. n1-i, n2, t 중 작은 수만큼 ant[1]과 ant[0]의 문자를 추가한다. 그리고 ant[1]과 ant[0]에 남은 문자가 있으면 순서대로 문자열에 추가한다.
• n1이 t보다 작은 경우, t-n1+1 만큼 ant[1]의 문자를 추가한다. n1, n2-j, t 중 작은 수만큼 ant[0]과 ant[1]의 문자를 추가한다. 그리고 ant[0]과 ant[1]에 남은 문자가 있으면 순서대로 문자열에 추가한다.

나의 풀이

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        //개미그룹의 수 n1, n2 입력
        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());
        int t, temp;
        int i = 0, j = 0;

        //개미 입력
        String[] ant = new String[2];
        while(i < 2) {
            ant[i] = br.readLine();
            i++;
        }
        t = Integer.parseInt(br.readLine());

        //첫번째 개미 그룹(ant[0]) 문자열을 reverse
        StringBuilder sb0 = new StringBuilder(ant[0]);
        ant[0] = sb0.reverse().toString();
        StringBuilder ans = new StringBuilder();

        //t가 n1 + n2 - 1 이상인 경우 개미의 순서는 똑같기 때문에 t = n1 + n2 - 1
        if (t > n1 + n2) {
            t = n1 + n2 - 1;
        }

        i = 0; j = 0;
        if (n1 >= t) {
            temp = n1 - t;

            //n1 - t 만큼 ant[0]의 문자를 추가
            for (i = 0; i < temp; i++)
                ans.append(ant[0].charAt(i));

            //ant[1]과 ant[0]의 문자를 순서대로 추가
            int min = Math.min(n1 - i, n2);
            min = Math.min(min, t);
            for (temp = 0; temp < min; temp++) {
                ans.append(ant[1].charAt(j));
                ans.append(ant[0].charAt(i));
                j++; i++;
            }

            //남은 문자가 있으면 추가
            if (j < n2) {
                for ( ; j < n2; j++)
                    ans.append(ant[1].charAt(j));
            }
            if (i < n1) {
                for ( ; i < n1; i++)
                    ans.append(ant[0].charAt(i));
            }
        }
        else {
            temp = t - n1;

            //t - n1 + 1 만큼 ant[1]의 문자를 추가
            for (j = 0; j <= temp; j++)
                ans.append(ant[1].charAt(j));

            //ant[0]과 ant[1]의 문자를 슨서대로 추가
            int min = Math.min(n1, n2 - j);
            min = Math.min(min, t);
            for (temp = 0; temp < min; temp++) {
                ans.append(ant[0].charAt(i));
                ans.append(ant[1].charAt(j));
                i++; j++;
            }

            //남은 문자가 있으면 추가
            if (i < n1) {
                for ( ; i < n1; i++)
                    ans.append(ant[0].charAt(i));
            }
            if (j < n2) {
                for ( ; j < n2; j++)
                    ans.append(ant[1].charAt(j));
            }
        }
        System.out.println(ans);
    }
}

• StringBuilder를 이용해 ant[0]의 문자열을 reverse하고 답을 StringBuilder에 저장한다.
• t는 0부터 50 사이의 정수인데, t가 n1 + n2 - 1 이상인 경우 개미의 순서는 똑같기 때문에 t = n1 + n2 - 1 를 추가한다.

각각의 경우에 대해 마지막 for문을 없애면 틀린다.

---

다른 사람의 풀이

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        //개미그룹의 수 n1, n2 입력
        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());
        int t;
        int i = 0, j = 0;

        //개미 입력
        String[] ant = new String[2];
        while(i < 2) {
            ant[i] = br.readLine();
            i++;
        }
        t = Integer.parseInt(br.readLine());

        //t가 n1 + n2 - 1 이상인 경우 개미의 순서는 똑같기 때문에 t = n1 + n2 - 1
        if (t > n1 + n2) {
            t = n1 + n2 - 1;
        }

        //첫번째 개미 그룹(ant[0]) 문자열을 reverse
        StringBuilder sb0 = new StringBuilder(ant[0]);

        //전체 개미 위치를 나타낼 문자배열과 방향을 나타내줄 상태배열
        ant[0] = sb0.reverse().append(ant[1]).toString();
        char[] ants = ant[0].toCharArray();
        boolean[] check = new boolean[n1 + n2];

        //개미 그룹1이면 true, 개미 그룹2이면 false
        for (i = 0; i < n1; i++)
            check[i] = true;
        for (; i < n1+ n2; i++)
            check[i] = false;


        while(t-- > 0) {
            for (i = 0; i < n1 + n2 - 1; i++ ) {
                if (check[i] && !check[i+1]) {
                    //개미의 위치 swap
                    char tmp = ants[i];
                    ants[i] = ants[i+1];
                    ants[i+1] = tmp;
                    //방향도 swap
                    boolean tmp2 = check[i];
                    check[i] = check[i+1];
                    check[i+1] = tmp2;

                    i++;
                }
            }
        }

        for (char ch: ants)
            System.out.print(ch);
    }
}

• 방향을 나타내줄 상태배열을 사용
• 초기 개미위치에서 방향이 다른 개미가 만나면 그 위치를 swap하는 방식
• 위를 t번만큼 반복