QUADTREE 문제 도움바랍니다.

  • greatim
    greatim
    public class QuadTree {
    
        public static void main(String[] args) throws InterruptedException, NumberFormatException, IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
            int testcase = Integer.parseInt(br.readLine().trim());
    
            for (int t = 0; t < testcase; t++) {
                String str = new String(br.readLine());
    
                QTree top = new QTree();
                int readsize = top.read(str, 0);
                if (readsize != str.length()) {
                    Thread.sleep(3000);
                }
    
                System.out.println(top.reverse_write());
            }
        }
    }
    
    class QTree {
        QTree leftTop;
        QTree rightTop;
        QTree leftBottom;
        QTree rightBottom;
    
        char color = 0;
    
        int read(String str, int index) throws InterruptedException {
            char cur = str.charAt(index);
            index++;
    
            if (cur == 'x') {
                leftTop = new QTree();
                rightTop = new QTree();
                leftBottom = new QTree();
                rightBottom = new QTree();
    
                index = leftTop.read(str, index);
                index = rightTop.read(str, index);
                index = leftBottom.read(str, index);
                index = rightBottom.read(str, index);
            } else {
                this.color = cur;
                if (cur != 'b' && cur != 'w') {
                    Thread.sleep(3000);
                }
            }
    
            return index;
        }
    
        String reverse_write() {
            if (this.color != 0) {
                return this.color + "";
            } else {
                String[] rqt = new String[4];
    
                rqt[0] = leftTop.reverse_write();
                rqt[1] = rightTop.reverse_write();
                rqt[2] = leftBottom.reverse_write();
                rqt[3] = rightBottom.reverse_write();
    
                return 'x' + rqt[2] + rqt[3] + rqt[0] + rqt[1]; 
            }
        }
    }
    

    위와 같이 풀어서 정답이 나오긴 했습니다. 그런데 처음에 풀었던 방식에서는 계속 오답이 나오더군요. 근데 그 오답이 나오는 이유를 모르겠습니다.
    처음 풀었던 방식은 위 코드와 다 똑같고 reverse_write() 함수만 다릅니다.

        int reverse_write(char[] buf, int index) {
            if (this.color != 0) {
                buf[index++] = this.color;
            } else {
                buf[index++] = 'x';
    
                index = leftBottom.reverse_write(buf, index);
                index = rightBottom.reverse_write(buf, index);
                index = leftTop.reverse_write(buf, index);
                index = rightTop.reverse_write(buf, index);
            }
    
            return index;
        }
    

    보시는 바와 같이 String 으로 리턴하는 것을 char[] 버퍼로 받게 바꾼 것 밖에 없는데 왜 정답이 안나오는지 모르겠습니다. 예제로 나온 4개의 테스트 케이스는 정상적으로 나온 것으로 봐서는 로직상 문제는 없어 보이는데 왜 오답이 나올까요?


    7년 전
1개의 댓글이 있습니다.
  • greatim
    greatim

    self 답변 입니다.

    char[] buffer 를 넉넉하게 잡는다고 잡은게 문제가 되었네요. 결국 필요없는 문자까지 찍힌 모양입니다.
    buffer 를 딱 필요한 만큼만 할당하니 통과했습니다.


    7년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.