본문 바로가기

컴퓨터/백준 알고리즘

백준 알고리즘 21360번: Biosalong [C++]

문제 출처: https://www.acmicpc.net/problem/21360

 

21360번: Biosalong

Den första raden innehåller ett heltal $1 \le N \le 1\,000\,000$ -- antalet stolar i raden vi betraktar. Den andra raden innehåller en sträng med $N$ tecken, där det $i$:te tecknet är '#' ifall den $i$:te stolen på raden är upptagen och '.' om stol

www.acmicpc.net

1. 코드

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
	int N;
	cin >> N;

	string arr;
	cin >> arr;

	int min = N;
	int first;
	int last;
	for (int i = 0; i < arr.length(); i++)
	{
		if (arr[i] == '.') {
			first = i;
			break;
		}
	}

	for (int i = first + 1; i < arr.length(); i++)
	{
		if (arr[i] == '.') {
			last = i;
			if (min > last - first - 1)
				min = last - first - 1;
			first = last;
		}
	}
	cout << min;
}

(실행)

2. 풀이

이 문제는 문자열 처리에 대해 잘 알고있다면 쉽게 해결할 수 있다. 문자열을 입력받고 첫번째 공석의 위치를 탐색한 이후에 두 번째 공석의 위치를 찾아낸 뒤 두 거리를 빼고 최솟값으로 설정한 다음 두 번째 공석의 위치를 first에 저장하고 last에는 다음 공석의 위치를 찾아 반복을 해주면 문제는 쉽게 해결됩니다.

int min = N;		//거리 최솟값
int first;			//왼쪽에 있는 공석 위치
int last;			//오른쪽에 있는 공석 위치
for (int i = 0; i < arr.length(); i++)	//첫 번째 공석 위치 찾기
{
	if (arr[i] == '.') {
		first = i;
		break;
	}
}

반복문을 이용하여 첫 번째 공석의 위치를 탐색합니다.

for (int i = first + 1; i < arr.length(); i++)
{
	if (arr[i] == '.') {				//오른쪽에 있는 공석 위치 찾기
		last = i;
		if (min > last - first - 1)		//거리의 차이가 최솟값보다 더 작다면 저장
			min = last - first - 1;
		first = last;				//오른쪽에 있는 공석의 위치를 왼쪽에 있는 공석의 위치로 지정
	}
}

두 번째 공석 이후에도 반복문을 이용하는데 두 거리를 계산하고 최솟값보다 작다면 최솟값으로 설정하고 last의 값을 first에 저장한 뒤 계속해서 last의 값을 찾습니다.

3. 느낀점

해당 문제가 어떠한 언어로 쓰여있는지는 잘 모르지만 구글 번역기로 문제를 알아볼 수 있어서 쉽게 문제를 해결했습니다.