Feel Coding

https://www.acmicpc.net/problem/1292

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

int main() {
	int aa, bb;
	cin >> aa >> bb;
	int arr[1001];
	int index = 1;
	for (int i = 1; index <= 1000; i++) {
		for (int j = 0; j < i; j++) {
			if (index > 1000) break;
			arr[index++] = i;
		}
	}
	int total = 0;
	for (int i = aa; i <= bb; i++) {
		total += arr[i];
	}
	cout << total;
	return 0;
}

처음에는 아래와 같이 제출했는데

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

int main() {
	int aa, bb;
	cin >> aa >> bb;
	int arr[1001];
	int index = 1;
	for (int i = 1; index <= 1000; i++) {
		for (int j = 0; j < i; j++) {
			arr[index++] = i;
		}
	}
	int total = 0;
	for (int i = aa; i <= bb; i++) {
		total += arr[i];
	}
	cout << total;
	return 0;
}

배열의 인덱스를 초과해도 오류가 나지 않아서 바꾸지도 않은 a와 b가 45로 바뀌는 신기한 경험을 했다. 그래서 변수 이름을 aa, bb로 바꾸기까지 했다. 그런데 index가 1000을 넘어서도 안쪽 for문이 계속 돌면서 배열이 할당된 메모리를 넘어서도 계속 쓰기 때문에 배열 다음에 할당된 a와 b를 건드리는 것이었다.

https://www.acmicpc.net/problem/10989

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	vector<int> arr(10001);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		arr[temp]++;
	}
	for (int i = 1; i < 10001; i++) {
		for (int j = 0; j < arr[i]; j++) {
			cout << i << '\n';
		}
	}
	return 0;
}

https://www.acmicpc.net/problem/1927

C++의 priority_queue를 사용하면 된다.

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	priority_queue<int, vector<int>, greater<int>> q;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		if (num == 0) {
			if (q.empty()) cout << 0 << '\n';
			else {
				cout << q.top() << '\n';
				q.pop();
			}
		}
		else {
			q.push(num);
		}
	}
	return 0;
}

https://www.acmicpc.net/problem/10569

#include <iostream>
using namespace std;

int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int v, e;
		cin >> v >> e;
		cout << e - v + 2 << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/2864

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

int main() {
	string a, b;
	cin >> a >> b;
	string minA = "";
	string maxA = "";
	for (int i = 0; i < a.size(); i++) {
		if (a[i] == '6' || a[i] == '5') {
			minA += "5";
			maxA += "6";
		}
		else {
			minA += a[i];
			maxA += a[i];
		}
	}
	string minB = "";
	string maxB = "";
	for (int i = 0; i < b.size(); i++) {
		if (b[i] == '6' || b[i] == '5') {
			minB += "5";
			maxB += "6";
		}
		else {
			minB += b[i];
			maxB += b[i];
		}
	}
	int minResult = stoi(minA) + stoi(minB);
	int maxResult = stoi(maxA) + stoi(maxB);
	cout << minResult << " " << maxResult;
	return 0;
}

삼성 SW 역량 테스트 A형 기출문제

https://www.acmicpc.net/problem/16637

#include <iostream>
#include <vector>
#include <string>
using namespace std;
//16637번
vector<int> result;
vector<char> operators;
vector<int> operands;
int n;
long long maxResult = -2147483647;

void combination(vector<bool> visited, vector<int> endResult, int k, int num) {
	if (k == num) {
		vector<char> realOperators;
		vector<int> realOperands;
		realOperands.push_back(operands[0]);
		for (int i = 1; i < operands.size(); i++) {
			bool isIn = false;
			for (int j = 0; j < endResult.size(); j++) {
				if (endResult[j] == i) {
					isIn = true;
					break;
				}
			}
			if (isIn) {
				realOperators.push_back(operators[i - 1]);
				realOperands.push_back(result[i]);
				i++;
			}
			else {
				realOperators.push_back(operators[i - 1]);
				realOperands.push_back(operands[i]);
			}
		}
	
		int calculate = realOperands[0];
		for (int i = 0; i < realOperators.size(); i++) {
			switch (realOperators[i]) {
			case '*':
				calculate *= realOperands[i + 1];
				break;
			case '-':
				calculate -= realOperands[i + 1];
				break;
			case '+':
				calculate += realOperands[i + 1];
				break;
			}
		}
		if (calculate > maxResult) maxResult = calculate;
		return;
	}
	for (int i = 1; i < n / 2; i++) {
		if (num == 0) {
			if (!visited[i]) {
				visited[i] = true;
				endResult[num] = i;
				combination(visited, endResult, k, num + 1);
				visited[i] = false;
			}
		}
		else {
			if (!visited[i] && endResult[num - 1] < i - 1) {
				visited[i] = true;
				endResult[num] = i;
				combination(visited, endResult, k, num + 1);
				visited[i] = false;
			}
		}
	}
}


int main() {
	cin >> n;
	int operandIndex = 0;
	int operatorIndex = 0;
	string s;
	cin >> s;
	for (int i = 0; i < n; i++) {
		if (i % 2 == 0) {
			operands.push_back(s[i] - '0');
		}
		else {
			operators.push_back(s[i]);
		}
	}
	result = vector<int>(n / 2);
	for (int i = 0; i < n / 2; i++) {
		switch (operators[i]) {
		case '*':
			result[i] = operands[i] * operands[i + 1];
			break;
		case '+':
			result[i] = operands[i] + operands[i + 1];
			break;
		case '-':
			result[i] = operands[i] - operands[i + 1];
			break;
		}
	}
	if (n == 1) {
		cout << operands[0];
	}
	else {
		for (int i = 0; i <= (n - 3) / 2; i++) {
			vector<int> endResult(i);
			vector<bool> visited(n / 2);
			combination(visited, endResult, i, 0);
		}
		cout << maxResult;
	}
	return 0;
}

https://www.acmicpc.net/problem/5585

greedy 알고리즘의 아주 대표적인 문제이다.

#include <iostream>
using namespace std;

int main() {
	int cost;
	cin >> cost;
	int money[] = { 500, 100, 50, 10, 5, 1 };
	int change = 1000 - cost;
	int total = 0;
	int cnt = 0;
	while (true) {
		if (change == total) break;
		if (total + money[0] <= change) {
			total += money[0];
			cnt++;
		}
		else if (total + money[1] <= change) {
			total += money[1];
			cnt++;
		}
		else if (total + money[2] <= change) {
			total += money[2];
			cnt++;
		}
		else if(total + money[3] <= change) {
			total += money[3];
			cnt++;
		}
		else if (total + money[4] <= change) {
			total += money[4];
			cnt++;
		}
		else if (total + money[5] <= change) {
			total += money[5];
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}

이런 String 배열이 있을 때

public class ArrayTest {
    public static void main(String[] args) {
        String[] arr = {"apple", "banana", "cherry", "donut"};
        System.out.println(arr);
    }
}

이 배열을 출력하면

이렇게 이상한 글자가 출력된다.

public class ArrayTest {
    public static void main(String[] args) {
        String[] arr = {"apple", "banana", "cherry", "donut"};
        System.out.println(arr.toString());
    }
}

이렇게 arr.toString()을 출력해도 결과는 똑같다. toString()을 출력하는 것은 어떤 변수를 그냥 출력했을 때와 같다.

일반 배열은 그냥 출력하면 이렇게 이상하게 출력된다.

그럴 때 사용하는 것이 Arrays 클래스의 static 메소드 toString()이다.

import java.util.Arrays;

public class ArrayTest {
    public static void main(String[] args) {
        String[] arr = {"apple", "banana", "cherry", "donut"};
        System.out.println(Arrays.toString(arr));
    }
}

그러면 이렇게 우리가 원하는 대로 출력되는 것을 볼 수 있다.

Arrays와 같이 s로 끝나는 클래스들은 대부분 유용한 static 메소드들이 들어있는 유틸리티 클래스이다.

Arrays 클래스에서 자주 쓰이는 유용한 정적 메소드 중 하나가 sort() 메소드이다.

static 메소드이기 때문에 메소드 앞에 클래스이름.을 꼭 붙여서 Arrays.sort() 이렇게 사용해야 한다.

String[] arr = {"cherry", "Banana", "apple", "donut"};

이렇게 문자열들이 다 섞여있는 배열을 Arrays.sort() 메소드를 이용해서 정렬해보자.

import java.util.Arrays;

public class ArrayTest {
    public static void main(String[] args) {
        String[] arr = {"cherry", "Banana", "apple", "donut"};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

정렬이 되긴 했지만 대문자가 소문자보다 유니코드 값이 더 작기 때문에 Banana가 가장 앞에 온다.

대소문자를 구분하지 않고 정렬하고 싶다면 Arrays.sort() 메소드의 두 번째 인자에 Comparator 객체를 비교기준으로 넣어주면 된다.

import java.util.Arrays;

public class ArrayTest {
    public static void main(String[] args) {
        String[] arr = {"cherry", "Banana", "apple", "donut"};
        Arrays.sort(arr, String::compareToIgnoreCase);
        System.out.println(Arrays.toString(arr));
    }
}

그러면 이렇게 대소문자를 무시하고 알파벳 순서대로 정렬된 것을 볼 수 있다.

위 코드는 메소드 참조를 이용한 것이고 람다식을 이용하고 싶다면 다음과 같이 하면 된다.

import java.util.Arrays;

public class ArrayTest {
    public static void main(String[] args) {
        String[] arr = {"cherry", "Banana", "apple", "donut"};
        Arrays.sort(arr, (a, b) -> a.compareToIgnoreCase(b));
        System.out.println(Arrays.toString(arr));
    }
}

이 코드를 실행해도 결과는 같다.

람다식과 메소드 참조를 잘 모른다면 아래 두 글을 먼저 읽어보는 것을 추천한다.

https://breakcoding.tistory.com/4

https://breakcoding.tistory.com/183

람다식이나 메소드 참조를 이용하고 싶지 않다면 Comparator 클래스를 구현한 클래스를 만들어서 객체를 생성해서 sort() 메소드의 두 번째 인자로 넣어줄 수도 있다.

import java.util.Arrays;
import java.util.Comparator;

public class ArrayTest {
    public static void main(String[] args) {
        String[] arr = {"cherry", "Banana", "apple", "donut"};
        Arrays.sort(arr, new MyComparator());
        System.out.println(Arrays.toString(arr));
    }
}
class MyComparator implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return o1.compareToIgnoreCase(o2);
    }
}

이렇게 해도 결과는 똑같다.

그런데 역시 정적 배열이라서 출력할 때도 귀찮고 중간에 원소를 삭제하고 싶을 때 곤란하다. 따라서 이런 정적 배열을 동적배열(리스트)로 바꾸고 싶다면 어떻게 해야 할까?

이것 역시 유틸리티 클래스인 Arrays에 있는 static 메소드 asList() 메소드를 이용하면 된다.

import java.util.Arrays;
import java.util.List;

public class ArrayTest {
    public static void main(String[] args) {
        String[] arr = {"apple", "banana", "cherry", "donut"};
        List<String> list = Arrays.asList(arr);
    }
}

이렇게 하면 배열을 동적 배열인 List로 쉽게 바꿀 수 있다.

이 List를 ArrayList로 바꾸고 싶다면 다음과 같이 하면 된다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ArrayTest {
    public static void main(String[] args) {
        String[] arr = {"apple", "banana", "cherry", "donut"};
        List<String> list = Arrays.asList(arr);
        ArrayList<String> arrayList = new ArrayList<>(list);
    }
}

이렇게 ArrayList의 생성자의 인자로 넣어주면 된다.

동적 배열 ArrayList로 바꾸고 나면 정적 배열이었을 때보다 훨씬 할 수 있는 것들이 많다. 특히 스트림을 이용해서 굉장히 편리하게 처리할 수 있는 것들이 많아진다.

https://www.acmicpc.net/problem/10995

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		if (i % 2 == 1) cout << ' ';
		for (int j = 0; j < n; j++) {
			cout << '*' << ' ';
		}
		cout << '\n';
	}
	return 0;
}

https://www.acmicpc.net/problem/3980

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

int ability[11][11];
vector<int> result(11);
int maxTotal = 0;

void select(vector<bool> visited, int num) {
	if (num == 11) {
		int total = 0;
		for (int i = 0; i < 11; i++) {
			total += ability[i][result[i]];
		}
		if (total > maxTotal) maxTotal = total;
		return;
	}
	for (int i = 0; i < 11; i++) {
		if (ability[num][i] != 0 && !visited[i]) {
			visited[i] = true;
			result[num] = i;
			select(visited, num + 1);
			visited[i] = false;
		}
	}
}


int main() {
	cin.tie(NULL);
	vector<bool> person(11);
	vector<bool> position(11);
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		for (int i = 0; i < 11; i++) {
			for (int j = 0; j < 11; j++) {
				cin >> ability[i][j];
			}
		}
		vector<bool> visited(11);
		maxTotal = 0;
		select(visited, 0);
		cout << maxTotal << '\n';
	}
	return 0;
}