487-3279

From Progteam

Revision as of 05:18, 22 February 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by Eric.


487-3279
Problem Number 1002
Sorter: Uncategorized
Source: East Central North America 1999
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1002



487-3279 is problem number 1002 on the Peking University ACM site.


Contents

Problem Information

Problem Name: 487-3279
Problem Number on PKU: 1002
Synopsis: Converting various alpha-numeric telephone numbers to a standard form. Alphabets are mapped to digits from 1-9 with the exception of Q and Z. Then, only the duplicate numbers with more than 2 entries are displayed, followed by a frequency, in the order of increasing lexicographical order. Otherwise, the program should display "No duplicates."

Solver Information

Solver: Eric Hong
Date: February 05, 2008

General Strategy

  1. Using Scanner, take the input.
  2. Using switch() statement for each char, convert the alpha-numerals to numbers, ignoring all other characters.
  3. After 3 iterations, insert a dash.
  4. Store each number in Hashtable<String, Integer> with the number as a key and the frequency as a value.
  5. Enumerate entries of Hashtable to Vector.
  6. Sort them lexicographically using Collections.sort().
  7. Using foreach loop, display the numbers with frequency greater than or equal to 2.
  8. Otherwise, display "No duplicates."


Solution

import java.util.*;

public class Main
{

    public static Scanner in;
    public static Hashtable<String, Integer> hash = new Hashtable<String, Integer>();
 
    public static void main(String[] args)
    {
        in = new Scanner(System.in);

        doStuff();
    }

    public static void doStuff()
    {
        int N = in.nextInt();
	int noDupeCount = 0;

        for (int i = 0; i < N; i++)
	{
            solve();
        }

	Vector v = new Vector(hash.keySet());
	Collections.sort(v);

	for (Enumeration e = v.elements(); e.hasMoreElements();) 
	{
	    String key = (String) e.nextElement();
	    Integer val = (Integer) hash.get(key);

	    if (val > 1) 
                System.out.println(key + " " + val);
	    else
		++noDupeCount;

	    if (noDupeCount == hash.size())
		System.out.println ("No duplicates.");
        }
    }

    public static void solve()
    {
        String line = in.next();
        int len = line.length();
	String num = "";

	for (int i = 0; i < len; i++)
	{
	    char ch = line.charAt(i);

	    if (num.length() == 3)
	        num = num + '-';			

	    switch (ch)
	    {
	        case '0': case '1': case '2': case '3': case '4': 
		case '5': case '6': case '7': case '8': case '9':
		    num = num + ch;
		    break;
		case 'A': case 'B': case 'C':
		    num = num + '2';
		    break;
		case 'D': case 'E': case 'F':
		    num = num + '3';
		    break;
		case 'G': case 'H': case 'I':
		    num = num + '4';
		    break;
		case 'J': case 'K': case 'L':
		    num = num + '5';
		    break;
		case 'M': case 'N': case 'O':
		    num = num + '6';
		    break;
		case 'P': case 'R': case 'S':
		    num = num + '7';
		    break;
		case 'T': case 'U': case 'V':
		    num = num + '8';
		    break;
		case 'W': case 'X': case 'Y':
		    num = num + '9';
		    break;
		default:
		    continue;
		}
	}

	Integer count = 0;
	count = hash.get(num);
		
	if (count == null) 
	    hash.put(num, 1);
	else
	    hash.put(num, ++count);
    }
}


Additional Remarks

Memory: 11976K
Time: 4574MS

This solution may not be as efficient as it can be. If at all possible, can someone suggest how to make it more efficient?

Personal tools