D-PHONE.pdf

대회때 못풀었던 문제를 다시 풀어보니 기분이 새롭다. 문제 해결책을 떠올리는데 한.. 2시간정도, 문제를 코딩하는데 1시간 반정도 걸렸다. ㅠㅠ

이 문제는 3X4 전화번호 자판에 볼팬으로 내가 누를 번호들을 순서대로 따라간다. 그럼 번호들을 따라갔기 때문에 선들이 몇개 나오는데 그 선들중 최소의 개수를 구하는 문제이다.

먼저 해결방법에 대해서 생각해 보았다.  시작점과 끝점 그리고 기울기를 사용하여 해결하는 문제로 다음과 같이 해결하였다.

•  내가 누른 좌표들과 기울기를 구하여 Set에 저장한다. Set에 저장하므로 자동으로 중복은 사라진다. 이제 시작점, 끝점, 기울기 데이터를 갖는 집합군이 생성되었다.
• 기울기가 0, -1, 1, 무한대(100)인것들에 따라서 String을 별도로 두었다.

              // 0, -1, 1, 100
              str = new String[]{"147*2580369#", "32615948#70*", "12435768*90#", "123456789*0#"};

• Set으로부터 하나씩 원소를 빼서 기울기에 해당하는 원소들을 지워가며 선의 최소개수를 센다.
• 위의 4가지 기울기를 빼고는 모드 unique하므로 +1을 한다.

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

//2007 Problem D : Phone

/**
 * 좌표 객체
 */
class Point {
        int x; // x좌표
        int y; // y좌표
       
        public Point(int x, int y) {
                this.x = x;
                this.y = y;
        }
}

/**
 * Entry 객체 (시작번호, 끝번호, 기울기)
 */
class EntryType implements Comparable<EntryType> {
        char start;
        char end;
        double inclination; // 기울기
       
        public EntryType(char start, char end, double inclination) {
                this.start = start;
                this.end = end;
                this.inclination = inclination;
        }

        public int compareTo(EntryType o) {
                if(start > o.start)   return 1;
                if(start < o.start)   return -1;
                if(end > o.end)       return 1;
                if(end < o.end)       return -1;
                return 0;
        }
}

public class D_2007 {
        Scanner in = new Scanner(System.in);
        Map<Character, Point> phoneMap; // 폰 번호당 좌표 매핑
        Set<EntryType> entrySet;                // entry들의 집합
        int resultCount;                               // 결과 개수
        String[] str;                                  // 기울기당 폰번호의 나열
               
        public D_2007() {
                int n = in.nextInt();
                initPhoneMap();
               
                int i;
                for(i=0 ; i<n ; i++) {
                        init();
                        start();
                }
        }
       
        /**
         * phoneMap을 초기화한다.
         */
        private void initPhoneMap() {
                phoneMap = new HashMap<Character, Point>();
                phoneMap.put('*', new Point(0,0));
                phoneMap.put('0', new Point(0,1));
                phoneMap.put('#', new Point(0,2));
                phoneMap.put('7', new Point(1,0));
                phoneMap.put('8', new Point(1,1));
                phoneMap.put('9', new Point(1,2));
                phoneMap.put('4', new Point(2,0));
                phoneMap.put('5', new Point(2,1));
                phoneMap.put('6', new Point(2,2));
                phoneMap.put('1', new Point(3,0));
                phoneMap.put('2', new Point(3,1));
                phoneMap.put('3', new Point(3,2));
        }
       
        /**
         * 변수를 초기화한다.
         */
        public void init() {
                resultCount = 0;
               
                // 0, -1, 1, 100
                str = new String[]{"147*2580369#", "32615948#70*", "12435768*90#", "123456789*0#"};
               
                String phoneNumber = in.next();
                int i;
               
                entrySet = new TreeSet<EntryType>();
                for(i=0 ; i<phoneNumber.length()-1 ; i++) {                  
                        char c1 = phoneNumber.charAt(i);
                        char c2 = phoneNumber.charAt(i+1);
                       
                        if(c1 == c2) continue;
                        if(c1 > c2) { char temp = c1; c1 = c2; c2 = temp; } // swap
                       
                        entrySet.add(new EntryType(c1, c2, calcInclination(phoneMap.get(c1),phoneMap.get(c2))));
                }
        }
       
        /**
         * 계산을 시작한다.
         */
        public void start() {
                EntryType entry;
               
                Iterator<EntryType> iter = entrySet.iterator();
                while(iter.hasNext()) {
                        entry = iter.next();
                        calculate(entry);
                }
               
                if(resultCount == 3) System.out.println("EXCELLENT");
                else if(resultCount == 4) System.out.println("GOOD");
                else System.out.println("BAD");
        }
       
        /**
         * p1과 p2를 사용하여 기울기를 계산한다.
         * @param p1 점1
         * @param p2 점2
         * @return
         */
        private double calcInclination(Point p1, Point p2) {
                if(p2.x - p1.x == 0)
                        return 100;
               
                double result = (double)(p2.y-p1.y)/(double)(p2.x-p1.x);
                if(result == -0)
                        result = 0;

                return result;  
        }
       
        /**
         * entry를 사용하여 선의 개수를 계산한다.
         * @param entry
         */
        private void calculate(EntryType entry) {
                int strIndex;
                if(entry.inclination == 0) strIndex = 0;
                else if(entry.inclination == -1) strIndex = 1;
                else if(entry.inclination == 1) strIndex = 2;
                else if(entry.inclination == 100) strIndex = 3;
                else {
                        resultCount++;
                        return;
                }
               
                int index1 = str[strIndex].indexOf(String.valueOf(entry.start));
                int index2 = str[strIndex].indexOf(String.valueOf(entry.end));
               
                if(index1 > index2) { int temp=index1; index1=index2; index2=temp; } // swap
               
                if(index1 == -1 && index2 == -1)
                        return;
                if(index1 == -1) {
                        str[strIndex] = str[strIndex].replaceAll(String.valueOf(str[strIndex].charAt(index2)), "");
                        return;
                }
                if(index2 == -1) {
                        str[strIndex] = str[strIndex].replaceAll(String.valueOf(str[strIndex].charAt(index1)), "");
                        return;
                }
                resultCount++;
                str[strIndex] = str[strIndex].substring(0, index1) + str[strIndex].substring(index2+1);
        }
       
        public static void main(String[] args) {
                new D_2007();
        }
}

이올린에 북마크하기