[백준, Java] 17609번, 회문(투 포인터)

문제 링크

17609번: 회문

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 일반적인 문자열이 주어질 때 회문/유사회문/일반 문자열인지 판단해야 한다.

2. 한 문자를 삭제하여 회문을 만들 수 있으면 유사 회문입니다.

3. 회문이면 0, 유사회문이면 1, 그 외에는 2를 결과로 출력해야 한다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 문자열이 회문/유사 회문/일반 문자열인지 탐색합니다.

 

3. 탐색으로 얻은 회문의 대한 결과를 출력합니다.

 

회문 탐색하기(투 포인터)

 

회문은 앞과 뒤를 기준으로 동일한 값인지 확인해야 합니다.

 

 

또한, 1개의 글자라도 다른 값이 존재하다면 회문은 될 수 없으며 유사 회문이 될 가능성만 존재합니다.

 

문자열이 회문인지 탐색할 때 발견되는 경우의 수는 아래와 같습니다.

 

1. 문자열이 회문인 경우

 

2. 앞 부분의 문자 1개를 지우면 유사 회문이 된 경우

 

3. 뒷 부분의 문자 1개를 지우면 유사 회문이 된 경우

 

4. 다른 부분이 2개 이상으로 회문/유사 회문이 되지 않고 일반 문자열인 경우

 

 

※ 앞/뒷 부분의 글자가 지웠을 때가 나누어지는 이유

 

아래 2가지 부분을 비교하면 abbaa는 4번째 문자(a)을 지워야만 유사 회문이 가능하며, aabba는 2번째 문자를 지워야 유사 회문이 가능하기 때문에, 앞/뒤 부분의 대한 두 경우를 모두 확인해야 합니다

 

 

a

b

b

a

a

 

a

a

b

b

a

 

 

이제는 회문에 대한 검증을 어떻게 할 것인가???

 

회문은 앞의 시작과 뒷의 시작이 같아야 하는 값으로 순차적으로 가운데로 좁혀지면서 같은 값이 유지되는 것인지 확인해야 한다.

 

해당 앞과 뒤의 인덱스 포인터를 두고 탐색하는 알고리즘 = 투 포인터를 사용하라는 명제이다.

 

a	b	a	b	a
start				end

 

1. start(a) == end(a) : 회문의 조건에 만족한다.

start  = start + 1

end = end - 1

 

2. start(a) != end(?) : 회문의 조건에 불만족한다.

 

1). 앞 부분의 문자를 삭제한다.(start + 1 == end)

start  = start + 2

end = end - 1

 

2). 뒷 부분의 삭제를 삭제한다.(start == end - 1)

start = start + 1

end = end - 2

 

위 2가지를 이용해서 투 포인터로 탐색하였을 때 회문, 유사 회문, 일반 문자열인지 탐색을 진행하여 결과로 출력합니다.

 

※ 예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

문자열 : summuus

 

※ 예제 입력 1번의 summus의 대한 풀이 과정만 설명드릴 예정입니다.

 

2. 문자열이 회문/유사 회문/일반 문자열인지 탐색합니다.

 

문자열 : summuus

 

s	u	m	m	u	u	s
start						end

 

start(s) == end(s)

start = start + 1

end = end - 1

 

s	u	m	m	u	u	s
	start				end

 

start(u) == end(u)

start = start + 1

end = end - 1

 

 

s	u	m	m	u	u	s
		start		end

 

start(m) != end(u)

1). 앞 부분 삭제 : start + 1(m) != end(u) ▶︎ 삭제해도 회문이 유지되지 않기 때문에 X

2). 뒷 부분 삭제 : start(m) == end - 1(m) ▶︎ 삭제하면 회문 유지!

start = start + 2end = end - 1

 

 

투 포인터의 인덱스가 교차되었으므로 탐색 종료!

 

 

3. 탐색으로 얻은 회문의 대한 결과를 출력합니다.

 

summuus에서 summuus의 5번째의 u을 삭제하면 유사 회문이 됩니다

 

해당 문자열은 유사 회문으로써 1을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• N개의 문자열에 대해서 각각 회문, 유사 회문, 일반 문자열인지 투 포인터를 이용한 4가지 경우를 기반으로 탐색합니다.
• 탐색을 통해 얻은 문자열의 결과를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
  //회문 투 포인터 관련 클래스
  static class Info{
    int start;
    int end;
    int result;

    public Info(int start, int end, int result) {
      this.start = start;
      this.end = end;
      this.result = result;
    }
  }
  public static void main(String[] args) throws IOException {
    //입력값 처리하는 BufferedReader
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //결과값 출력하는 BufferedWriter
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int n = Integer.parseInt(br.readLine());
    //n개의 문자열에 대한 회문, 유사 회문, 일반 문자열에 대해서 탐색합니다.
    for (int i = 0; i < n; i++) {
      char[] word = br.readLine().toCharArray();
      Queue<Info> queue = new ArrayDeque<>();
      int len = word.length;
      //투 포인터 정의
      int start = 0;
      int end = len - 1;
      int result = 2;
      queue.add(new Info(start, end, 0));
      //회문 탐색 진행!
      while (!queue.isEmpty()) {
        Info cur = queue.poll();
        //현재 경우 회문 탐색 종료
        if(cur.start > cur.end){
          result = Math.min(result, cur.result);
          continue;
        }
        //회문 유지
        if (word[cur.start] == word[cur.end]) {
          queue.add(new Info(cur.start+1, cur.end-1, cur.result));
        } else {
          //이미 1번 삭제한 경우
          if(cur.result == 1){
            continue;
          }
          //앞 부분을 삭제할 때
          if (word[cur.start + 1] == word[cur.end]) {
            queue.add(new Info(cur.start+2, cur.end-1, 1));
          }
          //뒷 부분을 삭제할 때
          if (word[cur.start] == word[cur.end - 1]) {
            queue.add(new Info(cur.start+1, cur.end-2, 1));
          }
        }
      }
      //회문에 대한 결과 BufferedWriter 저장
      bw.write(String.valueOf(result));
      bw.newLine();
    }
    bw.flush();		//결과 출력
    bw.close();
    br.close();
  }
}