[SW Expert] [모의 SW 역량테스트] 5648번 원자 소멸 시뮬레이션 (Java)

SW Expert [모의 SW 역량테스트] 5648번 원자 소멸 시뮬레이션 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRFInKex8DFAUo

 

 

모의 SW 역량테스트 중에 가장 낮은 정답률을 자랑하는 원자 소멸 시뮬레이션이다.

17%의 정답률 치고는 나름 할만했던 문제라고 생각한다.

 

가장 먼저 생각한 점이 '프로그램은 언제 종료되는가?'였다.

제약 사항 중에 원자들이 움직일 수 있는 좌표의 범위의 제한은 없다고 한다.

처음 생각했을 때, 좌표가 무한정으로 움직인다면 무한루프에 빠질 것 같았다.

하지만 조금 더 생각해보니 입력으로 주어지는 좌표는 -1000부터 1000 사이의 값이고,

그 밖으로 넘어가면 원자들이 충돌할 수가 없으니 범위를 넘어가면 종료를 해야겠다고 생각했다.

 

배열을 사용하려면 음수의 인덱스는 없으므로 입력을 받을 때 1000씩 더해주었고,

1.5초 후에도 원자가 충돌할 수 있으므로 2배까지 해서 입력을 받았다.

 

원자들은 Atom이라는 클래스를 만든 뒤 LinkedList에 담아주었다.

원자들이 움직일 때 가장 중요한 점은 원자들이 충돌할 때 처리를 어떻게 해줘야 하는가였다.

길이 4001짜리 2차원 int 배열을 만든 뒤 원자의 위치에 맞는 곳에 value들을 저장했다.

value들을 먼저 저장한 뒤에 원자들 하나씩 탐색하며 원자의 value와 배열 안에 있는 값이 다르다면 list에서 제거해주었다.

2개 이상의 value가 배열에 저장되어야 원자의 value와 달라질 수 있다.

 

한 가지 주의할 점이,

길이가 4001짜리 2차원 배열을 선언하기 때문에 메모리를 많이 잡아먹게 된다.

50개의 테스트케이스를 통과해야 하는데 매번 배열을 선언해주면 메모리 초과가 뜨게 된다.

따라서 전역변수로 1번 선언한 뒤, value 값을 담아주기 전에 0으로 초기화하며 사용했다.

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    private static int n, answer;
    private static Atom atom;
    private static Iterator<Atom> itr;
    private static int[][] check = new int[4001][4001];
    private static int[] dx = {0, 0, -1, 1};
    private static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            n = Integer.parseInt(br.readLine());
            answer = 0;
            LinkedList<Atom> atoms = new LinkedList<>();

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());

                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken());
                int value = Integer.parseInt(st.nextToken());

                atoms.add(new Atom(2 * (x + 1000), 2 * (y + 1000), dir, value));
            }

            solution(atoms);
            System.out.println("#" + t + " " + answer);
        }
    }

    private static void solution(LinkedList<Atom> atoms) {
        while (atoms.size() != 0) {
            itr = atoms.iterator();
            while(itr.hasNext()){
                atom = itr.next();
                atom.move(); // 원자 이동
                if(!isValid(atom)) itr.remove(); // 맵 밖으로 나갔으면 삭제
            }
            collision(atoms); // 충돌 처리
        }
    }

    private static void collision(LinkedList<Atom> atoms) {
        for (Atom atom : atoms) { // 0으로 초기화
            check[atom.x][atom.y] = 0;
        }
        for (Atom atom : atoms) { // value 더해줌
            check[atom.x][atom.y] += atom.value;
        }

        itr = atoms.iterator();
        while (itr.hasNext()) {
            atom = itr.next(); 
            if (check[atom.x][atom.y] != atom.value) { // 2개 이상인 원자 삭제 및 값 더해줌
                answer += atom.value;
                itr.remove();
            }
        }
    }

    private static boolean isValid(Atom atom) {
        if (atom.x < 0 || atom.y < 0 || atom.x > 4000 || atom.y > 4000) return false;
        return true;
    }

    static class Atom {
        int x, y;
        int dir;
        int value;

        public Atom(int x, int y, int dir, int value) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.value = value;
        }

        public void move() {
            this.x = x + dx[dir];
            this.y = y + dy[dir];
        }
    }
}