Willing

1. 문제 / 난이도 : SilverⅡ

www.acmicpc.net/problem/1058

2. 풀이 및 코드 설명

직접 친구이거나, 한 다리 건너서 아는 사람이면 전부 세는 문제. 친구관계를 먼저 설정한 후에 직접 친구인 사람들을 먼저 세고 그 사람들의 친구인 사람들까지 세서 카운트했다.

나랑 직접 친구이고, 한 다리 건너서 하는 친구 일 수도 있기 때문에 중복을 없애기 위해 set을 사용하기로 했다. 그냥 set은 자동으로 정렬이 되지만, 해당 문제는 정렬까지는 필요없고 중복이 없기만 하면 되기 때문에 unordered_set을 사용했다. 

(1) 초기화 및 설정

char temp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> temp;
			if (temp == 'Y') {
				map[i].push_back(j);
			}
		}
	}

• map[i] : i와 친구인 사람들

(2) unordered_set 사용해서 친구 세기

unordered_set<int> friends; // 직접 친구 + 한 다리 건너서 아는 사람
	for (int i = 0; i < N; i++) {
		for (auto &ele : map[i]) {
			friends.insert(ele); //직접 친구인 사람 추가
			for (auto &f : map[ele]) {
				if (f != i) friends.insert(f); // 그 사람과 친구인 사람 추가
			}
		}
		friends_cnt.push_back(friends.size()); 
		friends.clear();
	}

	sort(friends_cnt.begin(), friends_cnt.end()); // 카운트 정렬 
	cout << friends_cnt[N-1];

• friends : 직접 친구와 한 다리 건너서 아는 사람을 저장하는 set.
• friends_cnt : friends를 다 판별하고 난 뒤, 해당 set의 크기를 저장(set의 크기 = 아는 사람 수)
• 정렬 후 마지막 원소를 출력함으로써 제일 아는 사람이 많은 사람의 지인 수를 출력

3. 전체 코드

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

vector<int> map[50];
vector<int> friends_cnt;
int N;

int main() {
	cin >> N;
	char temp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> temp;
			if (temp == 'Y') {
				map[i].push_back(j);
			}
		}
	}

	unordered_set<int> friends;
	for (int i = 0; i < N; i++) {
		for (auto &ele : map[i]) {
			friends.insert(ele);
			for (auto &f : map[ele]) {
				if (f != i) friends.insert(f);
			}
		}
		friends_cnt.push_back(friends.size());
		friends.clear();
	}

	sort(friends_cnt.begin(), friends_cnt.end());
	cout << friends_cnt[N-1];
}

1. 문제 / 난이도 : Level 2

programmers.co.kr/learn/courses/30/lessons/42860?language=cpp

2. 풀이 및 코드

처음에는 굉장히 단순하게 오른쪽으로 이동하는 것보다 왼쪽으로 이동하는 게 적은 경우는 _A______형태로 name[1] == 'A' 일 때 뿐이라고 생각했다.

그래서 호다닥 풀어서 냈으나, 결과는 당연히 실패....

정확하게 풀기 위해서는 다음과 같은 반례를 고려해야 한다.

name = "BBBAAAB" / answer = 9
name = "ABABAAAAABA" / answer = 11

요점은 쭉 오른쪽으로 가다가 어느 순간 왼쪽으로 되돌아갈 때가 최적인 경우도 있다는 것!

결국 최적의 경우를 항상 선택해야하므로 Greedy 다.

(1) 초기화 및 설정

answer = 0;
int N = name.length(); // name 길이
int a_num = 'A' - '0'; // 'A'의 ASCII
string compare(N, 'A'); // 바꾸고자 하는 문자열

• a_num : 알파벳을 바꿀 때 위, 아래 버튼을 몇 번 눌러야하는지를 간편히 계산하기 위해 ASCII 코드를 이용.
  • ex ) 'A' = 48, 'B' = 49 이므로 ASCII 코드의 차를 이용해 버튼을 몇 번 눌러야하는지 계산할 수 있음.
• compare : 'A'를 N만큼 가지고 있는 문자열. 나중에 While 종료조건(compare == name)을 위해 사용.
  • ex ) name = 'JAZ'. 'compare' = 'AAA

(2) 최적 방향 찾기

int check_move(int N, int i, string name, string compare) {
	int left = 0; int right = 0; int index = 0;
	for (int j = i + 1; j < i + N; j++) { // 오른쪽으로 이동하는 경우
		if (name[j % N] != compare[j % N]) { // name과 compare가 달라질 때까지 이동
			right = j - i; // 오른쪽으로 몇 번 이동했는지
			index = j % N; // 그때의 인덱스
			break;
		}
	}

	for (int j = i - 1; j > i - N; j--) { // 왼쪽으로 이동하는 경우
		if (name[(N + j) % N] != compare[(N + j) % N]) {
			left = i - j;
			if(left < right) index = (N + j) % N; // 왼쪽으로 이동하는 경우가 더 최적이면, 해당 위치로 인덱스 갱신
			break;
		}
	}
	answer += min(left, right); // 왼쪽 이동과 오른쪽 이동 중에 더 작은 값 더하기
	return index; // 그 때의 인덱스 반환
}

• 왼쪽으로 이동하는 것과 오른쪽으로 이동하는 것 중 어느 방향으로 이동하는 것이 더 최적인지를 계산하기 위한 함수.
• 맨 끝 문자에서 +1 을 하면 맨 처음으로, 맨 처음 문자에서 -1을 하면 맨 끝으로 이동해야하기 때문에 모듈러 연산 사용.
  • ex ) N = 7, j = 8 이라면, name[j % N] = name[8 % 7] = name[1]
• 최적의 이동 수만큼 answer에 더해주고, 그 때 도착한 인덱스 반환

(3) 원하는 문자열이 될 때까지 갱신하며 반복

int i = 0;
	while (name != compare) {
		if(name[i] == compare[i]) i = check_move(N, i, name, compare); // 현재 인덱스의 name과 compare가 같으면 이동
		if (name[i] != 'A') {
			int move = (name[i] - '0') - a_num; // 얼마나 위 버튼을 눌러야 하는지
			if (move > 13) move = 26 - move; // 중간값인 13보다 크다면 아래 버튼을 누르는 게 이득
			answer += move;
			compare[i] = name[i]; // compare 갱신
		}
	}
	return answer;

3. 전체 코드

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

int answer;

int check_move(int N, int i, string name, string compare) {
	int left = 0; int right = 0; int index = 0;
	for (int j = i + 1; j < i + N; j++) {
		if (name[j % N] != compare[j % N]) {
			right = j - i;
			index = j % N;
			break;
		}
	}

	for (int j = i - 1; j > i - N; j--) {
		if (name[(N + j) % N] != compare[(N + j) % N]) {
			left = i - j;
			if(left < right) index = (N + j) % N;
			break;
		}
	}
	answer += min(left, right);
	return index;
}

int solution(string name) {
	answer = 0;
	int N = name.length();
	int a_num = 'A' - '0';
	string compare(N, 'A');

	int i = 0;
	while (name != compare) {
		if(name[i] == compare[i]) i = check_move(N, i, name, compare);
		if (name[i] != 'A') {
			int move = (name[i] - '0') - a_num;
			if (move > 13) move = 26 - move;
			answer += move;
			compare[i] = name[i];
		}
	}
	return answer;
}

1. 문제 / 난이도 : Level 3

programmers.co.kr/learn/courses/30/lessons/59042

2. 풀이 및 전체 코드

SQL문제들은 책정된 난이도보다 체감난이도는 훨씬 평이한 편. 해당 문제도 어렵지 않게 풀 수 있었음.

JOIN 카테고리로 분류되어있었는데 결과적으로는 JOIN을 사용하지 않고 NOT IN을 이용해서 풀었다.

SELECT 
  ANIMAL_ID, 
  NAME
FROM ANIMAL_OUTS
WHERE 
  ANIMAL_ID NOT IN (
    SELECT ANIMAL_ID 
    FROM ANIMAL_INS
  );

• 입양은 간 기록은 있는데, 보호소에 들어온 기록이 없다 => ANIMAL_OUTS 테이블에는 있지만, ANIMAL_INS에는 없다.

1. 문제 / 난이도 : GoldⅡ

www.acmicpc.net/problem/2623

2. 풀이 및 코드 설명

처음에는 어떻게 풀어야하지...? 하고 고민하다가 결국 알고리즘 분류에 위상정렬이라는 키워드가 있는 것을 보고 간단한 위상정렬 구현으로 쉽게 풀었다.

순서가 정해져 있는 노드들을 전부 방문해야 한다면 => 위상 정렬을 사용할 수 있다는 점을 잊지 말자!

(1) 초기화 및 설정

	cin >> N >> M;
	while (M--) {
		cin >> K;
		int prev;
		for (int i = 0; i < K; i++) {
			int current;
			if (i == 0) cin >> prev; // i가 0이라면 맨 처음 값이므로 prev 초기화
			else {
				cin >> current;
				cnt[current] = cnt[current] + 1; // 진입 vertex 수 cnt 증가
				arr[prev].push_back(current); // prev -> current로 이어진 그래프 생성
				prev = current; // prev 갱신
			}
		}
	}

• arr : 각 노드마다 연결된 노드들의 정보들을 저장
• cnt : 위상정렬을 구현하기 위한 배열. 각 노드당 진입 vertex의 개수를 저장

(2) 큐 초기값

queue<int> q; // 위상정렬 큐
	for (int i = 1; i < N + 1; i++) {
		if (cnt[i] == 0 && visit[i] == 0) { // 아직 방문하지 않았고, 진입 vertex 수가 0이라면
			q.push(i); // 해당 노드 큐에 추가
			visit[i] = 1; // visit값 갱신
		}
	}

(3) 위상정렬

	while (!q.empty()) {
		int current = q.front(); // 현재 노드
		q.pop();
		result.push_back(current); // result 배열에 추가

		for (int i = 0; i < arr[current].size(); i++) {
			cnt[arr[current][i]]--; // 현재 노드와 연결된 노드 모두 진입 vertex 수 하나씩 감소
		}

		for (int i = 1; i < N + 1; i++) {
			if (cnt[i] == 0 && visit[i] == 0) { // 갱신된 노드들 중 진입 vertex 수가 0이고 아직 방문하지 않았다면
				q.push(i);
				visit[i] = 1;
			}
		}
	}

• 큐가 빌 때까지 위상정렬 진행

(4) 출력

	if (result.size() != N) cout << 0;
	else {
		for (int i = 0; i < N; i++) cout << result[i] << endl;
	}

• result 크기와 N이 같지 않다는 것 : 중간에 순환이 생겨 위상정렬이 제대로 이루어지지 않았다는 것 = 순서를 정할 수 없다는 말
• 위의 조건이 아닐때는 result 순서대로 출력

3. 전체 코드

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

int N, M, K;
vector<vector<int>> arr(1001);
int cnt[1001];
int visit[1001];
vector<int> result;

int main() {
	cin >> N >> M;
	while (M--) {
		cin >> K;
		int prev;
		for (int i = 0; i < K; i++) {
			int current;
			if (i == 0) cin >> prev;
			else {
				cin >> current;
				cnt[current] = cnt[current] + 1;
				arr[prev].push_back(current);
				prev = current;
			}
		}
	}

	queue<int> q;
	for (int i = 1; i < N + 1; i++) {
		if (cnt[i] == 0 && visit[i] == 0) {
			q.push(i);
			visit[i] = 1;
		}
	}
	
	while (!q.empty()) {
		int current = q.front();
		q.pop();
		result.push_back(current);

		for (int i = 0; i < arr[current].size(); i++) {
			cnt[arr[current][i]]--;
		}

		for (int i = 1; i < N + 1; i++) {
			if (cnt[i] == 0 && visit[i] == 0) {
				q.push(i);
				visit[i] = 1;
			}
		}
	}

	if (result.size() != N) cout << 0;
	else {
		for (int i = 0; i < N; i++) cout << result[i] << endl;
	}
}