백준 문자열 검색 주요 문제 모음

백준 1543. 문서 검색  (문자열 검색)

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

들어간 개념 1. indexOf()

 

 

indexOf(String str)

 

Hello의 위치를 찾아 줘!

indexOf("Hello");

 

World의 위치를 찾아 줘!

indexOf("World");

 

 

즉, String 형태로 넣어주면 문자열의 시작인 첫번째 글자의 위치를 찾아주게 된다.

 

 

WWorld 이렇게 겹치는 경우 World의 index를 찾는다면?

 

답은

 

뒤에 있는것을 기준으로 나온다

 

 

 

시도했다가 실패했던 것

 

replaceFirst 메소드를 사용하니깐 단순히 찾으려는 문자열 'aba' 제외하고, 남은 문자열은 그대로 출력해주었다.

-> 원래는 'aba'를 찾았으면 그 다음 index부터 다시 계산해야함

 

 

 

substring 메소드를 이용해서 구했다.

들어간 개념 2. String substring(int beginIndex, int endIndex)

import java.util.Scanner;

public class Q1543 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String doc = sc.nextLine(); // 전체 문서
		String findStr = sc.nextLine(); // 찾으려는 문자열
		int total = 0; 		
		
		for(; doc.indexOf(findStr) > -1; total ++) {		
			doc = doc.substring(doc.indexOf(findStr) + findStr.length(), doc.length());
		}				
		System.out.println(total);
	}
}

 

이 와중에 문자열 입력 next(); 로 받으니깐 안됐음.

들어간 개념 3. Scanner 클래스에서 nextLine() 과 next()의 차이점

next()공백을 기준으로 입력을 받는다. 즉, 띄어쓰기(=\\s)을 기준으로 입력을 받는다.
nextLine()한 라인을 기준으로 입력을 받는다. 즉, 개행문자(=줄넘김)(=\n)을 기준으로 입력을 받는다.

 

 

---

백준 2966. 찍기 (Brute Force)

들어간 개념 1. 반복 메소드

java 1.5이상에서 String repeated = new String(new char[n]).replace("\0", s); 이런 식으로 하면 된다.

n은 문자열 s를 몇 번 반복할건지에 대한 변수이다.

아무것도 import할 필요 없음!

package Boj;

import java.util.Scanner;
// 2019-12-17
public class Q2966Test {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 문제의 수 (1<=n<=100)

		String ans1[] = new String[101]; // 상근이 정답 100/3 = 1
		String ans2[] = new String[101]; // 창영이 정답 100/4 = 0
		String ans3[] = new String[101]; // 현진이 정답 100/6 = 4
		// A B C
		// B A B C
		// C C A A B B
		
		// 1. 상근이,창영이,현진이의 정답패턴에 맞게 배열 String 생성
		String repeated1 = new String(new char[99]).replace("\0", "ABC");
		repeated1 = repeated1.concat("A");
		ans1 = repeated1.split(""); // 배열에 각자의 정답을 전부 담음
		String repeated2 = new String(new char[25]).replace("\0", "BABC");
		ans2 = repeated2.split("");
		String repeated3 = new String(new char[16]).replace("\0", "CCAABB");
		repeated3 = repeated3.concat("CCAA");
		ans3 = repeated3.split("");

		// 2. 문제의 정답 입력받음 (ex. AAAABBBBB)
		String str = sc.next().toUpperCase();
		str = str.substring(0,n);
		String answer[] = new String[101];
		answer = str.split(""); // 정답 문자열도 배열에 넣음
		
		// 3. 문제 정답과 3명의 정답을 비교하여 맞은 갯수 체크
		int i = 0;
		int cnt1 =0; int cnt2=0; int cnt3=0;
		while (i < n) {
			if (answer[i].equals(ans1[i]))	// 상근이 정답 (Adrian)
				cnt1 ++;
			if (answer[i].equals(ans2[i])) // 창영이 정답 (Bruno)
				cnt2 ++;
			if (answer[i].equals(ans3[i])) // 현진이 정답 (Goran)
				cnt3 ++;
			i++;
		}
		
		// 4. 가장 많은 문제를 맞춘 갯수를 변수 max 에다 집어넣음
		int max=0;
		int[] arr = {cnt1,cnt2,cnt3};
		for(i=0; i<3; i++) {
			if(max<arr[i]) {
				max = arr[i];
			}
		}
		System.out.println(max); // 가장 많은 문제를 맞춘 사람이 몇 문제 맞췄는지 출력
		
		// 5. 최다정답갯수 max와 같은 숫자가 있는 배열 원소를 찾아 Ardian - Bruno - Goran 순서대로 출력
		for (i=0; i<3; i++) {
			if(arr[i]==max) {
				switch(i) {
				case 0:
					System.out.println("Adrian");
					break;
				case 1:
					System.out.println("Bruno");
					break;
				case 2:
					System.out.println("Goran");
					break;
				}
			}
		}
	}
}

 

 

그러다 구글링 한 더 나은 것 같은 방법? (c++)

이중 for문을 써서 약간의 노가다성을 줄이긴 함 

출처 - https://happysuzy.tistory.com/105

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

char Adrian[3] = { 'A','B','C' };
char Bruno[4] = { 'B', 'A', 'B', 'C'};
char Goran[6] = { 'C', 'C', 'A', 'A', 'B', 'B' };

char input[102];

int n;

typedef struct Data
{	int score;
	string name;
}Data;

Data person[3];

int main()

{
	person[0].name = "Adrian";

	person[1].name = "Bruno";

	person[2].name = "Goran";

	cin >> n;

	for (int i = 0; i < n; i++)

		cin >> input[i];	

	for (int i = 0; i < n; i++)

	{
		for (int j = 0; j < 3; j++)

		{

			if (i + j < n&&input[i + j] == Adrian[j])

				person[0].score++;

		}

		i += 2;

	}

	for (int i = 0; i < n; i++)

	{
		for (int j = 0; j < 4; j++)

		{

			if (i + j < n&&input[i + j] == Bruno[j])

				person[1].score++;
		}

		i += 3;
	}

	for (int i = 0; i < n; i++)

	{
		for (int j = 0; j < 6; j++)

		{

			if (i + j < n&&input[i + j] == Goran[j])

				person[2].score++;
		}

		i += 5;
	}	

	int M = (max(max(person[0].score, person[1].score), person[2].score));

	cout << M << endl;

	for (int i = 0; i < 3; i++)

		if (M == person[i].score)

			cout<<person[i].name<<endl;

}

 

---

백준 1182. 부분 수열의 합

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

1182번: 부분수열의 합

모든 경우를 다 실행해 보는 완전탐색 문제다.

재귀호출을 이용해서 풀면된다.

재귀 호출 시 2가지 경우를 나눠서 호출하는데,

1. 현재 방문지역(index)의 값을 더해준 뒤 다음을 호출

2. 현재 방문지역의 값을 더해주지 않고 다음을 호출

원소의 개수가 3개인 배열을 예로 들어 그림으로 표현해 보면

출처 -  https://2744m.tistory.com /entry/1182 

 

/*1182번 부분수열의 합*/
#include <iostream>
using namespace std;
int N, S, cnt;
int arr[20];

void Search(int index,int sum) {
	int temp = sum + arr[index];
	if (index >= N) return;
	if (temp == S) cnt++;
	Search(index + 1, sum);//현 인덱스의 값을 더하지 않았을 때
	Search(index + 1, temp);//현 인덱스의 값을 더했을 떄
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> S;
	for (int i = 0; i < N; i++) cin >> arr[i];
	Search(0, 0);
	cout << cnt;
}

 

index와 sum을 매개변수로 완전탐색을 한 것이다

 

---

백준 2902. KMP는 왜 KMP일까?

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

2902번: KMP는 왜 KMP일까?

 

 

* String, StringBuffer, StringBuilder 차이점과 장단점.

 

String, StringBuffer, StringBuilder.. 모두 문자열을 저장하고, 관리하는 클래스입니다.

굳이 여러가지를 만들어놓은 이유는 무엇일까요.

 

1) String

String은 immutable(불변) 합니다. 즉, String 객체는 한번 생성되면 할당된 메모리 공간이 변하지 않습니다.

+ 연산자 또는 concat 메서드를 통해 기존에 생성된 String 클래스 객체 문자열에 다른 문자열을 붙여도 기존 문자열에 새로운 문자열을 붙이는 것이 아니라,

새로운 String 객체를 만든 후, 새 String 객체에 연결된 문자열을 저장하고, 그 객체를 참조하도록 합니다. (즉, String 클래스 객체는 Heap 메모리 영역(가비지 컬렉션이 동작하는 영역)에 생성. 한번 생성된 객체의 내부 내용을 변화시킬 수 없습니다. 기존 객체가 제거되면 Java의 가비지 컬렉션이 회수합니다.)

 

String 객체는 이러한 이유로 문자열 연산이 많은 경우, 그 성능이 좋지 않습니다.

하지만, Immutable한 객체는 간단하게 사용가능하고, 동기화에 대해 신경쓰지 않아도 되기때문에(Thread-safe),  내부 데이터를 자유롭게 공유 가능합니다.

 

2) StringBuffer와 StringBuilder

StringBuffer/StringBuilder는 mutable(변함) 합니다. 문자열 연산 등으로 기존 객체의 공간이 부족하게 되는 경우,

기존의 버퍼 크기를 늘리며 유연하게 동작합니다.

 

그럼 두 클래스의 차이점은 무엇일까요? 바로 동기화 여부입니다.

- StringBuffer는 각 메서드별로 Synchronized Keyword가 존재하여, 멀티스레드 환경에서도 동기화를 지원.
- 반면, StringBuilder는 동기화를 보장하지 않음.

 

그렇기 때문에 멀티스레드 환경이라면 값 동기화 보장을 위해 StringBuffer를 사용하고, 단일스레드 환경이라면 StringBuilder를 사용하는 것이 좋습니다. 단일 스레드환경에서 StringBuffer를 사용한다고 문제가 되는 것은 아니지만, 동기화 관련 처리로 인해 StringBuilder에 비해 성능이 좋지 않습니다.

 

String은 짧은 문자열을 더할 경우 사용합니다.

StringBuffer는 스레드에 안전한 프로그램이 필요할 때나, 개발 중인 시스템의 부분이 스레드에 안전한지 모를 경우 사용하면 좋습니다.

StringBuilder는 스레드에 안전한지 여부가 전혀 관계 없는 프로그램을 개발할 때 사용하면 좋습니다.

 

단순히 성능만 놓고 본다면 연산이 많은 경우, StringBuilder > StringBuffer >>> String 입니다.

출처: https://12bme.tistory.com/42

 

 

---

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

1239번: 차트