Feel Coding

삼성 SW 역량 테스트 기출 문제인 14891번 문제

나보다 더 노가다로 푼 사람이 있을까 싶을 정도다

#include <iostream>
#include <string>
using namespace std;


int main() {
	string wheel[4];
	int left[4];
	int right[4];
	for (int i = 0; i < 4; i++) {
		cin >> wheel[i];
		left[i] = 6;
		right[i] = 2;
	}
	int k;
	cin >> k;
	int* wheelNum = new int[k];
	int* direction = new int[k];
	for (int i = 0; i < k; i++) {
		int temp;
		cin >> temp;
		cin >> direction[i];
		wheelNum[i] = temp - 1;
	}
	for (int i = 0; i < k; i++) {
		if (wheelNum[i] == 0) { //0번 톱니바퀴인 경우
			if (direction[i] == 1) { //시계 방향인 경우
				if (wheel[0][right[0]] != wheel[1][left[1]]) { //오른쪽 톱니바퀴(1번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 1번이 시계 반대 방향으로 돌아야 함
					if (wheel[1][right[1]] != wheel[2][left[2]]) { //1번과 2번 톱니바퀴가 맞닿는 부분이 다른 극이면 2번 톱니바퀴가 시계방향으로 돌아야 함
						if (wheel[2][right[2]] != wheel[3][left[3]]) { //2번 톱니바퀴와 3번 톱니바퀴가 맞닿는 부분이 다른 극이면 3번이 시계반대방향으로 돌아야 함
							right[3] = (right[3] + 1) % 8;
							left[3] = (left[3] + 1) % 8;
						}
						right[2] = (right[2] - 1 + 8) % 8;
						left[2] = (left[2] - 1 + 8) % 8;
					}
					left[1] = (left[1] + 1) % 8;
					right[1] = (right[1] + 1) % 8;
				}
				right[0] = (right[0] - 1 + 8) % 8;
				left[0] = (left[0] - 1 + 8) % 8;
			}
			else { //시계 반대 방향인 경우
				if (wheel[0][right[0]] != wheel[1][left[1]]) { //오른쪽 톱니바퀴(1번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 시계 방향으로 돌아야 함
					if (wheel[1][right[1]] != wheel[2][left[2]]) { //1번 톱니바퀴와 2번 톱니바퀴가 맞닿는 부분이 다른 극이면 2번 톱니바퀴가 시계반대방향으로 돌아야 함
						if (wheel[2][right[2]] != wheel[3][left[3]]) { //2번 톱니바퀴와 3번 톱니바퀴가 맞닿는 부분이 다른 극이면 3번이 시계방향으로 돌아야 함
							right[3] = (right[3] - 1 + 8) % 8;
							left[3] = (left[3] - 1 + 8) % 8;
						}
						right[2] = (right[2] + 1) % 8;
						left[2] = (left[2] + 1) % 8;
					}
					left[1] = (left[1] - 1 + 8) % 8;
					right[1] = (right[1] - 1 + 8) % 8;
				}
				right[0] = (right[0] + 1) % 8;
				left[0] = (left[0] + 1) % 8;
			}
		}






		else if (wheelNum[i] == 1) {
			if (direction[i] == 1) { //시계 방향인 경우
				if (wheel[1][right[1]] != wheel[2][left[2]]) { //시계 반대 방향으로 돌아야 함
					if (wheel[2][right[2]] != wheel[3][left[3]]) {
						left[3] = (left[3] - 1 + 8) % 8;
						right[3] = (right[3] - 1 + 8) % 8;
					}
					left[2] = (left[2] + 1) % 8;
					right[2] = (right[2] + 1) % 8;
				}
				if (wheel[0][right[0]] != wheel[1][left[1]]) { //왼쪽 톱니바퀴(0번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 시계 반대 방향으로 돌아야 함
					left[0] = (left[0] + 1) % 8;
					right[0] = (right[0] + 1) % 8;
				}
				right[1] = (right[1] - 1 + 8) % 8;
				left[1] = (left[1] - 1 + 8) % 8;
			}
			else { //1번 톱니바퀴이고 반시계 방향인 경우
				if (wheel[1][right[1]] != wheel[2][left[2]]) { //시계 방향으로 돌아야 함
					if (wheel[2][right[2]] != wheel[3][left[3]]) {
						left[3] = (left[3] + 1) % 8;
						right[3] = (right[3] + 1) % 8;
					}
					left[2] = (left[2] - 1 + 8) % 8;
					right[2] = (right[2] - 1 + 8) % 8;
				}
				if (wheel[0][right[0]] != wheel[1][left[1]]) { //왼쪽 톱니바퀴(0번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 시계 방향으로 돌아야 함
					left[0] = (left[0] - 1 + 8) % 8;
					right[0] = (right[0] - 1 + 8) % 8;
				}
				right[1] = (right[1] + 1) % 8;
				left[1] = (left[1] + 1) % 8;
			}
		}
		else if (wheelNum[i] == 2) { //2번 톱니바퀴인 경우
			if (direction[i] == 1) { //시계 방향인 경우
				if (wheel[2][right[2]] != wheel[3][left[3]]) { //오른쪽 톱니바퀴(3번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 3번 톱니바퀴가 시계 반대 방향으로 돌아야 함
					left[3] = (left[3] + 1) % 8;
					right[3] = (right[3] + 1) % 8;
				}
				if (wheel[2][left[2]] != wheel[1][right[1]]) { //왼쪽 톱니바퀴(1번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 시계 반대 방향으로 돌아야 함
					if (wheel[0][right[0]] != wheel[1][left[1]]) { //0번 톱니바퀴와 1번 톱니바퀴가 맞닿는 부분이 다른 극이면 0번 톱니바퀴가 시계방향으로 돌아야 함
						right[0] = (right[0] - 1 + 8) % 8;
						left[0] = (left[0] - 1 + 8) % 8;
					}
					left[1] = (left[1] + 1) % 8;
					right[1] = (right[1] + 1) % 8;
				}
				right[2] = (right[2] - 1 + 8) % 8;
				left[2] = (left[2] - 1 + 8) % 8;
			}
			else { //2번 톱니바퀴이고 반시계 방향인 경우
				if (wheel[2][right[2]] != wheel[3][left[3]]) { //오른쪽 톱니바퀴(3번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 3번 톱니바퀴가 시계 방향으로 돌아야 함
					left[3] = (left[3] - 1 + 8) % 8;
					right[3] = (right[3] - 1 + 8) % 8;
				}
				if (wheel[2][left[2]] != wheel[1][right[1]]) { //왼쪽 톱니바퀴(1번 톱니바퀴)와 맞닿는 부분이 다른 극일 때 시계 방향으로 돌아야 함
					if (wheel[0][right[0]] != wheel[1][left[1]]) { //0번 톱니바퀴와 1번 톱니바퀴가 맞닿는 부분이 다른 극이면 0번 톱니바퀴가 시계반대방향으로 돌아야 함
						right[0] = (right[0] + 1) % 8;
						left[0] = (left[0] + 1) % 8;
					}
					left[1] = (left[1] - 1 + 8) % 8;
					right[1] = (right[1] - 1 + 8) % 8;
				}
				right[2] = (right[2] + 1) % 8;
				left[2] = (left[2] + 1) % 8;
			}
		}
		else { //3번 톱니바퀴인 경우
			if (direction[i] == 1) { //시계 방향인 경우
				if (wheel[3][left[3]] != wheel[2][right[2]]) { //2가 시계반대 방향으로 돌아야 함
					if (wheel[1][right[1]] != wheel[2][left[2]]) { //1이 시계 방향으로 돌아야 함
						if (wheel[0][right[0]] != wheel[1][left[1]]) { //0이 시계 반대 방향으로 돌아야 함
							right[0] = (right[0] + 1) % 8;
							left[0] = (left[0] + 1) % 8;
						}
						right[1] = (right[1] - 1 + 8) % 8;
						left[1] = (left[1] - 1 + 8) % 8;
					}
					left[2] = (left[2] + 1) % 8;
					right[2] = (right[2] + 1) % 8;
				}
				right[3] = (right[3] - 1 + 8) % 8;
				left[3] = (left[3] - 1 + 8) % 8;
			}
			else { //시계 반대 방향인 경우
				if (wheel[3][left[3]] != wheel[2][right[2]]) { //2가 시계방향으로 돌아야 함
					if (wheel[1][right[1]] != wheel[2][left[2]]) { //1이 시계 반대 방향으로 돌아야 함
						if (wheel[0][right[0]] != wheel[1][left[1]]) { //0이 시계 방향으로 돌아야 함
							right[0] = (right[0] - 1 + 8) % 8;
							left[0] = (left[0] - 1 + 8) % 8;
						}
						right[1] = (right[1] + 1) % 8;
						left[1] = (left[1] + 1) % 8;
					}
					left[2] = (left[2] - 1 + 8) % 8;
					right[2] = (right[2] - 1 + 8) % 8;
				}
				right[3] = (right[3] + 1) % 8;
				left[3] = (left[3] + 1) % 8;
			}
		}
	}
	int sum = 0;
	if (wheel[0][(left[0] + 2) % 8] == '1') {
		sum += 1;
	}
	if (wheel[1][(left[1] + 2) % 8] == '1') {
		sum += 2;
	}
	if (wheel[2][(left[2] + 2) % 8] == '1') {
		sum += 4;
	}
	if (wheel[3][(left[3] + 2) % 8] == '1') {
		sum += 8;
	}
	cout << sum << endl;
	return 0;
}

포인터를 어려워하는 분들이 많은 것 같다. 물론 나도 겁먹었었다.

하지만 전혀 어렵지 않다는 것을 알게 되었고 다른 사람들에게도 포인터가 어렵지 않다는 것을 전파시키고 싶다.

일반적으로 변수는 정수, 실수, 문자 등 데이터 값을 저장한다.

하지만 포인터 변수는 위와 같은 데이터가 저장되어 있는 메모리 주소를 저장하는 특별한 변수이다.

변수 이름 앞에 &를 붙이면 그 변수가 저장된 메모리의 주소이다.

#include <iostream>
using namespace std;

int main() {
	int a = 100;
	cout << &a << endl; // a의 주소 출력
	return 0;
}

위 코드를 실행하면 이런 결과가 나온다.

a가 저장된 메모리의 주소가 출력되는 것을 볼 수 있다.  이처럼 &a 라는 표현은 a의 주소라는 것이다.

잊지 말자 어떤 변수의 주소를 사용하고 싶다면

&변수이름

이렇게 쓰면 된다.

그런데 012FF71C와 같은 주소를 어떤 변수에 저장하고 싶다면? 그 변수의 타입은?

주소는 어떤 타입의 변수에 저장해야 하는걸까?

포인터 변수에 저장하면 된다. 포인터 변수는 무조건 4바이트이다. 왜냐하면 포인터 변수는 어떤 변수(그 변수 이름을 a라고 하자)의 주소를 담는 변수인데 a가 int 타입이건 double 타입이건 char 타입이건 메모리 주소는 32비트(4바이트)이기 때문이다. (32bit 시스템의 경우)

그럼 포인터 변수는 무슨 타입의 변수일까?

포인터에도 여러 타입이 있다.

int 타입 a의 주소를 저장하려면 int* 타입의 포인터 변수에 저장하면 되고

short 타입 변수인 b의 주소를 저장하려면 short* 타입의 포인터 변수에 저장하면 되고

char 타입 변수인 c의 주소를 저장하려면 char* 타입의 포인터 변수에 저장하면 된다.

포인터 변수도 다른 변수들과 마찬가지로 사용하기 전에 선언해야 한다.

예를 들어 a라는 int 타입 변수의 주소를 pa라는 포인터 변수에 저장하려면

int a = 100;
int* pa = &a; //포인터 변수 선언 및 a의 주소 대입

이렇게 하면 된다. 이제 pa에는 a의 주소 32비트(4바이트)가 저장되어 있다.

메모리 몇 번지인지 pa에 저장된 주소를 보고 싶다면 직접 cout << pa; 해 보면 된다.

pa에는 주소가 담겨 있다는 것을 알 수 있다.

그러니까 cout << &a;와 cout << pa;는 똑같이 a의 주소를 출력한다.

그럼 int 말고 다른 타입 변수들도 포인터 변수에 주소를 저장해 보자.

int count = 5;
short status = 2;
char letter = 'A';

int* pCount = &count;
short* pStatus = &status;
char* pLetter = &letter;

이 경우 메모리 상에는 이렇게 저장된다.

count는 int 타입이기 때문에 4칸에 걸쳐서  5가 저장되고 status는 short 타입이기 때문에 두 칸에 걸쳐서 2가 저장되고 letter은 char 타입이기 때문에 한 칸에 'A'의 아스키코드 값인 65(16진수로 41)가 저장된다. (메모리는 1바이트마다 주소가 부여되어 있기 때문에 메모리 한 칸은 1바이트라고 생각하면 된다.)

그리고 포인터 변수인 pCount는 4칸에 걸쳐서 count가 저장된 메모리의 주소를 저장하고 있고

pStatus도 4칸에 걸쳐서 status가 저장된 메모리의 주소를 저장하고 있고

pLetter도 4칸에 걸쳐서 letter가 저장된 메모리의 주소를 저장하고 있는 것을 볼 수 있다.

그러면 여기에서 의문이 들 것이다. 일반 변수를 선언할 때 타입을 명시하는 이유는

int 타입은 메모리 4바이트를 잡아야 하고 double 타입은 8바이트, char은 1바이트, ... 이런 식으로 타입마다 잡아야 하는 메모리의 크기가 다르니까 그러는 것이지만

포인터 변수는 어차피 다 4바이트인데 왜 선언할 때 int*, short*, char* 이런 식으로 타입을 다르게 선언하는 것일까?

어차피 다 4바이트인데?

그 이유는 여기에 있다.

포인터 변수는 간접 참조 연산자 *를 통해서 그 주소에 저장된 값을 읽어올 수 있다.

예를 들면 int*형 포인터 변수 pCount에 저장된 주소를 가지고 count에 저장된 값인 5를 읽어올 수 있다.

int count = 5;
int* pCount = &count;
cout << *pCount << endl; //5 출력

pCount에는 주소인 00B3FC00이 저장되어 있다. 그리고 그 주소 00B3FC00번지에는 5가 저장되어 있다.

*pCount는 pCount에 있는 그 주소(00B3FC00번지)에 가서 거기에 있는 값을 가져오라는 것이다. 

따라서 cout << *pCount;나 cout << count;나 똑같이 5를 출력한다.

정리하면

*포인터변수

는 '그 주소에 가서 거기에 저장되어 있는 값을 가져와'라는 말이다.

그런데 문제가 있다. *pCount라고 해서 일단 00B3FC00번지에 가긴 했는데 여기에서 몇 바이트를 읽어와야 하지?

00B3FC00번지에는 00이 저장되어 있고 그 다음 번지에는 00, 그 다음 번지에는 00, 그 다음 번지에는 05, 그 다음 번지에는 00, 그 다음 번지에는 02가 저장되어 있는데 몇 칸을 읽어와야 하는 걸까?

여기에서 포인터 변수의 타입이 필요하다. pCount는 int* 타입의 포인터 변수이다. int는 4바이트이므로 00B3FC00번지부터 4바이트 만큼의 데이터를 읽어오면 된다. 즉 00000005를 읽어오는 것이다.

그러니까 포인터 변수의 타입은 * 연산자를 이용해서 그 주소에 있는 값을 읽어올 때 몇 칸을 읽어올지 알기 위해서 있는 것이다. int* 타입의 포인터 변수는 4바이트를 읽어오면 되고 char* 타입의 포인터 변수는 1바이트를 읽어오면 되고 double* 타입의 포인터 변수는 8바이트를 읽어오면 된다.

만약 변수의 타입과 포인터 변수의 타입이 다르다면

이렇게 컴파일 에러가 난다. 따라서 반드시 변수의 타입과 포인터의 타입을 일치시켜야 한다.

이제 포인터의 기본을 배웠으니 예제 코드를 살펴보자.

#include <iostream>
using namespace std;

int main() {
  	int count = 5;
  	int* pCount = &count;

  	cout << "The value of count is " << count << endl;
  	cout << "The address of count is " << &count << endl;
  	cout << "The address of count is " << pCount << endl;
  	cout << "The value of count is " << *pCount << endl;

  	return 0;
}

위의 코드의 실행 결과이다.

count와 *pCount는 5를, &count와 pCount는 주소를 출력하는 것을 볼 수 있다.

다음 글은 여기에서 이어집니다. ↓

breakcoding.tistory.com/294

c언어에서 쓰는 cstring은 문자열이 아니라 문자(char)의 배열인데 끝에 '\0'(널)로 막아줘야 하는 등 불편하고 문제가 많아서 C++에서는 string 클래스를 사용해서 문자열을 처리한다.

string은 int, double과 같은 기초타입(basic type)이 아니라 클래스이다.

따라서 string 클래스를 사용하고 싶으면 #include <string> 문장을 써서 <string> 헤더파일을 포함해야 한다.

string 클래스는 문자의 배열을 멤버변수로 가지며, 그것을 처리하는 함수들을 멤버함수로 가지고 있다.

아래의 두 문장은 결과적으로는 같지만 첫 번째 문장이 더 빠르다.

string s("Welcome to c++");

string s = "Welcome to c++";

첫 번째 문장은 바로 문자열 객체를 생성하는 것이지만

두 번째 문장이 동작하는 과정은 다음과 같다.

string은 클래스이기 때문에 생성자가 있다. 두 번째 문장의 경우 string s; 이렇게 선언한 것과 같으므로 string 클래스의 인자 없는 생성자가 호출된다. 따라서 일단 빈 문자열을 가진 객체가 생성된다.

그러고 나서 "Welcome to c++"라는 리터럴을 리터럴 저장소에서 복사해서 가져오는 것이다.

따라서 두 문장은 결과적으로는 같지만 내부적으로 동작되는 것은 다르다.

하지만 요즘은 내부적으로 optimizing(최적화) 시키기 때문에 시간 차이가 거의 없다고 한다.

문자열 추가

(참고로 UML 클래스 다이어그램에서 +는 public을, -는 private을 뜻한다.)

①append(s :string)

string s1("Welcome");
s1.append(" to C++");
cout << s1 << endl; // Welcome to C++ 출력

②append(s: string, index: int, n: int)

string s2("Welcome");
s2.append(" to C and C++", 0, 5);
cout << s2 << endl; // Welcome to C 출력

여기서 헷갈리지 말아야 할 것은

s2.append(문자열, 0, 5");는 0번째 인덱스에서 시작해서 5개를 추가한다. ("0번째 인덱스부터 5번째 인덱스까지"가 아님)

③append(s: string, n: int)

string s3("Welcome");
s3.append(" to C and C++", 5);
cout << s3 << endl;

s3.append(문자열, 5);는 처음부터 5개를 s3에 추가하는 것이다. 즉 s3.append(문자열, 0, 5);와 같다.

④append(n: int, ch: char)

string s4("Welcome");
s4.append(4, 'G');
cout << s4 << endl;

이 함수에서 두 번째 인자는 char 타입이어야 한다. 'G'는 char 타입의 문자이지만 "G"는 string 클래스의 문자열이다.

작은따옴표는 char(문자), 큰 따옴표는 string(문자열)이라는 것 잊지 말자.

문자열 대입

①assign(s[]: char)

string s1("Welcome");
s1.assign("Dallas"); 
cout << s1 << endl; // Dallas 출력

②assign(s: string, index: int, n: int)

string s2("Welcome");
s2.assign("Dallas, Texas", 0, 5); 
cout << s2 << endl; // Dalla 출력

③assign(s: string, n: int)

string s3("Welcome");
s3.assign("Dallas, Texas", 5); 
cout << s3 << endl; // Dalla 출력

④assign(n: int, ch: char)

string s4("Welcome");
s4.assign(4, 'G'); 
cout << s4 << endl; // GGGG 출력

at, clear, erase, empty 함수

string s1("Welcome");
cout << s1.at(3) << endl;         // c 출력
cout << s1.erase(2, 3) << endl ;  // Weme 출력
s1.clear();                	// s1은 빈 문자열
cout << s1.empty() << endl ;     // s1은 비어있으므로 1(true)을 출력한다.                                    

length, size, capacity 함수

string s1("Welcome");
cout << s1.length() << endl;       // 길이는 7
cout << s1.size() <<endl;          // 크기는 7
cout << s1.capacity() << endl;     // 용량은 15

s1.erase(1, 2);                    //s1은 Wcome가 됨
cout << s1.length() << endl;       // 길이는 5
cout << s1.size() << endl;         // 크기는 5
cout << s1.capacity() << endl;     // 길이는 줄었지만 용량은 여전히 15

length()나 size()는 우리가 직접 글자 수를 세어보면 알 수 있지만 capacity()의 경우 직접 출력해보지 않으면 알 수 없다.

이 경우 운영체제가 15byte를 잡고 시작한 것이다. 규칙은 없고 OS가 여유있게 잡아놓고 나중에 필요하면 용량을 증가시킨다. 운영체제가 몇 바이트를 잡았는지는 문자열객체.capacity()로 직접 찍어봐야 알 수 있다.

문자열 비교 함수

두 개의 문자열 내용을 비교해야 할 때에는 compare() 함수를 사용한다.

두 개의 문자열을 비교하는데 왜 인자가 한 개일까? 

문자열 객체 자기 자신과 매개변수로 들어온 문자열을 비교한다.

string s1("Welcome");
string s2("Welcomg");

cout << s1.compare(s2) << endl; 	// 앞이 작으므로 -1 반환
cout << s2.compare(s1) << endl; 	// 앞이 크므로 1 반환
cout << s1.compare("Welcome") << endl; 	// 같으므로 0 반환

문자열을 비교하는 방법은 앞에서부터 한 글자씩 비교하는 것이다.

s1.compare(s2);의 경우를 예로 살펴보자.

일단 s1의 0번 인덱스에 해당하는 문자인 'W'와 s2의 0번 인덱스에 해당하는 문자 'W'를 비교한다. 같다.

그러면 s1의 1번 인덱스의 'e'와 s2의 1번 인덱스 'e'를 비교한다. 같다.

그러면 또 다음 인덱스인 2번 인덱스를 비교한다.

그렇게 하다가 6번 인덱스를 비교할 차례이다.

s1의 6번 인덱스인 'e'와 s2의 6번 인덱스인 'g'를 비교한다. 'e'의 아스키코드 값은 101, 'g'의 아스키코드 값은 103이다.

101 - 103은 음수이다. 이렇게 객체 자신(이 경우 s1)이 인자로 들어온 문자열(이 경우 s2)보다 작을 경우 -1을 반환한다.

s2.compare(s1); 처럼 객체 자신이 인자로 들어온 문자열보다 클 경우 1을 반환한다.

s1.compare("Welcome"); 처럼 문자열 객체 자신과 인자로 들어온 문자열이 일치하면 0을 반환한다.

만약 헷갈리고 외우기가 어렵다면 앞의 것에서 뒤의 것을 뺀다고 생각하면 된다.

앞의 것이 더 크면 1, 뒤의 것이 더 크면 -1, 같으면 0.

부분 문자열 구하기

string s1("Welcome");
cout << s1.substr(0, 1) << endl;  // W 출력(0위치부터 1개)
cout << s1.substr(5) << endl;    // me 출력(5위치부터 끝까지)
cout << s1.substr(3, 3) << endl; // com 출력(3위치부터 3개)

여기서 헷갈리지 말아야 할 것은 s1.substr(5);은 처음부터 5까지도 아니고, 처음부터 5개도 아니고 인덱스 5 위치부터 끝까지이다.

아까 위에서 append() 함수의 경우 s1.append(" to C and C++", 5);는 처음부터 5개이기 때문에 이것과 헷갈릴 수 있다.

append() 함수는 처음부터 5개, substr() 함수는 5부터 끝까지라는 것 꼭 기억하자.

또 하나 기억해야 할 것은 substr() 함수는 원본을 바꾸지 않는다는 것이다. 단지 부분문자열을 반환만 할 뿐이다.

s1.substr(0, 1)을 출력하면 W를 출력하겠지만 s1이 W로 바뀌는 것은 아니다. s1은 "Welcome" 그대로이다.

문자열 검색

//문자 검색
cout << s1.find('o') << endl;      // 4 출력(처음위치부터 찾음)
cout << s1.find('o', 6) << endl;   // 9 출력(인덱스 6 부터 찾음)

//문자열 검색
string s1("Welcome to HTML");
cout << s1.find("co") << endl;     // 3 출력(처음위치부터 찾음)

if (s1.find("co", 6) == string::npos)//찾지 못하면(인덱스 6부터 찾음) string::npos 반환
	cout << "co는 없습니다" << endl;

find() 함수는 최초 발견된 위치를 반환하기 때문에 문자열에서 'o'가 있는 모든 인덱스를 찾고 싶으면 이렇게 사용하면 된다.

string s1("Welcome to c++");
int idx = 0;
int count = 1;
while (s1.find('o', idx) != string::npos) {
	idx = s1.find('o', idx);
	cout << count << "번째로 발견된 o의 위치는 " << idx++ << "입니다." <<endl;
	count++;
}

이렇게 find() 함수의 반환값 + 1을 find 함수의 두 번째 인자로 주면 계속 검색할 수 있다. (여기에서는 후위연산자로 idx를 1 증가시켜줬다)

만약에 찾지 못하면 string::npos를 반환하는데 npos는 const형 static 변수이다. (npos는 not position의 줄인 말이다.)

static 멤버를 사용할 때에는 클래스이름::을 앞에 붙여줘야 한다.

문자열 삽입과 교체

string s1("Welcome to HTML");
s1.insert(11, "C++ and "); // s1의 인덱스 11 위치에 문자열 삽입
cout << s1 << endl;	// Welcome to C++ and HTML 출력

string s2("AA");
s2.insert(1, 4, 'B'); //s2의 인덱스 1 위치에 문자 4개 삽입
cout << s2 << endl; //ABBBBA 출력

string s3("Welcome to HTML");
s3.replace(11, 4, "C++"); // s3의 인덱스 11부터 4개를 문자열로 교체
cout << s3 << endl;	// Welcome to C++ 출력

문자열 연산자

string s1="ABC";
string s2 = s1;
cout << s1[0];  // A 출력

string s3 = s1 + "DEFGH";  //s3는 ABCDEFGH
s1 += "ABC";  //s1은 ABCABC
cout << (s1<=s3) << endl ;  // 1(true) 출력

s1[0]은 s1.at(0)과 똑같고 s1 += "ABC"는 s1.append("ABC")와 똑같다.

+=라는 연산자를 그런 역할을 하도록 내부적으로 그렇게 정의해놓은 것이다.

그런데 +=보다는 append() 함수를 사용하는 것이 문자열을 더 정교하게 컨트롤할 수 있다.

물론 단순히 문자열을 하나의 문자열 뒤에 통째로 추가하고 싶을 때에는 +=와 append()나 똑같기 때문에 아무거나 사용해도 된다.

또 주의해야 할 것은 <= 연산자는 참일 때 1(true)를 리턴하지만 compare() 함수는 두 문자열이 같을 때 1을 리턴한다.

단계별로 풀어보기 문자열의 3단계 문제

c++의 <string>을 포함하고 <string>의 편리한 함수를 사용하면 쉽게 풀 수 있다.

find 함수의 사용법은 다음과 같다.

string s1("Welcome");
cout << s1.find('o') << endl; // 4 출력 (처음부터 찾음)
cout << s1.find('o', 6) << endl; // 9 출력. (인덱스 6부터 'o'를 찾음)
if (s1.find("el", 3) == string::npos)
	cout << "el은 없습니다" << endl;

find 함수는 찾고자 하는 문자 또는 문자열이 없으면 string::npos를 반환한다.

#include <iostream>
#include <string>
using namespace std;


int main() {
	string s;
	cin >> s;
	int alphabet[26];
	for (int i = 0; i < 26; i++) {
		alphabet[i] = -1;
	}
	alphabet[0] = s.find('a');
	alphabet[1] = s.find('b');
	alphabet[2] = s.find('c');
	alphabet[3] = s.find('d');
	alphabet[4] = s.find('e');
	alphabet[5] = s.find('f');
	alphabet[6] = s.find('g');
	alphabet[7] = s.find('h');
	alphabet[8] = s.find('i');
	alphabet[9] = s.find('j');
	alphabet[10] = s.find('k');
	alphabet[11] = s.find('l');
	alphabet[12] = s.find('m');
	alphabet[13] = s.find('n');
	alphabet[14] = s.find('o');
	alphabet[15] = s.find('p');
	alphabet[16] = s.find('q');
	alphabet[17] = s.find('r');
	alphabet[18] = s.find('s');
	alphabet[19] = s.find('t');
	alphabet[20] = s.find('u');
	alphabet[21] = s.find('v');
	alphabet[22] = s.find('w');
	alphabet[23] = s.find('x');
	alphabet[24] = s.find('y');
	alphabet[25] = s.find('z');
	for (int i = 0; i < 26; i++) {
		cout << alphabet[i] << " ";
	}
	return 0;
}

단계별로 풀어보기 백트래킹의 8단계 문제이자 삼성 SW 역량 테스트 기출 문제인 14889번 문제

#include <iostream>
#include <vector>
using namespace std;

int n;
bool* visited;
int* startMembers;
int* linkMembers;
int** arr;
vector<int> difference;

int ability(int* members) {
	int sum = 0;
	for (int i = 0; i < n / 2; i++) {
		for (int j = 0; j < n / 2; j++) {
			if (j != i) {
				sum += arr[members[i]][members[j]];
			}
		}
	}
	//cout << "sum은 " << sum << " ";
	return sum;
}
void divideTeam(int num) {
	if (num == n / 2) {
		int index = 0;
		for (int i = 0; i < n; i++) {
			bool flag = true;
			for (int j = 0; j < n / 2; j++) {
				if (startMembers[j] == i) {
					flag = false;
				}
			}
			if (flag) {
				linkMembers[index] = i;
				index++;
				if (index == n / 2) break;
			}
		}
		difference.push_back(abs(ability(startMembers) - ability(linkMembers)));
		return;
	}
	for (int i = 0; i < n; i++) {
		if (num > 0) {
			if (startMembers[num - 1] < i) {
				if (!visited[i]) {
					startMembers[num] = i;
					visited[i] = true;
					divideTeam(num + 1);
					visited[i] = false;
				}
			}
		}
		else {
			if (!visited[i]) {
				startMembers[num] = i;
				visited[i] = true;
				divideTeam(num + 1);
				visited[i] = false;
			}

		}
	}
}


int main() {
	cin >> n;
	arr = new int*[n];
	visited = new bool[n];
	for (int i = 0; i < n; i++) {
		visited[i] = false;
	}
	for (int i = 0; i < n; i++) {
		arr[i] = new int[n];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	startMembers = new int[n / 2];
	linkMembers = new int[n / 2];
	divideTeam(0);
	int minDifference = difference[0];
	for (int i = 1; i < difference.size(); i++) {
		if (difference[i] < minDifference)
			minDifference = difference[i];
	}
	cout << minDifference << endl;
	return 0;
}

삼성 SW 역량 테스트 기출 문제이자 단계별로 풀어보기 백트래킹의 7단계 문제

처음에 분명히 맞게 풀었는데 컴파일 에러가 나는 것이었다. 원인은 min과 max라는 변수 이름 때문이었다.

따라서 min을 minn으로, max를 maxx로 바꿔줬더니 성공

#include <iostream>
using namespace std;

int n;
int* numbers;
int maxx = -1000000000;
int minn = 1000000000;

void select(char* oper, int num, int plusRemain, int minusRemain, int multiplyRemain, int divideRemain) {
	if (num == n - 1) {
		int result = numbers[0];
		for (int i = 0; i < n - 1; i++) {
			switch (oper[i]) {
			case '+':
				result += numbers[i + 1]; break;
			case '-':
				result -= numbers[i + 1]; break;
			case '*':
				result *= numbers[i + 1]; break;
			case '/':
				result /= numbers[i + 1]; break;
			}
		}
		if (result > maxx) maxx = result;
		if (result < minn) minn = result;
		return;
	}
	if (plusRemain > 0) {
		oper[num] = '+';
		select(oper, num + 1, plusRemain - 1, minusRemain, multiplyRemain, divideRemain);
	}
	if (minusRemain > 0) {
		oper[num] = '-';
		select(oper, num + 1, plusRemain, minusRemain - 1, multiplyRemain, divideRemain);
	}
	if (multiplyRemain > 0) {
		oper[num] = '*';
		select(oper, num + 1, plusRemain, minusRemain, multiplyRemain - 1, divideRemain);
	}
	if (divideRemain > 0) {
		oper[num] = '/';
		select(oper, num + 1, plusRemain, minusRemain, multiplyRemain, divideRemain - 1);
	}
}

int main() {
	cin >> n;
	numbers = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	int plus, minus, multiply, divide;
	cin >> plus >> minus >> multiply >> divide;
	char* oper = new char[n - 1];
	select(oper, 0, plus, minus, multiply, divide);	
	cout << maxx << endl;
	cout << minn << endl;
	return 0;
}

자바의 StringTokenizer를 이용해서 손쉽게 풀 수 있었다. C++로도 한 번 더 풀어봐야겠다.

import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        int count = 0;
        while (st.hasMoreTokens()) {
            st.nextToken();
            count ++;
        }
        System.out.println(count);
    }
}

입력을 받을 때 0인 것의 위치를 emptyLocation이라는 벡터에 집어넣는다.

그리고 1부터 9까지의 수로 emptyLocation.size() 만큼의 중복순열을 구한다.

check 함수는 숫자를 배치하려고 하는 위치에 그 값을 집어넣는 것이 바람직한지 체크해서 true나 false를 리턴해주는 함수이다.

#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

int sudoku[9][9];
bool flag = false;
bool check(int row, int col, int value) {
	for (int i = 0; i < 9; i++) { //row번째 가로줄, col번째 세로줄에 value와 같은 값이 있는지 체크
		if (sudoku[row][i] == value || sudoku[i][col] == value)
			return false;
	}
	//(row, col)이 몇 번째 사각형에 속하는지 알아보고 그 사각형에 value와 같은 값이 있는지 체크
	int recRow = row / 3;
	int recCol = col / 3;
	for (int i = recRow * 3; i < recRow * 3 + 3; i++) {
		for (int j = recCol * 3; j < recCol * 3 + 3; j++) {
			if (sudoku[i][j] == value)
				return false;
		}
	}
	return true;
}

void select(int* result, vector<pair<int, int>> emptyLocation, int num) {
	if (num == emptyLocation.size()) {

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << sudoku[i][j] << " ";
			}
			cout << endl;
		}
		flag = true;
		return;
	}

	for (int i = 1; i <= 9; i++) {
		if (check(emptyLocation[num].first, emptyLocation[num].second, i) && !flag) {
			result[num] = i;
			sudoku[emptyLocation[num].first][emptyLocation[num].second] = i;
			select(result, emptyLocation, num + 1);
			sudoku[emptyLocation[num].first][emptyLocation[num].second] = 0;
		}
		if (flag) {
			return;
		}
	}
}

int main() {
	vector<pair<int, int>> emptyLocation;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> sudoku[i][j];
			if (sudoku[i][j] == 0) {
				emptyLocation.push_back(make_pair(i, j));
			}
		}
	}
	int count = emptyLocation.size();
	int* result = new int[count];
	select(result, emptyLocation, 0);

	return 0;
}

단계별로 풀어보기 수학 1의 7단계 문제

배열을 하나 만들어놓고 차곡차곡 더해서 저장하면 된다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int a;
	cin >> a;
	int** input = new int*[a];
	for (int i = 0; i < a; i++) {
		input[i] = new int[2];
	}
	int maxFloor = 0;
	int maxNumber = 1;
	for (int i = 0; i < a; i++) {
		int floor, number;
		cin >> floor >> number;
		if (floor > maxFloor) maxFloor = floor;
		if (number > maxNumber) maxNumber = number;
		input[i][0] = floor;
		input[i][1] = number;
	}
	int** apartment = new int*[maxFloor + 1];
	for (int i = 0; i < maxFloor + 1; i++) {
		apartment[i] = new int[maxNumber];
	}
	for (int i = 0; i <= maxFloor; i++) {
		apartment[0][i] = i + 1; //0층 i호를 i + 1로 초기화
	}
	for (int i = 1; i < maxFloor + 1; i++) { //1층부터 k층까지
		int sum = 0;
		for (int j = 0; j < maxNumber; j++) { //1호부터 n호까지
			sum += apartment[i - 1][j];
			apartment[i][j] = sum;
		}
	}
	for (int i = 0; i < a; i++) {
		cout << apartment[input[i][0]][input[i][1] - 1] << endl;
	}

	return 0;
}

단계별로 풀어보기 동적 계획법 1의 10단계 문제

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* grape = new int[n];
	int** dp = new int*[n];
	for (int i = 0; i < n; i++) {
		dp[i] = new int[2];
	}
	for (int i = 0; i < n; i++) {
		cin >> grape[i];
	}
	dp[0][0] = grape[0];
	dp[0][1] = grape[0];
	if (n > 1) {
		dp[1][0] = grape[0] + grape[1];
		dp[1][1] = grape[1];
	}
	for (int i = 2; i < n; i++) {
		dp[i][0] = dp[i - 1][1] + grape[i];
		int max = 0;
		for (int j = i - 2; j >= 0; j--) {
			for (int k = 0; k < 2; k++) {
				if (dp[j][k] > max) {
					max = dp[j][k];
				}
			}
		}
		dp[i][1] = max + grape[i];
	}
	int max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			if (dp[i][j] > max) {
				max = dp[i][j];
			}
		}
	}
	cout << max << endl;
	return 0;
}

배열 dp[i][0]에는 i-1번째 포도주를 마셨을 경우 최대 양을, dp[i][1]에는 i-1번째 포도주를 마시지 않았을 경우 가능한 최대 양을 저장했다.

2579번 계단오르기와 다른 점은 계단 오르기 문제는 반드시 마지막 계단을 밟아야 하지만 이 문제는 반드시 마지막 포도주를 마실 필요가 없다. 또, 계단오르기는 무조건 한 칸이나 두 칸씩 올라야 하지만 포도주 마시기는 여러 포도주를 뛰어넘고 안 마셔도 상관이 없다. 따라서 이 문제가 더 고려할 것이 많아 조금 더 복잡하다.

이렇게 2020년에 1월 24일에 풀고 두 달 반 후인 4월 11일에 다시 한 번 풀어보았다.

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	vector<tuple<int, int, int>> dp(n);
	dp[0] = make_tuple(0, v[0], v[0]);
	if (n > 1) {
		dp[1] = make_tuple(v[0], v[1], v[0] + v[1]);
	}
	for (int i = 2; i < n; i++) {
		get<0>(dp[i]) = max(get<0>(dp[i - 1]), max(get<1>(dp[i - 1]), get<2>(dp[i - 1])));
		get<1>(dp[i]) = get<0>(dp[i - 1]) + v[i];
		get<2>(dp[i]) = get<1>(dp[i - 1]) + v[i];
	}
	cout << max(get<0>(dp[n - 1]), max(get<1>(dp[n - 1]), get<2>(dp[n - 1])));
	return 0;
}

코드 길이도 더 짧고 시간도 더 적게 걸렸고 메모리도 더 적게 사용했다.

나는 잘 모르겠어도 나도 모르는 사이에 발전은 하나보다.

3-tuple을 만들어서 dp 벡터에 저장했다.

dp[i]에 저장된 튜플의 첫 번째 원소는 i번째 포도주를 마시지 않는 경우 중 최댓값을 저장한다. i번째 포도주를 마시지 않으므로 dp[i]에 저장된 3가지 숫자 중에 가장 큰 수를 그대로 가져온다.

dp[i]에 저장된 튜플의 두 번째 원소는 i번째 포도주를 마시되 i - 1번째 포도주는 마시지 않았을 경우 중 최댓값을 저장한다. i - 1번째 포도주는 마시지 않았어야 하므로 dp[i - 1]의 첫 번째 원소에 i번째 포도주를 더해준 값을 저장한다.

dp[i]에 저장된 튜플의 세 번째 원소는 i번째 포도주 연속으로 마시는 경우이다. 세 개를 연속으로 마시지는 못하므로 dp[i - 1]의 두 번째 원소에 i번째 포도주를 더해준 값을 저장한다.