[1] C++ 구현 알고리즘, 문제에 적용하기, 이것이 코딩테스트다 chapter4 구현 문제풀이

이것이 코딩테스트다. chapter 4 구현 실전 문제 풀이

 

 

구현 문제는 어떤 문제?

머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정으로, 어떤 문제든 간에 해당이 될 수 있는 매우 넓은 범위의 유형이다.

 

구현 문제를 풀 때 생각할 점들

- 파이썬 기준 1초에 2000만 번의 연산 수행을 가정할 때 크게 무리가 없음

- 시간제한이 1초이고, 데이터 개수가 100만 개인 문제에서 N= 1,000,000이면 시간복잡도가 NlogN=20,000,000이므로 이정도의 데이터를 혀용한다고 생각하고 문제를 풀면 무리가 없을 것임

 

이제, 문제를 풀어보자.

 

 

1. 상하좌우 문제

 

문제) 여행가 A는 N*N의 크기의 정사각형 공간 위에 서 있다. 이 공간은 1*1 크기의 정사각형으로 나누어져 있다. 가장 왼 쪽 위 좌표는 (1,1)이며 가장 오른쪽 아래 좌표는 (N,N)에 해당한다, 여행가 A는 상,하,좌,우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 계획서에는 이동할 계획이 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D중 하나의 문자가 반복적으로 적혀있다. 이 계획서에 따라 A가 최종 도착하는 지점의 좌표를 구하라.

 

풀이)

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

int main() {
	//L, R, U, D순서
	//x는 행, y는 열
	int dx[4] = {0, 0, -1, +1};
	int dy[4] = {-1, +1, 0, 0};
	char directions[4] = { 'L', 'R', 'U', 'D' };

	int n;
	cin >> n;
	cin.ignore(); //줄바꿈 문자를 인식해서 바로 처리되므로 버퍼를 비워야 다음 줄을 인식할 수 있음
	string plans;	
	//띄어쓰기를 포함하되 줄바꿈 문자 제외하고 통째로 한 줄을 입력받기(string 헤더)
	getline(cin, plans);
	int x = 1; int y = 1;

	for (int i = 0; i < plans.size(); i++) {
		int nx = 0; int ny = 0;
		for (int j = 0; j < 4; j++) {
			if (plans[i] == directions[j]) {
				nx = x + dx[j];
				ny = y + dy[j];
			}
		}
		if (nx <1 || nx >n || ny <1 || ny >n) {
			continue;
		}
		else {
			x = nx; 
			y = ny;
		}
	}
	cout << x << " " << y;
	return 0;
}

 

2. 시각문제 - (완전탐색)

 

문제) 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

- 00시 00분 03초

- 00시 13분 30초

 

첫 풀이)

 

완전탐색으로 구현해도 워낙 데이터 수가 작은 거라 바보 같이 하나하나 경우의 수를 따졌다. 풀리긴 풀리지만 조금 비효율적이다. 시간을 먼저 파악해서 시간 안에 3이 들어가면 그냥 바로 answer에 3600을 더한 뒤 continue를 했고, 그 이외의 경우, 즉 분이나 초에서 3이 있는 지 확인해야 하는 경우에는 3이 들어가는 시간이 몇 개인지가 고정되어 있으므로 그 수를 계산했다. 분과 초에서 3이 들어갈 수 있는 경우의 수를 구했다. ( 분에 3이 들어가는 경우 + 초에 3이 들어가는 경우 - 분과 초에 모두 3이 들어가는 중복의 경우 )

#include <iostream>
using namespace std;

int main() {
	int answer = 0;
	int n;
	cin >> n;
	//시간이 (3, 13, 23)이면 무조건 포함 : 60(분)* 60(초) = 3600
	//03, 13, 23, 43, 53 , 30~39 -> 15개
	// 15개 * 60 + 15개*60 - 15*15 = 15*(120 - 15) = 15* 105 = 
	for (int i = 0; i <= n; i++) {
		if (i == 3 || i == 13 || i == 23) {
			answer += 3600;
			continue;
		}
		answer += 1575;
	}
	cout << answer;
	return 0;
}

 

교재의 효율적인 풀이)

 

1) 시간을 문자로 바꿔서 3이 있는지 확인하는 방식

2) 10으로 나눠보고 나머지도 구해서 십의 자리 수나 일의 자리 수에 3이 있는 지 확인하는 방식

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

bool check(int h, int m, int s) { //해설만 보고 내가 만든 함수
	string time = "";
	time += to_string(h);
	time += to_string(m);
	time += to_string(s);
	for (char c : time) {
		if (c == '3')
			return true;
	}
	return false;
}
bool check_by_ndb(int h, int m, int s) {//교재 저자의 c++코드
	if (h % 10 == 3 || m / 10 == 3 || m % 10 == 3 || s / 10 == 3 || s % 10 == 3)
		return true;
	return false;
}
int main() {
	int answer = 0;
	int n;
	cin >> n;

	for (int h = 0; h <= n; h++) {
		for (int m = 0; m < 60; m++) {
			for (int s = 0; s < 60; s++) {
				if (check(h, m, s)) answer++;
			}
		}
	}
	cout << answer;
	return 0;
}

 

3. 왕실의 나이트

 

문제) 길어서 생략

풀이) 

 

상하좌우 문제와 매우 유사한 문제로, 문자로 받아지는 열의 알파벳을 -'a' 연산을 해줌으로써 숫자 인덱스로 바꿔서 계산하면 상하좌우 문제와 거의 동일해진다. 저자는 숫자 인덱스로 바꾸면서도 (1,1)부터 시작이라고 생각했지만 내 코드는 맨 왼쪽 상단을 (0,0)이라고 지정해서 각 열과 행을 7번까지 가지는 것으로 생각하고 풀었다.

 

행은 알파벳이므로 입력값에서 'a'를 빼는 연산을 하면 바로 숫자 인덱스를 알 수 있고, 열은 문자를 숫자로 바꾼 뒤에(-'0'을 통해) -1을 해서 0부터 시작하는 인덱스의 값을 구한다.

 

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

//x는 행, y는 열
int dx[8] = {-2, -2, -1, 1, 2,  2, +1, -1};
int dy[8] = {-1, +1, 2, 2, -1, 1, -2, -2};

int main() {
	int answer = 0;

	string location;
	cin >> location; //a1 열, 행 순으로 입력
	int x = (location[1]-'0') -1; //문자의 숫자를 숫자형으로 바꾼 뒤에 -1
	int y = location[0] - 'a';

	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >7 || ny < 0 || ny >7)
			continue;
		else
			answer++;
	}
	cout << answer;
	return 0;
}

 

 

4. 게임개발

 

문제) 길어서 생략

풀이) 

#include <iostream>
using namespace std;

int map[50][50];

//상 좌 하 우 (북동남서)
int dx[4] = { -1, 0, +1, 0 };
int dy[4] = {0, -1, 0,  +1 };

int main(void) {
	int move = 1;
	int m, n, x, y, d;
	cin >> m >> n; 
	cin >> x >> y >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	while (1) {
		map[x][y] = 1;
		for (int i = 1; i <= 4; i++) {//4개 방향 회전
			int nd = (d + i) % 4; //탐색할 방향
			//탐색할 위치
			int nx = x + dx[nd];
			int ny = y + dy[nd];
			if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == 0) { //전진 가능하다면 위치와 방향 업데이트
				d = nd;
				x = nx; y = ny;
				move++;
				break; //for문에 대한 break
			}
			if (i == 4) { // 모든 면이 바다라면
				d = nd; //바라보는 방향 유지
				nd = (nd + 2) % 4; //뒤로 갈 때의 방향 얻기
				nx = x + dx[nd];
				ny = y + dy[nd];
				if ( nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == 1) { //뒷방향도 바다라면
					cout << move;
					return 0;
				}
				else { //뒷 방향 갈 수 있다면
					x = nx; y = ny;
					move++;
				}
			}
		}

	}
}

 

혼잣말.

인턴으로 자바만 보다가 몇 달 만에 C++ 알고리즘 문제 푼 건데 입력 받는 코드를 안 써서 30분 낭비함..하...정신차리자!