BOJ - 1802 종이접기

Problem

---

Solve

종이를 접었을 때의 규칙은 종이가 접힌 중심점을 기준으로 좌우(i, length-1-i)는 서로 반대로 접혀있다는 것이다.

처음에는 중심점 하나만 가지고 양옆의 값들이 서로 다른지를 비교했었다.

하지만 중심점 하나만 가지고 비교를 한다면 1110000(동호의 조건을 만족하지 못함)인 경우를 잡지 못한다.

그렇기 때문에 중심점을 왼쪽이든 오른쪽이든 분할하면서 분할된 부분의 중심점을 기준으로 양옆의 값들을 비교해 나가야한다.

---

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class 종이접기 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		StringBuilder sb = new StringBuilder();
		for(int i=0;i<T;i++){
			String rule = br.readLine();
			validation(rule, sb);
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static public void validation(String rule, StringBuilder sb){

		boolean isCorrect = true;

		//비교할 범위 초기값을 문자열의 크기로 설정한다.
		int len = rule.length();
        //중심점을 범위의 가운데로 설정한다.
		int idx = len/2;

		while(idx!=0){
        	//중심점기준으로 양옆을 비교해서 값이 같다면 NO를 반환한다.
			for(int i=0,j=len-1;i<idx;i++,j--){
				if(rule.charAt(i) == rule.charAt(j)){
					isCorrect = false;
					break;
				}
			}

			if(!isCorrect) break;

			//해당 중심점이 조건을 만족한다면 왼쪽 부분으로 분할하여 비교한다.
			len /= 2;
			idx /= 2;
		}

		if(isCorrect){
			sb.append("YES");
		}else{
			sb.append("NO");
		}
		sb.append("\n");
	}
}

---

Result

---

Reference

https://velog.io/@ehdcks3421/%EB%B0%B1%EC%A4%80-%EC%A2%85%EC%9D%B4-%EC%A0%91%EA%B8%B0-1802