[구름 | Java Lv.2] 블록 게임 (자료구조)

문제

https://level.goorm.io/exam/191052/%EB%B8%94%EB%A1%9D-%EA%B2%8C%EC%9E%84/quiz/1

구름LEVEL

---

첫번째 코드 - 실패

package week7.baek.datastructure;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class BlockGame {
static Queue<Integer> score;
static List<Map<Integer, Integer>> map;

arduino
코드 복사
public static void search(int x, int y, int s){
    //들어갈 자리가 있는지 확인
    if(map.contains(new HashMap<Integer, Integer>(x,y))){
        //없으면 될 때까지 큐 비워주기
            while(map.get(map.size()-1) != new HashMap<Integer, Integer>(x,y)){
                map.remove(map.size()-1);
            }
            map.remove(map.size()-1);
    }

    //이제 queue와 map에 추가
    score.offer(s);
    map.add(new HashMap<>(x,y));
}

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = br.readLine();
    int N = Integer.parseInt(input);
    String D = br.readLine();
    String[] s = br.readLine() .split(" ");

    score = new LinkedList<>();
    map = new ArrayList<>();
    int x = 0; int y = 0;

    for (int i = 0; i <N; i++) {
        char c = D.charAt(i);
        switch (c) {
            case 'L':
                search(x-1, y, Integer.parseInt(s[i]));
                break;

            case 'R':
                search(x+1, y,  Integer.parseInt(s[i]));
                break;

            case 'U':
                search(x, y+1,  Integer.parseInt(s[i]));
                break;

            case 'D':
                search(x, y-1,  Integer.parseInt(s[i]));
                break;
        }
    }

    int count = 0;
    while(!score.isEmpty()){
        count += score.poll();
    }
    System.out.println(count);
}
}

 

비교하는데 에러가 나서 밑에처럼 같이 Node 클래스를 따로 만들어줘서 비교하도록 했다! 

static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Point point = (Point) obj;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

 

그렇게 했더니.. 대부분은 잘 출력되는 데 몇 가지 테스트 케이스들이 실패했다. 

 

두번째 코드 - 몇 가지 테스트 케이스 실패 (3, 9, 13, 14, 15) 

package week7.baek.datastructure;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class BlockGame {
    static Stack<Integer> score;
    static List<Point> map;

    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Point point = (Point) obj;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    public static void search(int x, int y, int s) {
        Point p = new Point(x, y);

        // 들어갈 자리가 있는지 확인
        while (map.contains(p)) {
            map.remove(map.size()-1);
            score.pop();
        }

        // 이제 queue와 map에 추가
        score.push(s);
        map.add(p);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int N = Integer.parseInt(input);
        String D = br.readLine();
        String[] s = br.readLine().split(" ");

        score = new Stack<>();
        map = new ArrayList<>();
        int x = 0, y = 0;
        score.add(1);

        for (int i = 0; i < N; i++) {
            char c = D.charAt(i);
            switch (c) {
                case 'L':
                    x -= 1;
                    break;
                case 'R':
                    x += 1;
                    break;
                case 'U':
                    y += 1;
                    break;
                case 'D':
                    y -= 1;
                    break;
            }
            search(x, y, Integer.parseInt(s[i]));
//            System.out.println(score);
        }

        int count = 0;
        while (!score.isEmpty()) {
            count += score.pop();
        }
        System.out.println(count);
    }
}

 

문제점 - 초기화 문제

 

(0,0)에서 1점을 가장 먼저 두고 시작하는데, score에 1점은 넣어줬으면서 (0,0)은 map에 표시하지 않았던 것

        int x = 0, y = 0;
        score.add(1);
        map.add(new Point(0,0));

 

그렇게 바꿔주니까~~~~~

 

 

최종 코드 

package week7.baek.datastructure;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class BlockGame {
    static Stack<Integer> score;
    static List<Point> map;

    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Point point = (Point) obj;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    public static void search(int x, int y, int s) {
        Point p = new Point(x, y);

        // 들어갈 자리가 있는지 확인
        while (map.contains(p)) {
            map.remove(map.size()-1);
            score.pop();
        }

        // 이제 queue와 map에 추가
        score.push(s);
        map.add(p);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int N = Integer.parseInt(input);
        String D = br.readLine();
        String[] s = br.readLine().split(" ");

        score = new Stack<>();
        map = new ArrayList<>();
        int x = 0, y = 0;
        score.add(1);
        map.add(new Point(0,0));

        for (int i = 0; i < N; i++) {
            char c = D.charAt(i);
            switch (c) {
                case 'L':
                    x -= 1;
                    break;
                case 'R':
                    x += 1;
                    break;
                case 'U':
                    y += 1;
                    break;
                case 'D':
                    y -= 1;
                    break;
            }
            search(x, y, Integer.parseInt(s[i]));
//            System.out.println(score);
        }

        int count = 0;
        while (!score.isEmpty()) {
            count += score.pop();
        }
        System.out.println(count);
    }
}