1. .length()

문자열의 길이 반환, 공백 포함, null 문자 미포함

int solution(string message) {
	//입력받은 string 문자열 message의 길이를 출력한다
	//the apple을 입력받았다면 9를 출력할 것이다
    return message.length();
}

2. .size()

현재 사용하고 있는 메모리의 크기 반환, null 문자 포함, 하지만 string에서는 문자열 끝에 null 문자를 포함하지 않으므로 length와 같게 나옴

3. .erase(first,last)

first 부터 last 전까지 범위의 요소를 제거한다

//the apple -> e apple
int solution(string message) {
    message.erase(message.begin(),message.begin()+2);
    return message;
}

4. .substr(pos, count)

문자열의 pos 번째 문자 부터 count 길이 만큼의 문자열을 리턴한다.

#include <string>
#include <vector>

using namespace std;

//my_String의 앞에서부터 n글자를 반환
string solution(string my_string, int n) {
    return my_string.substr(0,n);
}

5. .find(str)

문자열에서 str의 위치를 리턴한다. 없으면 string::npos를 반환한다

비슷하게 rfind(str) 함수는 문자열에서 str 위치를 리턴하되 뒤에서부터 찾는다.

#include <string>
#include <vector>

using namespace std;

//문자열 str2에 문자열 str1을 포함할 경우 true를 반환
int solution(string str1, string str2) {
    return str2.find(str1) != string::npos;
}

6. .replace(pos, count, str)

문자열에서 pos부터 시작하는 count 개수의 문자열을 str로 대체한다

#include <string>
#include <vector>

using namespace std;

//문자열 my_string의 s부터 overwrite_string으로 덮어씌운다
string solution(string my_string, string overwrite_string, int s) {
    my_string.replace(s, overwrite_string.size(), overwrite_string);
    return my_string;
}

문제

A도시에서 출발한 기차는 B도시로 도착한다. 그런데 도로 중간에 T자형 교차로가 있어 출발한 기차의 도착 순서를 조정할 수 있다.

교차로에서는 다음과 같은 두 개의 작업을 합니다.

P(Push)작업: A도시에서 오는 기차를 교차로에 넣는다.

O(Out)작업: 교차로에 들어온 가장 최근 기차를 B도시로 보낸다.

만약 2 1 3 기차 번호 순으로 A도시에서 출발하더라도 B도시에는 T교차로를 이용하여 1 2 3 순으로 도착하게 할 수 있습니다.

그 작업 P, P, O, O, P, O 순으로 작업을 하면 B도시에 1, 2, 3 순으로 도착합니다.

1부터 N까지 번호를 가진 기차가 A도시에서 어떤 순으로 출발하든, B도시에 번호순으로 도착하도록 하는 교차로 작업을 출력합니다. 모든 기차는 교차로에 들어가야만 B도시로 갈 수 있습니다. 번호순서대로 도착이 불가능하면 impossible 이라고 출력합니다.

해결

교차로에 다음과 같이 6 1 2 5 4 3 의 기차가 들어간다고 가정하고 생각해보자.

A에서 출발한 기차는 무조건 stack을 거쳐야 한다. 즉 6을 입력함과 동시에 교차로 stack에 A가 저장되는 것이다.

이후 교차로에서 빠져나갈 수 있는 기차, 즉 stack의 꼭대기에 있는 기차가 순서에 맞는 기차인지 판단한다.

아래 상황에서 다음 기차는 1인데 stack의 꼭대기에는 6이 있으므로 6를 꺼내지 않은 채로 새 기차를 받는다.

이제 다음 기차인 1을 교차로 stack에 저장한다.

이후 다음 순서에 맞는 기차인지 판단한다.

다음 기차는 1이고 stack의 꼭대기에도 1이 있으니 기차를 꺼낸다.

기차 1번이 도착했으므로 다음 순서의 기차는 2가 된다.

남아있는 stack의 꼭대기가 다음 순서의 기차인지 확인한다.

다음 순서의 기차는 2인데 stack의 꼭대기에는 6이 있다. 그러므로 A에서 새 기차를 stack에 넣는다.

위와 같은 방법으로 기차 2도 stack에 넣었다가 B로 꺼낸다.

다음 순서의 기차는 2인데 stack의 꼭대기에는 6이 있다. 그러므로 A에서 새 기차를 stack에 넣는다.

다음 기차인 5가 stack에 저장된다. stack의 꼭대기가 된 5는 다음 순서인 3이 아니므로 다음 기차를 받는다.

다음 기차인 4가 stack에 저장된다. stack의 꼭대기가 된 4는 다음 순서인 3이 아니므로 다음 기차를 받는다.

stack의 꼭대기에 다음 순서의 기차인 3이 있으므로 3을 꺼낸다. 다음 순서의 기차는 4가 된다.

stack의 꼭대기에 다음 순서의 기차인 4가 있으므로 4를 꺼낸다. 다음 순서의 기차는 5가 된다.

stack의 꼭대기에 다음 순서의 기차인 5가 있으므로 5를 꺼낸다. 다음 순서의 기차는 6이 된다.

stack의 꼭대기에 다음 순서의 기차인 6가 있으므로 6을 꺼낸다. 모든 기차가 순서대로 꺼내졌다.

만약 기차가 1 3 6 4 5 2 순서로 들어간다면 어떨까?

1번 기차가 stack에 들어갔다가, 다음 순서 기차인 1이므로 빠져나온다

이제 다음 순서 기차인 2가 교차로에 들어올 때까지 교차로는 새 기차를 받을 것이다.

다음 순서 기차인 2가 stack에 들어왔을 때, 2가 빠져나가고 다음 순서 기차가 3이 된다.

하지만 다음 순서 기차인 3은 그 위 기차인 6 4 5에 가로막혀 꼭대기로 나올 수 없다.

또한 더이상 받을 수 있는 새 기차도 없다.

즉, 더이상 새 기차를 받을 수 없는 상태에서 교차로가 비워지지 않았다면, 그것은 기차를 순서대로 빼내는 것이 불가능한 상태이다.

이 경우 impossible을 출력한다.

따라서 다음과 같이 코드 구현이 가능하다.

코드 구현

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main(void)
{
	int nTrainCount; //몇 대의 기차가 들어올 것인가 입력
	cin >> nTrainCount; 

	stack<int> stCrossRoad; //교차로로 사용할 stack
	vector<char> vecOutput; //기차의 P, O 정보를 저장할 vector
	int nNextNumber = 1; //다음 순서의 기차 번호, 1부터 시작해 하나씩 증가한다

	for (int i = 0; i < nTrainCount; i++) //입력받은 기차 수 만큼 기차가 들어온다
	{
		int nTrainNumber;
		cin >> nTrainNumber; //다음에 들어올 기차의 번호를 입력

		stCrossRoad.push(nTrainNumber); //들어온 기차는 무조건 교차로에 넣어져야 한다
		vecOutput.push_back('P'); //기차가 넣어졌으므로 문자열 P 추가

		//교차로 꼭대기에 있는 기차가 다음 순서 기차와 같은지 판정한다
		//교차로 꼭대기에 있는 기차가 다음 순서 기차와 같다면 stack에서 꺼내고 새로 꼭대기가 된 기차를 다시 판정한다
		//교차로 꼭대기에 있는 기차가 다음 순서 기차가 아니라면 반복문을 빠져나와 다음 기차를 받는다
		//모든 기차가 빠져나가 교차로가 비었다면 반복문을 빠져나와 다음 기차를 받는다
		while (true) 
		{
			if (stCrossRoad.empty()) //교차로가 비었다면 다음 기차를 받는다
				break;
			if (stCrossRoad.top() == nNextNumber) //교차로 꼭대기에 다음 순서 기차가 있다면 stack에서 꺼낸다
			{
				stCrossRoad.pop();
				vecOutput.push_back('O');
				nNextNumber++; //다음 기차 순서를 1 늘려주고 다시 새 꼭대기와 비교한다
			}
			else
				break; //교차로 꼭대기에 다음 순서 기차가 없다면 반복문을 중단하고 새 기차를 받는다
		}
	} //A에 있는 기차가 바닥나면 판정을 종료한다

	//만약 A에 있는 모든 기차를 받았는데도 교차로가 비워지지 않았다면 불가능한 것이다
	if (!stCrossRoad.empty())
		cout << "impossible" << endl;
	else
	{
		//교차로가 비워졌다면 성공한 것이니 입출력 결과를 출력한다
		for (int i = 0; i < vecOutput.size(); i++)
			cout << vecOutput[i] << " ";
	}

	return 0;
}

테스트

문제

세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다. 전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨져 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요. 다음과 같은 땅의 정보가 주어지고, 현수가 하사받을 크기가, 가로 2, 세로 3의 크기이면 가장 많은 오렌지 나무가 있는 영지는 총 오렌지 나무의 개수가 16인 3행 4열부터 시작하는 구역이다.

고찰

처음 시도했던 방식은 간단히 설명하면 다음과 같다.

구현하고 보니 아주 잘못된 방식이었기 때문에 자세히 설명하지는 않겠다.

예시 데이터를 수동으로 계산했을 때 최대값도 정확하게 잘 나오는 듯 보였다.

하지만 막상 구현해보니....

for문의 변수명을 i, j, k까지 쓰고 나서야 이 코드가 4중 for문이 될 것임을 알았다.

완성된 코드를 돌려보니 값은 정확하지만, 현수의 영토 크기가 커지자 값을 구하는 속도가 급격하게 느려졌다.

생각해보면 그냥 맨 앞부터 끝까지 4중 for문을 돌리며 최대값을 갱신해 주는 것과 결국 똑같다.

그래도 이전 영역의 최대값을 이용해 다음 영역의 최대값을 구하려고 시도했다는 점에 의의를 두고 싶다.......

해결

처음 영 정보를 받아올 때, 해당 인덱스를 우하단 꼭지점으로 가지는 범위의 오렌지 나무 총 갯수를 다른 2중 배열에 저장한다.

vecTerri[0][0] 일 때 누적값은 (값이 한 개밖에 없으므로) 당연하게도 3이다.

vecTerri[0][1] 일 때 누적값(빨간 사각형 범위의 오렌지 나무 총합)은 기존의 3과 새로 만난 5 값을 더하여 8이다.

단순히 3 + 5 = 8이 아니라 기존 누적값 3에 새로 들어간 값 5을 더해서 8을 얻었다고 생각해야 한다.

따라서 첫 번째 줄의 누적값은 다음과 같이 18이라는 것을 구할 수 있다.

vecTerri[1][0] 일 때 누적값은 다시 vecTerri[0][0]의 값을 가지고 계산해야 한다.

vecTerri[1][0] 를 우하단 꼭지점으로 가지는 사각형에 vecTerri[0][1],  vecTerri[0][2]...  는 포함되지 않기 때문이다.

따라서 누적값은 기존의 3에 새로 들어간 값 1을 더해서 4가 된다.

이제 vecTerri[1][1] 일 때의 누적값을 구해야 한다. 이제는 단순히 이전 값 + 새로 만난 값 계산으로는 구할 수 없다.

구해야 하는 범위(빨간 사각형)에서 새로운 값(초록 사각형)을 뺀 부분의 모양이 사각형이 아니라 ㄱ자 모양이기 때문이다.

하지만 여기서 이제까지 저장해온 누적값을 통해 저 ㄱ자 모양 영토를 분해해서 생각할 수 있다.

앞서 우리는 보라색 사각형 범위의 누적값 4와 파란색 사각형 범위의 누적값 8을 누적값 표에 기록하고 있었기 문이다.

즉 아래 그림에서 빨간 영역의 범위는 보라색 사각형 + 파란색 사각형 값에, 두 사각형을 더하는 과정에서 중복되게 더해진 노란색 사각형 값을 빼준 것과 같다는 것을 알 수 있다.

따라서 vecTerri[1][1] 일 때의 누적값은 4 + 8 - 3 에 새로 들어간 2를 더해서 11이 된다.

이 방식으로 모든 칸의 누적값을 계산할 수 있다.

예를 들어 vecTerri[2][4]까지의 누적값은 보라색 사각형 + 파란색 사각형 - 노란색 사각형 + 초록색 사각형 = 29 + 21 - 19 + 1 = 32로 계산할 수 있다.

하지만 이 규칙을 사용하자니 영토의 맨 윗줄과 맨 왼쪽 줄, 즉 vecTerri[0][n]일 때와 vecTerri[n][0]일 때가 걸린다.

이 경우 초록색 사각형이 가장자리에 붙어 위나 왼쪽에 존재하는 보라색, 파란색, 노란색 사각형이 존재하지 않을 수 있기 때문이다.

이 문제를 해결하기 위해 누적 값을 저장하고 있는 2중 배열에 윗줄과 왼쪽 줄을 하나 더 추가하고, 이것을 0으로 채우는 방법을 사용할 수 있다. (물론 이 경우 보라색, 파란색, 노란색 사각형이 전부 0이기 때문에 값 자체에 영향을 끼치진 않는다)

따라서 이제 영토 vecTerri에 대해 다음과 같은 공식을 사용할 수 있다.

새 칸의 누적값 = 보라색 사각형 + 파란색 사각형 - 노란색 사각형 + 초록색 사각형(새 칸의 값)

→ i, j > 0일 때, vecSum[i][j] = vecSum[i][j-1] + vecSum[i-1][j] - vecSum[i-1][j-1] + vecTerri[i-1][j-1] 

위 공식을 이용해서 vecSum을 완성해준다.

이제 vecTerri[n][m]을 우하단 꼭지점으로 가지는 현수 땅의 오렌지 나무 수를 구해 최대값을 계산하면 된다.

vecSum을 이용하면 고찰에서처럼 2중 for문을 돌지 않고도 특정 땅의 오렌지 나무 수를 구할 수 있다.

아래 그림에서 초록색으로 색칠된 영토의 오렌지 나무 수를 구하고자 한다면, 빨간색 사각형 - 보라색 사각형 - 파란색 사각형 + 노란색 사각형을 해주면 되고, 이 값들은 모두 vecSum에 인덱스 접근이 가능한 형태로 저장되어있다.

즉 vecTerri[3][5] 칸을 우하단 꼭지점으로 하는 현수 땅의 오렌지 나무 수 = vecSum[4][6] - vecSum[4][3] - vecSum[2][6] + vecSum[2][3] = 53 - 25 -25 +13 = 16 이라는 것을 알 수 있다.

이를 공식으로 표현하면 다음과 같다.

현수의 땅이 세로 크기 n, 가로 크기 m일 때, vecTerri[i][j]를 우하단 꼭지점으로 하는 현수 땅의 오렌지 나무 수는

vecSum[i+1][j+1] - vecSum[i+1][j+1-m] - vecSum[i+1-n][j+1] + vecSum[i+1-n][j+1-m] 이다.

이때 i는 n-1부터, j는 m-1부터 시작해야 한다. (그것보다 작으면 현수 땅의 크기가 다 들어가지 못하므로)

코드 구현

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    int nTerriH, nTerriW; //세종대왕 영역 세로, 가로 크기 지정
    cin >> nTerriH >> nTerriW;

    vector<vector<int>> vecTerri(nTerriH, vector<int>(nTerriW)); //세종대왕 영역 2중 벡터
    vector<vector<int>> vecSum(nTerriH + 1, vector<int>(nTerriW + 1)); //누적값 저장할 2중 벡터

    for (int i = 1; i <= nTerriH; ++i)
    {
        for (int j = 1; j <= nTerriW; ++j)
        {
            //세종대왕 땅에 1~9개의 오렌지 나무를 랜덤으로 심는다
            int nOrange = rand() % 9 + 1;
            vecTerri[i-1][j-1] = nOrange;

            //vecSum에 해당 인덱스 영역을 우하단 꼭지점으로 갖는 땅의 오렌지 나무 합계를 저장한다
            vecSum[i][j] = vecSum[i][j - 1] + vecSum[i - 1][j] - vecSum[i - 1][j - 1] + vecTerri[i - 1][j - 1];

            cout << nOrange << " ";
        }
        cout << endl;
    }

    int nMyH, nMyW; //현수 땅의 세로, 가로 크기 지정
    cin >> nMyH >> nMyW;

    int nMaxOrange = 0; //현수 땅이 가질 수 있는 최대 오렌지 나무 수 저장할 변수

    for (int i = nMyH - 1; i < nTerriH; ++i)
    {
        for (int j = nMyW - 1; j < nTerriW; ++j)
        {
            //vecSum을 이용해서 vecTerri[i][j]를 우하단 꼭지점으로 갖는 현수 땅의 오렌지 나무 수를 계산
            int nTempOrange = vecSum[i + 1][j + 1] - vecSum[i + 1][j + 1 - nMyW] - vecSum[i + 1 - nMyH][j + 1] + vecSum[i + 1 - nMyH][j + 1 - nMyW];
            //그 값이 기존에 저장되어 있던 값보다 크면 갱신
            if (nTempOrange > nMaxOrange)
                nMaxOrange = nTempOrange;
        }
    }

    cout << nMaxOrange << endl;

    return 0;
}

테스트

같은 rand()값을 가지고 4중 for문 방식과 정답 방식(다이나믹 프로그래밍)을 돌려보았다. (땅 크기 700x700, 현수 땅 100x100)

clock_t 를 이용해 현수 땅의 세로, 가로 값을 입력받은 후부터 정답 출력까지 걸린 시간을 표시했다.

4중 for문 방식은 어떤 컴퓨터에서 돌리느냐에 따라 차이가 엄청나게 난다. (같은 코드여도 다른 컴퓨터에서는 70초대가 나왔다.)

반면 다이나믹 프로그래밍 방식은 어떤 컴퓨터에서든 0.1초 아래를 유지했다.