[BOJ] 21237. Clockwise Fence (greedy)

#. Problem

https://www.acmicpc.net/problem/21237

* The copyright in this matter is in acmicpc

 

#. Resolution Process

1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it

#. Solve

ㅇ 범위
    - 1 <= N <= 20
    - 4 <= String <= 100

ㅇ 정보
    - 동(E) 서(W) 남(S) 북(N) 1미터씩 이동

ㅇ 결과
    - 울타리 경로가 시계방향인지(CW) 반시계 방향인지(CCW) 출력

 

//

 

무식한 방법일 수 있지만..

N 과 input String 의 범위가 굉장히 너그럽다는 점을 이용하자.

 

fence 가 시계방향인지 반시계방향인지 구별하기 위해서는 바깥 모서리를 확인하면 된다.

...? 그렇다 말은 쉽다.

컴퓨터는 바깥 모서리만을 분별해내지 못하므로 결국 모든 모서리를 확인해야 할 것이다.

 

모서리는 양의 90도 혹은 음의 90도의 각도로 이루어 진다.

음의 90도로 이루어진 모서리의 개수와 양의 90도로 이루어진 모서리의 개수를 모두 구한 후, 

(

    음의 90도로 이루어진 모서리 : WS, SE, EN, NW

    양의 90도로 이루어진 모서리 : NE, ES, SW, WN

)

그 차이가 양수라면 시계 방향, 음수라면 반시계 방향일 것이다.

 

N은 최대 20

F(fence 문자열)는 최대 100

 

O(N * F) = O(20 * 100) = O(2000) 

이므로 충분히 해결할 수 있다.

#. Code

import java.io.*;
import java.util.*;
 
public class Main {
 
    FastScanner in;
    PrintWriter out;
 
    static int N;
    static Map<String, Integer> dirMap =  new HashMap<String, Integer>() {
        {
            put("NE", 1);
            put("ES", 1);
            put("SW", 1);
            put("WN", 1);
            put("WS", -1);
            put("SE", -1);
            put("EN", -1);
            put("NW", -1);
            put("EE", 0);
            put("WW", 0);
            put("SS", 0);
            put("NN", 0);
        }
    };
 
    void solve() {
        try {
            N = in.nextInt();
            for (int i = 0; i < N; i++) {
                int rst = 0;
                String fence = in.br.readLine();
                
                for (int j = 0; j < fence.length() ; j++) {
                    if (j == fence.length() - 1) { // 출발지점에 도착
                        rst += dirMap.get(Character.toString(fence.charAt(j)) + Character.toString(fence.charAt(0))).intValue();
                    } else { // fence 의 모서리
                        rst += dirMap.get(fence.substring(j, j+2)).intValue();
                    }
                }
                
                // 시계방향 모서리 개수 확인
                if (rst == 4) out.println("CW"); 
                else out.println("CCW");
            }
        } catch (Exception e) {
        }
    }
 
    /********************************** Input function **********************************/
    
    void run() {
        in = new FastScanner();
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
 
    public static void main(String[] args) {
        new Main().run();
    }
 
    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
 
        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(nextToken());
        }
 
        long nextLong() {
            return Long.parseLong(nextToken());
        }
 
        double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}