백준 3048. 개미 :: 돼지개발자

백준 3048. 개미 (https://www.acmicpc.net/problem/3048)

---

"단순 시뮬레이션"

해당 문제는 단순 시뮬레이션 문제인 것 같다. 실제로 해보는 것이 답. 근데 어떻게 구현 할 것인가. 

단순 시뮬레이션을 돌려야 하는 것인가?

어떤 수식 수식이나 그리디하게 풀 수 있는 방법이 있나? 

잘 모르겠다. 무식하게 다 해보자. 나는 구현에 ArrayList 를 사용했다. 두 그룹을 ArrayList에 넣고 반대 방향의 개미를 만나면 위치를 서로 바꿔주었다. 그리고 실제 개미들이 모두 지나갔는데도 T 값이 증가할 것을 염려하여 시뮬레이션 이전에 T 값을 비교하여, 모두 지나간 시간보다 더 큰 T값이 주어지면 그냥 문자열을 붙여서 출력하고 끝냈다.

아 그리고 매번 System.out.println으로 출력하는 것은 System call 을 이용하기 때문에 느리다. 그렇기 때문에 다량의 데이터를 출력할 일이 있으면 Stringbuffer 를 이용해 System call 의 횟수를 줄이자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static int N1;
    static int N2;
    static int T;
    static ArrayList<Node> list = new ArrayList<>();
    static StringBuffer sb = new StringBuffer();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N1 = Integer.parseInt(st.nextToken());
        N2 = Integer.parseInt(st.nextToken());
        
        char[] temp1 = br.readLine().toCharArray();
        
        for (int i = N1-1; i >= 0 ; i--) {
            list.add(new Node(temp1[i], true));
        }
        char[] temp2 = br.readLine().toCharArray();
        
        for (int i = 0; i < N2; i++) {
            list.add(new Node(temp2[i], false));
        }
        
        T = Integer.parseInt(br.readLine());
        
        // 시뮬레이션 이전에 체크
        if(N2 + N1 -1 <= T) {
            for (int i = 0; i < temp2.length; i++) {
                sb.append(temp2[i]);
            }
            
            for (int i = temp1.length-1; i >= 0; i--) {
                sb.append(temp1[i]);
            }
            System.out.println(sb.toString());
            return ;
        }
        
        while(T-- >0) {
            for (int i = 0; i < list.size()-1; i++) {
                Node cur = list.get(i);
                Node next = list.get(i+1);
                
                if(!cur.team || cur.team == next.team) continue;
                
                list.set(i, next);
                list.set(i+1, cur);
                i++;
            }
        }
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i).c);
        }
        System.out.println(sb.toString());    
    }
}
 
class Node {
    char c;
    boolean team;
    
    Node(char c, boolean team) {
        this.c = c;
        this.team = team;
    }
}