짝패

package com.sarojaba.algospot;
import java.util.Scanner;
/**
    * [http://algospot.com/judge/problem/read/BOGGLE](http://algospot.com/judge/problem/read/BOGGLE)
    * 
    * @author 준혁
    * 
    */
public class BOGGLE {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // test case
        int C = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < C; i++) {
            // board
            Board b = new Board(5, 5);
            for (int j = 0; j < 5; j++) {
                String line = scanner.nextLine();
                for (int k = 0; k < 5; k++) {
                    b.set(j, k, line.charAt(k));
                }
            }
            // words
            int N = Integer.parseInt(scanner.nextLine());
            for (int j = 0; j < N; j++) {
                String line = scanner.nextLine();
                String yn = b.search(line) ? "YES" : "NO";
                System.out.println(String.format("%s %s", line, yn));
            }
        }
        scanner.close();
    }
}
/**
    * implementation of boggle board
    * 
    * @author 준혁
    * 
    */
class Board {
    /**
        * board
        */
    private char[][] board;
    /**
        * constructor
        * 
        * @param r
        *            row
        * @param c
        *            col
        */
    public Board(int r, int c) {
        board = new char[r][c];
    }
    /**
        * setter
        * 
        * @param r
        *            index of row
        * @param c
        *            index of column
        * @param value
        */
    public void set(int r, int c, char value) {
        board[r][c] = value;
    }
    /**
        * exhaustive search
        * 
        * @param word
        * @return match
        */
    public boolean search(String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (search(i, j, word)) {
                    return true;
                }
            }
        }
        return false;
    }
    /**
        * 
        * @param r
        *            row
        * @param c
        *            col
        * @param word
        * @return match
        */
    private boolean search(int r, int c, String word) {
        // match
        if (word.isEmpty()) {
            return true;
        }
        // out of bound
        if (r < 0 || r > board.length - 1) {
            return false;
        }
        if (c < 0 || c > board[r].length - 1) {
            return false;
        }
        // not match
        if (board[r][c] != word.charAt(0)) {
            return false;
        }
        // recursive search
        String w = word.substring(1);
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if(i == 0 && j == 0) {
                    continue;
                }
                if (search(r + i, c + j, w)) {
                    return true;
                }
            }
        }
        return false;
    }
}

Comment

샘플 케이스만 만족시킨 답안이다. 완전 탐색이라 시간 초과에 걸린다.

Flight

2013-02-13

Movie

불가항력의 위급 상황에서 기지를 발휘하여 기적적으로 대부분의 승객을 구한 비행사. 하지만 그는 비행 전 음주를 한 사실이 발각되었다.

우리는 그를 영웅이라고 해야할까? 죄인이라고 해야할까?

진실과 거짓이 사이에서 갈등하는 주인공의 모습이 잘 묘사된 영화이다.

7번방의 선물

2013-02-12

Movie

어린 아이의 지능을 가진 아버지가 누명을 쓰고, 교도소에서 벌어지는 이야기를 담았다.

아버지가 딸을 애타게 부르는 장면에서 눈물이 났다. 가슴 찡한 부성애를 느낄 수 있었다.

정리 못하는 정리베

2013-02-04

ProgrammingAlgorithm

Algorithm, Programming

문제

알고스팟 새싹 콘테스트를 준비하느라 정신이 없던 정리베는, 버벅거리는 컴퓨터의 원인이 가득 찬 하드디스크라는 것을 알게 되었습니다. 하드의 파일들을 확인해본 후, 정리베는 두 가지 사실을 발견했습니다.

하드 용량의 대부분을 MP3파일이 차지한다.
MP3파일 중에 중복되는 파일이 존재한다.

따라서 정리베는 MP3파일들을 정리하여 하드 공간을 어느 정도 더 확보할 수 있는지 알아보려고 합니다.

모든 MP3파일의 이름은 다음과 같은 형식으로 쓰여집니다. 이를 통해 MP3파일에 해당하는 아티스트 명과 곡의 제목을 알 수 있으며, 아티스트 명과 곡의 제목이 같을 경우 이를 동일한 곡으로 간주합니다.

(트랙 번호)(아티스트 명)(곡 제목).mp3
(트랙 번호). (아티스트 명) - (곡 제목).mp3
(아티스트 명) - (곡 제목).mp3
(아티스트 명)_(곡 제목).mp3

(트랙 번호)는 0부터 9까지의 숫자 조합으로 이루어지고, (아티스트 명)과 (곡 제목)은 공백, 숫자, 영문자 그리고 여는 괄호 ’(‘와 닫는 괄호 ’)’ 문자의 조합으로 이뤄집니다. 모든 파일은 위 4가지 중 한 가지 형식으로만 해석될 수 있습니다. (아티스트 명)과 (곡 제목) 비교시에 알파벳 대소문자는 구분하지 않습니다.

입력

입력의 첫 줄에는 곡의 개수 N이 입력됩니다. 그 후 N줄에 각각 파일의 경로가 주어지는데, 형식은 다음과 같습니다.

(파일명)
/(폴더1)/(폴더2)/…/(파일명)

2번째 형식의 경우 중첩된 폴더 구조에 위치한 파일을 의미합니다.

출력

한 줄에 중복을 모두 제외한 곡의 개수를 출력합니다.

입력 파일

A1.txt A2.txt

제약 조건

예제 입력

9
Above and Beyond Feat Zoe Johnston - Alchemy (Above and Beyond Club Mix).mp3
Coldplay - Every Teardrop Is A Waterfall (Swedish House Mafia Remix).mp3
/Andrew Rayel/Armin Van Buuren - Serenity (Andrew Rayel Aether Remix).mp3
Armin Van Buuren - Serenity (Andrew Rayel Aether Remix).mp3
/Above and Beyond Feat Zoe Johnston - Alchemy/Above and Beyond Feat Zoe Johnston - Alchemy (Above and Beyond Club Mix).mp3
Nuera - Transatlantic 2009 (Original Mix).mp3
/Discograph/Nuera/Nuera - Transatlantic 2011 (Original Mix).mp3
/Alex M O R P H - Eternal Flame (Alex M O R P H s Reach Out For The Stars Mix).mp3
01. Armin Van Buuren Feat Fiora - Waiting For The Night (Radio Edit).mp3

예제 출력

Source Code

package com.sarojaba.algospot.newbie;
import java.io.File;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class A {
    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(new File("a.txt"));
        int N = scanner.nextInt();
        String[] lines = new String[N];
        for (int i = 0; i < N; i++) {
            lines[i] = scanner.nextLine();
        }
        System.out.println(solve(lines));
        scanner.close();
    }
    public static int solve(String[] lines) {
        Set mp3s = new HashSet<>();
        Pattern pattern = Pattern.compile("(?:/.*)*/(.*)");
        for (String l : lines) {
            Matcher matcher = pattern.matcher(l);
            String f = l;
            if (matcher.matches()) {
                f = matcher.group(1);
            }
            mp3s.add(MP3.parse(f));
        }
        return mp3s.size();
    }
}
class MP3 {
    private String artist;
    private String song;
    private int track;
    public MP3(String artist, String song) {
        this(artist, song, 0);
    }
    public MP3(String artist, String song, int track) {
        this.artist = artist;
        this.song = song;
        this.track = track;
    }
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof MP3)) {
            return false;
        }
        MP3 mp3 = (MP3) obj;
        if (!artist.equalsIgnoreCase(mp3.artist)) {
            return false;
        }
        if (!song.equalsIgnoreCase(mp3.song)) {
            return false;
        }
        return true;
    }
    @Override
    public int hashCode() {
        return (artist.toLowerCase().hashCode() + song.toLowerCase().hashCode())
                % Integer.MAX_VALUE;
    }
    @Override
    public String toString() {
        return String.format("{artist: %s, song: %s}", artist, song);
    }
    public static MP3 parse(String file) {
        Pattern[] patterns = new Pattern[2];
        patterns[0] = Pattern.compile("(.*)_(.*)_(.*)\\.mp3");
        patterns[1] = Pattern.compile("(.*)\\. (.*) - (.*)\\.mp3");
        for (Pattern p : patterns) {
            Matcher matcher = p.matcher(file);
            if (matcher.matches()) {
                try {
                    int track = Integer.parseInt(matcher.group(1));
                    String artist = matcher.group(2);
                    String song = matcher.group(3);
                    return new MP3(artist, song, track);
                } catch (NumberFormatException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
        }
        patterns[0] = Pattern.compile("(.*) - (.*)\\.mp3");
        patterns[1] = Pattern.compile("(.*)_(.*)\\.mp3");
        for (Pattern p : patterns) {
            Matcher matcher = p.matcher(file);
            if (matcher.matches()) {
                String artist = matcher.group(1);
                String song = matcher.group(2);
                return new MP3(artist, song);
            }
        }
        return null;
    }
}