[백준] 12904 - A와 B(JAVA)

1. 소요시간 : 32분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 5
4. 문제 유형 : 그리디 알고리즘, 문자열, 구현
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/12904
8. 푼 날짜 : 2023.03.15

1. 사용한 자료구조 & 알고리즘

그리디 알고리즘을 사용했다.

2. 풀이과정

우선 맨 처음에는 길이가 999까지 인것을 보고 BFS 를 통해서 풀어보려고 했다. 그러니까 메모리 초과가 났다. 곰곰이 생각해보니 한 번 탐색할 때마다 2의 지수형태로 늘어나서 2^s 의 시간복잡도를 가지게되고 그 사이에 해시와 큐에 String 형이 계속 쌓이게 돼서 메모리 초과가 난 것이다. 그러니 이 문제는 BFS 가 아닌 그리디 알고리즘을 적용해야한다는 것을 알았다.

1. 만약 찾는 단어의 끝이 A 이면 A를 제거한다.
2. 단어의 끝이 A가 아니라면 단어를 뒤집고 맨 앞글자를 제거한다.
3. 찾는 단어의 길이가 원래의 단어의 길이와 같아진다면 둘을 비교한다. 같다면 1출력. 다르다면 0출력

3. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static HashSet<Integer> set=new HashSet<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();

		StringTokenizer st;



		String word=br.readLine();
		String find=br.readLine();

		
		while(find.length()!=word.length()) {
			if(find.charAt(find.length()-1)=='A')
				find=find.substring(0,find.length()-1);
			else {
				StringBuilder sbr=new StringBuilder(find);
				find=sbr.reverse().toString();
				find=find.substring(1,find.length());
				
			}
			
		}
		
		if(find.equals(word))
			System.out.println(1);
		else
			System.out.println(0);
		
		
	}

}

4. 결과

BFS 로 푼 코드는 메모리 초과가 난 것을 볼 수 있다.

5. 회고

그리디 알고리즘을 적용해야 한다는 것을 깨달은 후에 어떤 조건으로 단어를 찾아야 할지 모르겠어서 풀이를 참고했다. 당연한 말이지만 풀이를 보고나니 허무하기도 하고 3분만에 문제를 풀었다. 다음 번엔 나 혼자 조건을 생각해볼 수 있도록 하게 하자.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212