[백준 Baekjoon] 2641번 다각형그리기 - JAVA

문제 풀이

입력받은 표본 모양수열과 같은 모양수열을 찾는 문제이다.

같은 모양수열은 화살표의 출발 지점이 다른 경우와, 화살표 방향이 반대인 경우에 존재할 수 있다.

 

우선 화살표 방향이 반대인 경우를 만들어야 한다. 그 다음 정방향과 역방향 둘 모두에 대해 출발 지점이 다른 경우를 고려해야 한다.

정방향은 forward, 역방향은 reverse라 한다.

 

입력을 받을 때에 역방향은 1 -> 3, 2 -> 4, 3 -> 1, 4 -> 2로 방향을 변경해주며, 출발을 반대(insert idx 0)로 해줘야 한다.

 

출발지점이 다른경우는 swap 방식을 통해 0번 인덱스를 맨 뒤로 옮기는 방식으로 하였다.

같은 다각형 검사를 위해 정방향, 역방향에서의 모든 경우를 set에 추가한다.

 

모양수열을 입력받아 set에 존재하는지 검사한다.

출력시에 각 숫자 사이의 공백을 유의하자.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringBuilder forward = new StringBuilder();
        StringBuilder reverse = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            String t = st.nextToken();

            forward.append(t);
            reverse.insert(0, reverse(t));
        }

        Set<String> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            set.add(forward.toString());
            set.add(reverse.toString());

            forward.append(forward.charAt(0));
            reverse.append(reverse.charAt(0));

            forward.deleteCharAt(0);
            reverse.deleteCharAt(0);
        }

        int cnt = 0;
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            StringBuilder t = new StringBuilder();

            for (int j = 0; j < N; j++) {
                t.append(st.nextToken());
            }

            if (set.contains(t.toString())) {
                cnt++;
                for (int j = 0; j < N; j++) {
                    sb.append(t.charAt(j)).append(" ");
                }
                sb.append("\n");
            }
        }

        System.out.println(cnt);
        System.out.println(sb);
    }

    public static String reverse(String s) {
        switch (s) {
            case "1":
                return "3";
            case "2":
                return "4";
            case "3":
                return "1";
            default:
                return "2";
        }
    }
}