[C++] 코딩 테스트 팁

19 Jul 2022 in Study on Algorithm

C++ 코딩 테스트에 쓰이는 팁들 모음

• 함수
  • 대소문자 변환
  • 직사각형의 나머지 꼭짓점 찾기
  • 앞에서부터 i번째 원소와 뒤에서부터 i번째 원소를 출력
  • 데이터 압축
  • 10진수 -> 2진수
• 자료구조 구현
  • 정적 할당 연결리스트

---

---

함수

대소문자 변환

char case_convert(char alphabet) {
	return alphabet ^ 32;
}

직사각형의 나머지 꼭짓점 찾기

void rest_vertex(int x0, int y0, int x1, int y1, int x2, int y2) {
	int x3 = x0 ^ x1 ^ x2;
	int y3 = y0 ^ y1 ^ y2;
	cout << x3 << " " << y3;
}

앞에서부터 i번째 원소와 뒤에서부터 i번째 원소를 출력

vector<int> vec{ 0, 1, 2, 3, 4 };
	for (size_t i = 0; i < vec.size(); ++i) {
		cout << vec.begin()[i] << " " << vec.end()[~i] << "\n";
	}

데이터 압축

// 12자 이내의 알파벳 대문자 문자열을 하나의 long long 변수에 압축
// WARNING 문자열의 끝(‘\0’) 이후에도 전부 ‘\0’으로 채워져 있어야 함
long long compress(char str[13]) {
	long long res = 0;
	for (size_t i = 0; i < 12; ++i) {
		res = (res << 5) | (str[i] ^ 64);
	}
	return res;
}

10진수 -> 2진수

string to_binary(int num) {
	string s = "";
	while (num > 0) {
		if (num % 2 == 1) s = "1" + s;
		else s = "0" + s;
		num >>= 1;
	}
	return s;
}

자료구조 구현

정적 할당 연결리스트

#include <iostream>
using namespace std;
struct Node {
	int data;
	Node* next;
};

constexpr size_t MAX_NODE = 1000;

int node_count = 0;
Node node_pool[MAX_NODE];

Node* new_node(int data) {
	node_pool[node_count].data = data;
	node_pool[node_count].next = nullptr;

	return &node_pool[node_count++];
}

class SinglyLinkedList {
	Node head;

public:
	SinglyLinkedList() = default;

	void init() {
		head.next = nullptr;
	}

	void insert(int x) {
		Node* node = new_node(x);

		node->next = head.next;
		head.next = node;
	}

	void remove(int x) {
		Node* prev_ptr = &head;
		while (prev_ptr->next != nullptr && prev_ptr->next->data != x) {
			prev_ptr = prev_ptr->next;
		}

		if (prev_ptr->next != nullptr) {
			prev_ptr->next = prev_ptr->next->next;
		}
	}

	bool find(int x) const {
		Node* ptr = head.next;
		while (ptr != nullptr && ptr->data != x) {
			ptr = ptr->next;
		}

		return ptr != nullptr;
	}

	void print() const {
		Node* ptr = head.next;
		cout << "[List]  ";
		while (ptr != nullptr) {
			cout << ptr->data;
			if (ptr->next != nullptr) {
				cout << " -> ";
			}
			ptr = ptr->next;
		}
		cout << '\n';
	}
};

int main() {
	SinglyLinkedList slist;
	// 0   : 초기화
	// 1 x : x 삽입
	// 2 x : x 삭제
	// 3 x : x 탐색
	int a, b;
	for (;;) {
		cin >> a;
		switch (a) {
		case 0:
			slist.init();
			slist.print();
			break;
		case 1:
			cin >> b;
			slist.insert(b);
			slist.print();
			break;
		case 2:
			cin >> b;
			slist.remove(b);
			slist.print();
			break;
		case 3:
			cin >> b;
			cout << (slist.find(b) ? "found" : "not found") << '\n';
			break;
		default:
			return cout << "invalid input\n", 0;
		}
	}
}