꾸준히 운동하는 개발자

[문제 링크]

https://programmers.co.kr/learn/courses/30/lessons/60057

[문제 풀이]

이름 그대로 문자열을 압축하는 문제였다. 문자열 처리가 좀 귀찮은 문제였다.

압출할 수 있는 길이에 따라 압축한 문자열의 길이를 비교하여 가장 작은 문자열의 길이를 리턴하는 것이 문제이다.

첫 번째 예제의 문자열을 길이 1로 압축한다면 "2a2ba3c"가 되고 이 문자열의 길이가 7로 가장 작은 길이가 된다.

두 번째 예제의 문자열을 길이 2로 압축한다면 "2ab2cd2ab2cd"가 되고 이 문자열의 길이는 12이다.

두 번째 에제의 문자열을 길이 8로 압축한다면 "2ababcdcd"가 되고 이 문자열의 길이가 9로 가장 작은 길이가 된다.

그럼 여기서 우리는 압축할 수 있는 길이를 1부터 다 찾아봐야한다는 사실을 알 수 있다.

하지만 1부터 어디까지 찾아봐야할까? 위에 예제들을 보면 압축할 수 있는 길이에서 절반을 압축하는 것을 볼 수 있다. 즉, 최대로 압출할 수 있는 길이는 주어진 문자열의 절반이다.

두 번째 예제의 문자열을 다시 보자. 주어진 문자열의 길이는 16이다. 이 길이의 절반은 8이다. 여기서 8보다 큰 숫자로 압축을 시도해봤자 압축이 되지 않는다.

이제 1부터 주어진 문자열 길이의 절반까지 반복문을 돌면서 가장 짧은 길이의 압축된 문자열 길이를 찾으면 된다.

여기서 문자열을 압축하는 과정을 구현하는게 생각보다 복잡했다.

본인은 우선 처음에 압축할 수 있는 길이에 따른 기준 문자열을 정하였다.

그리고 그 다음 인덱스부터 압축할 수 있는 길이만큼을 비교 문자열로 정하였다.

기준 문자열과 비교 문자열이 같다면 카운트를 해준다.

기준 문자열과 비교 문자열이 다르다면 두 가지 경우로 나뉜다.

지금까지 카운트된 횟수가 1보다 크다면 카운트 숫자를 스트링으로 변환한 뒤 숫자와 기준 문자열을 이어 붙이고 벡터에 저장하였다.

카운트 횟수가 1이라면 숫자를 생략하라고 했기 때문에 기준 문자열만 벡터에 저장하였다. 그리고 기준 문자열을 비교 문자열로 바꿔 준다. 그리고 연속으로 같은 문자열이 나온 게 아니기 때문에 카운트는 다시 1로 초기화한다.

이렇게 반복문이 끝나면 아직 벡터에 넣지 못한 문자열이 남을 수 있다. 그래서 반복문이 끝나고 같은 로직으로 카운트가 1보다 크면 숫자 + 기준 문자열을 넣어주고 1이라면 기준 문자열만 넣어준다.

마지막으로 벡터에 저장된 문자열을 하나로 이어 붙인 뒤에 길이를 업데이트 해준다.

이 문제에서 가장 많이 틀리는 케이스는 아마 문자열의 길이가 1일 때일 것이다.

문자열의 길이가 1일 때는 예외처리를 해주어야 한다.

[소스 코드]

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

int solution(string s) {
    int size = 1000;
	string tmp;
	string tmp2;
    vector<string> v;
	int s_size = s.size();
	for (int i = 1; i <= s_size / 2; i++) {
		bool flag = true;
		tmp = s.substr(0, i);
		int cnt = 1;
		int idx = 0;
		for (int j = i; j < s.size(); j++) {
			tmp2 = s.substr(j, i);
			j += (i - 1);

			if (tmp == tmp2) {
				cnt++;
			}
			else {
				if (cnt > 1) {
					string num = to_string(cnt);
					v.push_back(num + tmp);
				}
				else {
					v.push_back(tmp);
				}
				tmp = tmp2;
				cnt = 1;
			}

		}
		if (cnt > 1) {
			string num = to_string(cnt);
			v.push_back(num + tmp);
		}
		else {
			v.push_back(tmp);
		}
		string str;
		for (int j = 0; j < v.size(); j++) {
			str += v[j];
		}

		int str_size = str.size();
		size = min(size, str_size);
		tmp = "";
		v.clear();
	}
    if(s_size == 1) return 1;
    else return size;
}

[문제 링크]

https://programmers.co.kr/learn/courses/30/lessons/64061

[문제 풀이]

2019년 카카오 개발자 겨울 인턴십 코딩 테스트 문제이다.

제목에서부터 알 수 있듯이 인형 뽑기 게임을 하는데 바구니에 인형을 넣을 때 맨 위에 있는 인형과 넣는 인형이 같으면 터진다.

문제에 그림이 주어지기 때문에 문제를 이해하는 것은 어렵지 않다.

본인은 문제 설명을 보고 바로 스택을 떠올렸다.

인형을 위에서부터 뽑는다고 했기 때문에 번호마다 하나의 스택으로 생각하면 문제를 풀기가 편할 것이라고 생각했다.

그림을 보면 1번 격자에는 위에서부터 어피치와 튜브가 있다.

1번 격자를 스택으로 본다면 처음에 튜브를 넣고 어피치를 넣었을 것이다.

2번 격자를 스택으로 본다면 처음에 프로도를 넣고 무지를 2번 넣었을 것이다.

이런 식으로 해당하는 격자를 스택으로 표현하였고, 0이 아닌 경우에만 스택에 넣었다. (0은 빈 공간)

밑에서부터 넣어줘야 하기 때문에 1번 격자의 아래서부터 탐색을 진행하였다.

여기서 인형은 숫자로 표현되었다. 1은 네오, 2는 무지, 3은 튜브, 4는 어피치, 5는 프로도다.

매개 변수로 주어지는 board를 통해 스택으로 변환하였다면 이제 moves 변수를 통해 크레인을 움직이면서 바구니에 인형을 넣어줘야 한다.

여기서 바구니 또한 같은 구조이기 때문에 스택으로 선언하였다.

moves 변수에 들어있는 번호에 해당하는 스택에서 위에 있는 인형을 뽑는다.

여기서 해당 스택이 비어있다면 아무런 일도 일어나지 않는다고 했기 때문에 이 부분을 처리해줘야 한다.

바구니에 두 개의 같은 인형이 연속으로 쌓이면 사라진다고 했기 때문에 바구니에 인형을 넣을 때마다 바구니의 위에 있는 인형과 지금 넣으려고 하는 인형이 같은지 확인해야 한다. 같으면 카운트를 2 증가시켜준다. 2를 증가시키는 이유는 이미 바구니에 있는 인형과 지금 넣으려고 하는 인형이 사라지는 것이기 때문이다.

여기서 주의해야 할 부분이 있다면 바구니가 비어있을 때는 예외처리를 해줘야 한다.

마지막으로 스택에서 꺼낸 인형을 삭제해주면 된다.

참고로 본인은 스택의 인덱스를 0부터 시작하였다.

[소스 코드]

#include <string>
#include <vector>
#include <stack>
using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int n = board.size();
    stack<int> s[31];
    stack<int> bucket;
    int answer = 0;
    int idx = 0;
	for (int i = 0; i < n; i++) {
		for (int j = n - 1; j >= 0; j--) {
			if(board[j][i] != 0) s[idx].push(board[j][i]);
		}
		idx++;
	}
	
	for (int i = 0; i < moves.size(); i++) {
		int loc = moves[i];
		if (s[loc - 1].empty()) continue;

		if (bucket.empty()) {
			bucket.push(s[loc - 1].top());
		}
		else {
			if (bucket.top() == s[loc - 1].top()) {
				bucket.pop();
				answer += 2;
			}
			else {
				bucket.push(s[loc - 1].top());
			}
		}
		s[loc - 1].pop();
	}
    return answer;
}

2020 NAVER CAMPUS HACKDAY (네이버 핵데이) 온라인 코딩 테스트는 2020년 4월 11일 토요일 오전 11시부터 2시간 동안 진행되었다.

총 알고리즘 3문제를 120분 동안 푸는 것이기 때문에 무난한 난이도가 예상되었다. 코딩 테스트는 참고용으로 사용한다고 했기 때문에 가벼운 마음으로 보려고 했다.

사진에 나와 있는 것처럼 이번 네이버 핵데이 온라인 코딩 테스트는 프로그래머스 플랫폼에서 진행되었다.

1번 문제는 무난한 구현 문제였다. 문자열을 이용한 구현 문제였는데 문자열을 이용하는 구현 문제를 어려워하는 본인도 무난히 풀었기 때문에 난이도는 쉬운 편에 속한다고 볼 수 있다. 물론 테스트 케이스가 많이 주어지지 않기 때문에 정확히 맞춘지는 모르겠다. 푸는데 한 20분 정도 걸린 것 같다.

2번 문제도 문자열 문제였다. C++ 언어로 문자열 문제를 풀 때 가장 곤란한 것은 띄어쓰기가 포함된 문자열이 나올 때이다. 이 문제도 띄어쓰기가 포함된 문자열이 주어져서 생각보다 오래 푼 것 같다. 이후에는 맵을 이용 하여 문자의 개수를 카운트하여 푼 기억이 난다. 이 문제는 한 30분 정도 걸린 것 같다.

3번 문제는 정말 어려웠다. 아마도 문제의 알고리즘 유형은 DP라고 생각하는데 정확히 모르겠다. 문제에서 10억 가까이 되는 수로 나눈 수를 리턴하라고 했기 때문에 그렇게 생각했다. 실제로 문제도 DP 느낌이 많이 났다. DP말고도 여러 방면으로 풀이를 생각해봤지만 1시간 동안 고민해봐도 풀이가 떠오르지 않았다. 아마 이 3번을 푼 사람은 나중에 인턴십 참가에도 영향을 주지 않을까 생각이 들 정도로 어려웠다.

시험이 끝나고 역시나 3번이 어려웠다는 반응이 대부분이였다. 1, 2번은 무난한 난이도였는지 1, 2번에 대한 얘기는 거의 없었고 3번 얘기만 많이 하였다.

2솔이라고 생각하고 합격을 기대해봐야 할 것 같다.

[문제 링크]

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

[문제 풀이]

삼성 시뮬레이션 문제이다.

이 문제는 처음에 이해하는데만 20분 이상 걸린 것 같다. 문제 설명이 부실한 느낌?을 많이 받았다.

이 문제에서는 조건들이 굉장히 많이 나오는데 결국 중요한 것은 N X N인 격자 내에서 5개의 선거구를 만들 수 있는 조건을 충족하면서 각 선거구 인구의 최댓값에서 최솟값을 뺀 값이 최솟값이 되어야 한다.

여기서 중요한 것은 5개의 선거구를 만들 수 있는 조건이다.

문제 조건 중 일부를 보면 경계선을 만들 수 있는 조건이 나와 있다. 이 경계선과 경계선 안에 포함되어 있는 곳이 5번 선거구가 된다. 그렇다면 이 5번 선거구를 어떻게 구현할 것인지 생각해봐야 한다.

본인은 입력으로 주어지는 선거구의 인구를 MAP이라는 2차원 배열에 저장하였다. 그리고 선거구를 나눠주기 위해 TEMP라는 2차원 배열을 사용하였다.

기본적인 흐름은 완전 탐색이다. 완전 탐색이기 때문에 i와 j가 0부터 n-1까지 탐색한다. 그리고 5개의 선거구를 만들 수 있는 d1과 d2인 경우에 각 선거구를 나눈 뒤 합을 계산한다.

여기서 어려웠던 것은 d1과 d2의 범위 설정이다. d1과 d2의 길이를 잘 설정해야 범위 안에 들어오는 경계선을 만들 수 있는데 생각보다 쉽지 않았다.

기본적으로 d1의 길이에 따라 왼쪽 대각선의 길이가 정해지고 d2의 길이에 따라 오른쪽 대각선의 길이가 정해진다.

첫 번째 예시에서 d1이 3이고 d2가 2인 경우를 생각해보자. 5개의 선거구로 나눌 수 있을까? 나눌 수 있다.

하지만 d1이 4가 되는 순간 d2의 길이와 관계없이 범위를 벗어나게 된다. 그렇다면 첫 번째 예시에서 d1의 최대 길이는 3일 것이다. 여기서 또 3은 어떻게 구할 수 있을까?

본인은 인덱스를 0부터 시작했기 때문에 첫 번째 예시에서 기준점은 (1,3)이다. 기준점을 보면 알 수 있듯이 d1은 현재 기준점의 y좌표만큼 갈 수 있다. 현재 기준점의 y좌표 길이보다 커지면 범위를 벗어나는 것이다.

그렇다면 d2는 어떨까?

이번에는 두 번째 예시를 보자. d2가 2인 경우가 최대 길이라는 것을 쉽게 알 수 있다. d2가 3이 되는 순간 범위를 벗어나기 때문이다. 그러면 d2의 최대 길이가 2인 것은 어떻게 구할 수 있을까?

현재 n은 7이고 기준점은 (1,4)이다. 여기서 n-y를 하게 되면 3이 된다. 이 뜻은 n-y 전까지가 d2의 최대 길이 범위가 된다는 것이다.

d1과 d2의 최대 길이 범위를 구했기 때문에 남은 것은 선거구를 나눠주는 방법과 각 선거구의 인구를 합하는 방법이다.

선거구를 나눠주기 전에 할 일은 경계선이 범위 안에 들어오는지 체크하는 것이다.

본인은 꼭짓점 4개를 기준으로 선거구를 나눌 것이기 때문에 이 꼭짓점들 중에 하나라도 범위를 벗어나면 경계선을 만들지 못한다고 판단하였다.

첫 번째 예시를 다시 봤을 때 꼭짓점을 사진과 같이 번호를 붙였다.(인덱스는 0부터 시작하므로 0,1,2,3)

각 꼭짓점의 좌표는 문제에 제시되어있다.

1번은 (x, y) , 2번은 (x + d1, y - d1), 3번은 (x + d2, y + d2), 4번은 (x + d2 + d1, y + d2 - d1)이다.

1번은 기준점이기 때문에 항상 범위 안에 있으므로 범위를 체크할 필요가 없다.

그러므로 2번, 3번, 4번 꼭짓점이 범위 안에 들어오면 벡터에 각 꼭짓점 좌표를 넣어준다.

위 그림 같은 경우 v[0] = {1,3} , v[1] = {3,1} , v[2] = {3,5}, v[3] = {5,3} 이런 식으로 저장한다.

이제 선거구를 나눠줘야 한다.

우선 TEMP 배열을 모두 5로 초기화를 시켜준다. 그 이후에 4번 반복문을 돌면서 1, 2, 3, 4번 선거구를 정할 것이다.

1번 선거구의 경우에 행은 2번 꼭짓점 전까지, 열은 1번 꼭짓점까지 포함한다.

2번 선거구의 경우에 행은 2번 꼭짓점까지, 열은 n-1까지 포함한다.

3, 4번 선거구는 아래서부터 탐색한다.

3번 선거구의 경우에 행은 2번 꼭짓점까지, 열은 4번 꼭짓점 전까지 포함한다.

4번 선거구의 경우에 행은 3번 꼭짓점 전까지, 열은 n-1까지 포함한다.

각 선거구마다 규칙이 다르기 때문에 범위를 잘 설정해가며 선거구를 나눠야 한다.

1번 선거구는 1번 선거구의 행이 1번 꼭짓점의 행과 같거나 커지면 열의 범위를 하나씩 줄이면 된다.

2번 선거구는 2번 선거구의 행이 1번 꼭짓점의 행보다 커지면 열의 시작 지점을 한 칸씩 앞으로 간다.

3번 선거구는 3번 선거구의 행이 4번 꼭짓점의 행보다 작을 때 열의 범위를 하나씩 줄이면 된다.

4번 선거구는 4번 선거구의 행이 4번 꼭짓점의 행과 같거나 작을 때 열의 시작 지점을 한 칸씩 앞으로 간다.

이 부분은 코드를 보면 이해가 쉬울 것이다.

이런 식으로 선거구를 다 나눴으면 각 선거구의 인구의 합을 구해야 한다.

선거구의 인구의 최댓값에서 최솟값을 빼야 하기 때문에 본인은 각 선거구의 합을 배열에 저장한 뒤 정렬을 통해 그 차이를 구하였다. 이 차이가 한 번 기준점을 정하고 경계선을 정상적으로 그렸을 때 각 선거구 인구의 최댓값과 최솟값의 차이기 때문에 min 함수를 이용하여 그 차이를 업데이트해준다. 그리고 마지막에 최솟값을 출력해주면 된다.

[소스 코드]

#include <bits/stdc++.h>
using namespace std;
int n;
int MAP[21][21];
int TEMP[21][21];
vector<pair<int, int>> v;
int SUM[6];
int MIN = 2147483647;
bool check(int x, int y, int d1, int d2) {
	if (x + d1 >= n || y - d1 < 0) return false;
	else if (x + d2 >= n || y + d2 >= n) return false;
	else if (x + d2 + d1 >= n || y + d2 - d1 < 0) return false;
	return true;
}
void calculate() {
	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			SUM[TEMP[i][j]] += MAP[i][j];
		}
	}
	sort(SUM, SUM + 6);
	sum = SUM[5] - SUM[1];
	MIN = min(MIN, sum);
	fill(SUM, SUM + 6, 0);
}
void setting() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			TEMP[i][j] = 5;
		}
	}
}
void go() {
	setting();
	int cnt = 0;
	for (int i = 0; i < v[1].first; i++) {
		if (i >= v[0].first) cnt++;
		for (int j = 0; j <= v[0].second - cnt; j++) {
			TEMP[i][j] = 1;
		}
	}
	cnt = 0;
	for (int i = 0; i <= v[2].first; i++) {
		if (i > v[0].first) cnt++;
		for (int j = v[0].second + 1 + cnt; j < n; j++) {
			TEMP[i][j] = 2;
		}
	}
	cnt = 0;
	for (int i = n - 1; i >= v[1].first; i--) {
		if (i < v[3].first) cnt++;
		for (int j = 0; j < v[3].second - cnt; j++) {
			TEMP[i][j] = 3;
		}
	}
	cnt = 0;
	for (int i = n - 1; i > v[2].first; i--) {
		if (i <= v[3].first) cnt++;
		for (int j = v[3].second + cnt; j < n; j++) {
			TEMP[i][j] = 4;
		}
	}
	v.clear();
}
void INPUT() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> MAP[i][j];
		}
	}
}
void solve() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int d1 = 1; d1 <= j; d1++) {
				for (int d2 = 1; d2 < n - j; d2++) {
					if (check(i, j, d1, d2)) {
						v.push_back({ i,j });
						v.push_back({ i + d1, j - d1 });
						v.push_back({ i + d2, j + d2 });
						v.push_back({ i + d1 + d2, j - d1 + d2 });
						go();
						calculate();
					}
				}
			}
		}
	}
	cout << MIN;
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	INPUT();
	solve();
	return 0;
}

2020 상반기 라인 공채 온라인 코딩 테스트는 2020년 4월 5일 오전 10시부터 12시 30분까지 진행되었다.

라인의 온라인 코딩 테스트는 프로그래머스에서 진행되었다.

총 6문제였고, 시간은 150분이 주어졌다.

이번 공채 문제들의 난이도는 쉬운 것은 아니였지만 그렇다고 엄청나게 어려운 난이도는 아니였다고 생각한다.

1번 문제는 1번 답게 조금 쉬웠다. 본인은 스택으로 풀었는데 여러 가지 방법으로 풀 수 있을 것 같다. 하지만 문제 조건을 하나를 놓쳐서 틀렸을 것 같다. 문제 조건은 항상 빠짐 없이 확인해야하는데 급하다보니 실수를 하는 것 같다.

2번 문제는 딱히 풀이 방법이 떠오르지 않아서 완전탐색으로 풀었다. 테스트 케이스는 맞았지만 아마 효율성에서 점수를 못 받았을 것 같다. 문제 자체는 어렵지 않았다.

3번 문제는 딱 처음 봤을 때 조합으로 풀어야겠다고 생각했다. 하지만 입력 조건이 30만 정도여서 조합으로 풀면 시간 초과가 난다. 하지만 그걸 알고도 다른 풀이가 생각나지 않아서 그냥 제출했다. 푼 사람들 말로는 이분 탐색, 투포인터 알고리즘으로 풀 수 있다고 한다.

4번 문제는 맵을 이용해서 풀었다. 문제를 보자마자 맵으로 풀어야겠다는 생각이 들었고 맵을 사용할 줄 안다면 쉽게 풀었을 것 같다.

5번 문제는 순차탐색 하면서 정렬을 이용해서 풀었다. 프로그래머스가 시간제한을 몇 초로 주는지 모르지만 넉넉히 준다는 얘기를 들은 적이 있어서 그냥 풀었다. 이것도 다른 사람들 말을 들어보면 맵이나 셋으로 풀 수 있다고 하는 것 같다. 그게 맞다면 나의 코드는 효율성에서 거의 0점을 받았을 것 같다.

6번은 문자열 문제였다. 문자열 처리는 정말 어려운 것 같다. 이런 문자열 문제는 많이 접해보지 않았고 구현할 시간도 없어서 제대로 풀지 못했다. 이 문제만은 문제에서 부분 점수가 있다고 명시되어 있었다.

결과는 역시 불합격이었다. 대부분 반응은 완벽한 4솔정도가 합격 컷이라고 하는 것 같다.

이번 라인 코딩 테스트를 통해서 투포인터 알고리즘이라는 것이 있다는 것을 알게 되었다. 그리고 역시나 문자열 처리에 약한 모습을 보여줬기 때문에 이런 부분을 보완해야 할 것 같다.

이스트소프트는 다른 기업과 다르게 정해진 시간에 보는 것이 아니라 사진처럼 본인이 원하는 시간에 볼 수 있었다.

3월 28일~3월29일인데 제목이 3월 30일인 이유는 서버가 터졌기 때문이다.

29일에 시험을 보려고 했는데 서버가 터졌고 문의 결과 30일까지 기간을 연장해준다고 했다.

2020 상반기 이스트소프트 온라인 코딩 테스트는 코딜리티에서 진행되었다.

코딜리티는 외국 플랫폼이여서 문제들이 전부 영어다.

https://www.codility.com/

코딜리티에서 로그인을 하면 코딜리티에서 제공하는 문제들을 풀어볼 수 있다.

참고로 코딜리티에서 진행하는 코딩 테스트의 문제들은 복사가 안된다.

문제는 알고리즘만 4문제였고, 3시간 동안 풀 수 있었다.

모든 문제가 그냥 구현이었다. 특별한 알고리즘이 쓰인 문제는 없었다.

2번은 맵을 이용하면 시간복잡도를 줄일 수 있을 것 같다.

가장 힘들었던 문제는 4번이었다.

4번은 문자열 문제였는데 파이썬으로 풀면 쉽게 풀 수 있을 것 같았다.

하지만 본인은 C++ 유저이기 때문에 정말 힘들게 풀었다.

문자열 관련 문제에 약하기도 하고 다른 언어에 비해 C++이 문자열 처리는 조금 어렵기 때문이다.

출력하는 것도 정말 어려워서 이 문제만 2시간 가량 푼 것 같다.

어쨌든 4문제를 모두 풀긴했지만 정확히 맞은지는 모른다. 테스트 케이스가 1-2개밖에 주어지지 않았다.

모든 문제를 풀어서 조금은 기대했지만 결과는 불합격이었다. 아마 효율성까지 본 것 같았다.

[문제 링크]

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

[문제 풀이]

삼성 기출 시뮬레이션 문제이다.

다른 삼성 기출문제들보다는 난이도가 쉬운 편이라고 생각한다.

톱니바퀴가 4개있고 각 톱니바퀴는 8개의 톱니로 이루어져 있다. 그리고 톱니는 N극(0) 또는 S극(1)으로 이루어져 있다.

각 톱니바퀴는 맞닿은 극이 서로 다르면 회전을 한다. 즉, n번째 톱니바퀴의 2번째 톱니와 n+1번째 톱니바퀴의 6번째 톱니의 극이 서로 다르면 회전을 한다. (톱니는 0부터 시작한다고 가정)

톱니바퀴를 K번 회전시킨 후 조건에 따라 점수를 더한다.

회전 후 각 톱니바퀴의 12시 방향이 S극이면 점수를 더하는데 1번 톱니바퀴는 1점, 2번 톱니바퀴는 2점, 3번 톱니바퀴는 4점, 4번 톱니바퀴는 8점이다. 합산한 점수를 출력하면 된다.

왼쪽 톱니바퀴부터 1번, 2번, 3번, 4번 톱니바퀴이다.

그림과 같은 톱니바퀴가 주어진다면 아래와 같은 숫자로 나타낼 수 있다.

10101111
01111101
11001110
00000010

그 다음엔 K가 주어지고 회전시킬 톱니바퀴 번호와 방향을 입력받는다.

예를 들어 2 1이면 2번 톱니바퀴를 시계방향으로 돌리는 것이다. 1 -1이면 1번 톱니바퀴를 반시계 방향으로 돌리는 것이다.

본인은 문제를 쉽게 풀기 위해 톱니바퀴를 덱으로 선언하여 풀었다.

문제에는 톱니바퀴가 1번부터 시작했지만 본인은 0번부터 시작하였다. 그래서 처음 톱니바퀴 번호를 입력받을 때 -1을 해준다.

회전할 톱니바퀴를 찾기 위해 벡터와 큐를 사용하였다. 또한, 톱니바퀴의 방문 체크를 해주었다.

여기서 중요한 것은 K번 입력받는 톱니바퀴들은 그 방향으로 무조건 회전을 한다. 인접한 톱니바퀴와 극이 같다고 해서 회전을 안 하는 것이 아니다.

그리고 이 문제는 회전하기 전의 상태에서 맞닿은 극이 서로 다르면 서로 다른 방향으로 회전한다. 즉, 입력받은 톱니바퀴를 해당 방향으로 회전시킨 뒤 인접한 톱니바퀴와 맞닿은 극이 서로 다른지를 보는 것이 아니다. 본인은 이 부분에서 문제를 잘못 이해하여 계속 틀렸다.

다시 문제로 돌아와서 처음 입력받는 톱니바퀴 번호와 방향을 큐와 벡터에 넣어준다. 큐는 회전할 톱니바퀴를 찾기 위해서 사용하고, 벡터는 톱니바퀴 정보를 저장하고 실제로 회전시키기 위해 사용한다.

큐가 빌 때까지 반복하면서 회전할 큐를 찾는다. 여기서 톱니바퀴가 0번째가 아닌 경우, 3번째가 아닌 경우로 나뉜다.

0번째가 아닌 경우는 현재 톱니바퀴와 그 왼쪽 톱니바퀴의 맞닿은 극이 서로 다른지, 방문한 톱니바퀴인지 체크한다.

3번째가 아닌 경우는 현재 톱니바퀴와 그 오른쪽 톱니바퀴의 맞닿은 극이 서로 다른지, 방문한 톱니바퀴인지 체크한다.

방문하지 않았고, 맞닿은 극이 서로 다르면 큐와 벡터에 톱니바퀴 번호와 반대 방향(방향 * -1)을 넣어준 뒤 해당 톱니바퀴를 방문 체크해준다.

큐를 통해 회전할 톱니바퀴를 다 찾았으면 반복문을 빠져나오고 벡터에 저장된 회전할 톱니바퀴들을 실제로 회전시킨다.

톱니바퀴는 덱으로 선언했기 때문에 숫자를 앞뒤로 넣고 빼는 것이 쉽다.

시계 방향인 경우 뒤에 숫자를 저장한 뒤 삭제하고 저장한 숫자를 앞에 넣어주면 된다.

반시계 방향인 경우 앞에 숫자를 저장한 뒤 삭제하고 저장한 숫자를 뒤에 넣어주면 된다.

이 작업을 K번 반복한 뒤 마지막에 점수를 더해주면 된다.

K번 반복할 때 방문 체크 배열을 초기화해주고 벡터를 초기화해줘야 한다.

[소스 코드]

#include <bits/stdc++.h>
using namespace std;
int k; //회전 횟수
bool check[4];
deque<int> dq[4]; // 톱니바퀴 상태 저장 및 회전하기 위한 덱

queue<pair<int, int>> q; // 회전할 톱니바퀴를 저장하기 위한 큐
vector<pair<int, int>> v; // 회전할 톱니바퀴들을 실제로 방향에 따라 회전시키기 위한 벡터
void rotate() {
	for (int i = 0; i < v.size(); i++) { // 톱니바퀴 회전 
		int cur_num = v[i].first;
		int cur_d = v[i].second;
		if (cur_d == 1) { // 시계 방향이면
			int tmp = dq[cur_num].back(); // 현재 톱니바퀴의 마지막 숫자를 tmp에 저장
			dq[cur_num].pop_back(); // 현재 톱니바퀴의 마지막 숫자 삭제
			dq[cur_num].push_front(tmp); // 현재 톱니바퀴의 앞에다가 tmp 삽입
		}
		else { // 시계 반대방향이면
			int tmp = dq[cur_num].front(); // 현재 톱니바퀴의 첫번째 숫자를 tmp에 저장
			dq[cur_num].pop_front(); // 현재 톱니바퀴의 첫번째 숫자 삭제
			dq[cur_num].push_back(tmp); // 현재 톱니바퀴의 뒤에다가 tmp 삽입
		}
	}
}
void check_rotate() {
	cin >> k;
	for (int i = 0; i < k; i++) {
		memset(check, false, sizeof(check));
		v.clear();
		int num, d;
		cin >> num >> d;

		num -= 1; // 인덱스를 0부터 시작하기 위해 입력되는 num값에서 -1
		v.push_back({ num,d }); // 처음 입력받는 톱니바퀴와 방향을 푸쉬
		q.push({ num, d }); // 처음 입력받는 톱니바퀴와 방향을 푸쉬
		check[num] = true; // 해당 톱니바퀴 방문체크
		while (!q.empty()) {
			int cur_num = q.front().first; // 현재 톱니바퀴 숫자
			int cur_d = q.front().second; // 회전할 방향
			q.pop();

			if (cur_num != 0) { // 톱니바퀴가 첫번째가 아니라면
				if (dq[cur_num - 1][2] != dq[cur_num][6] && !check[cur_num - 1]) {
					// 왼쪽 톱니바퀴와 극이 다르고 왼쪽 톱니바퀴를 방문하지 않았다면
					q.push({ cur_num - 1, cur_d * -1 }); // 왼쪽 톱니바퀴 번호와 반대 방향을 큐에 푸쉬
					v.push_back({ cur_num - 1, cur_d * -1 }); // 왼쪽 톱니바퀴 번호와 반대 방향을 벡터에 푸쉬
					check[cur_num - 1] = true; // 왼쪽 톱니바퀴 방문 체크
				}
			}
			if (cur_num != 3) { // 톱니바퀴가 마지막이 아니라면
				if (dq[cur_num][2] != dq[cur_num + 1][6] && !check[cur_num + 1]) {
					// 오른쪽 톱니바퀴와 극이 다르고 오른쪽 톱니바퀴를 방문하지 않았다면
					q.push({ cur_num + 1, cur_d * -1 }); // 오른쪽 톱니바퀴 번호와 반대 방향을 큐에 푸쉬
					v.push_back({ cur_num + 1, cur_d * -1 }); // 오른쪽 톱니바퀴 번호와 반대 방향을 벡터에 푸쉬
					check[cur_num + 1] = true; // 오른쪽 톱니바퀴 방문 체크
				}
			}
		}

		rotate();
	}
}

void count() {
	int cnt = 0;
	if (dq[0][0] == 1) cnt += 1;
	if (dq[1][0] == 1) cnt += 2;
	if (dq[2][0] == 1) cnt += 4;
	if (dq[3][0] == 1) cnt += 8;
	cout << cnt;
}
void INPUT() {
	for (int i = 0; i < 4; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < 8; j++) {
			dq[i].push_back(str[j] - '0'); // 톱니바퀴 처음 상태 저장
		}
	}
}
void solve() {
	INPUT();
	check_rotate();
	count();
}
int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
	return 0;
}

시스템 엔지니어 직무는 서류 전형 통과와 관계 없이 코딩 테스트를 본다고 해서 일단 지원하였다.

2020 상반기 11번가 인턴 코딩 테스트는 객관식 및 주관식 20문제와 알고리즘 2문제로 구성되어 있었다.

사전테스트에서 객관식 및 주관식이 자바, 파이썬의 기본 문법을 묻길래 이런 류의 문제가 나오는 것이라고 생각했다.

본인의 개인적인 생각이지만 이번 11번가 인턴 코딩 테스트에서는 알고리즘 문제보다는 이 객관식이 더 관건이라고 생각한다.

심지어 객관식 및 주관식이라고 했는데 문제는 모두 객관식이었다.

문제는 주로 운영체제가 많았던 것 같은데 중간중간 클라우드 관련 내용도 있었다. 클라우드도 기초 지식이 아니라 완전 실무에서 나올법한 내용들이었다. 그냥 어려웠다.

알고리즘도 쉽지 않았다. 본인은 1번밖에 못풀었는데 그마저도 맞게 푼건지 모르겠다. 기억으로는 조합? 백트래킹?으로 풀었던 것 같다.

2번 문제는 풀이가 떠오르지 않았다. 느낌은 그리디 알고리즘, DP였는데 평소 그리디나 DP를 어려워했기 때문에 쉽게 접근할 수 없었다. 이를 통해 그리디와 DP를 보완해야겠다는 생각이 많이 들었다.

결과는 역시나 불합격이었다. 객관식 문제도 많이 틀렸을 것이고, 알고리즘 문제도 제대로 풀지 못했으니 당연한 결과다.

결과는 불합격이었지만 느낀 점은 많았다.

CS 기초 지식을 조금씩 공부해야겠다는 목표와 그리디, DP 알고리즘을 보완해야겠다는 목표를 가질 수 있게 되었다.