PS 시나브로

프로그래머스에서 이번 데브매칭에서 PCCP 기회를 주어서 응시하게 되었다.

일반적인 데브매칭에서는 모바일로 문제 푸는 모습만 나오게 촬영하면 되었지만

이번 시험에서는 규정이 상당히 까다로웠다.

큰 차이점은 주변환경을 촬영해야하는 것과 웹캠을 사용해야하는 것

또한 신분증도 촬영해야 하는데 사전테스트에서 미리 등록해 뒀었는데 다시 촬영할 필요가 없었다.

웹캠을 사용해야 하기때문에 부득이하게 노트북으로 테스트를 응시하였다.

(작은 모니터로 푸는게 쉽지 않았다.)

시험 1시간 전 입장가능하며 20분 전에는 입장이 불가능하다.

시험입장 후 대기하는 동안 중간중간 공지사항이 올라오며 따라서 이행하면 된다.

시험 후기

문제 난이도는 아무래도 인터넷 검색이나 IDE가 사용이 금지되어있기 때문에

고난도의 문제는 내지 않는 것으로 보였다.

기본적인 유형과 애드혹스러운 문제에 충실해서 내는 것 같았다.

기본 채점셋은 공개해 주지만 히든 테스트 셋은 공개해주지 않아 정답이 맞는지 긴가 민가 하였다.

시험 팁

시험시간은 2시간이지만 시험문제는 4개 이므로 시간 배분을 적절하게 해서 처리해야 한다.

모르는 문제에 계속 시간을 투자하지 말고 다음 문제로 넘어가서 풀다가 돌아오는 게 더 좋을 수도 있다.

실행 결과 테스트가 모두 맞았다고 해서 정답은 아니다 예외처리하지 못했거나

문제에서 요구하는 시간복잡도 내에 풀었는지 다시 한번 확인하는 게 좋다. (지문을 꼼꼼히 읽자)

IDE가 사용불가능하므로 자동완성이 되지 않기 때문에 응시언어의 자료구조의 함수들은 어느 정도 외워가는 게 좋다.

ex) insert, push, push_back, 인지 헷갈려 컴파일 에러가 나는 경우가 있다.

정 모를 경우 위에 레퍼런스를 눌러보면 해당자료구조의 기능들이 자세하게 나타나있다.

시험 결과

그래도 부분점수를 통해 LV.4를 턱걸이로 넘을 수 있었던 것 같다.

부족한 부분을 다시금 깨달을 수 있었던 좋은 시험이었다.

합정역에서 M7731번을 타고 킨텍스에 도착했다.

오후 1시 반쯤 도착했는데 사람이 엄청 많았다.

입장은 1시간 정도 줄 서서 기다렸다가 입장할 수 있었다.

들어와서 무슨 게임들이 있나 이곳저곳 돌아다녀봤다.

코세타

리듬게임이 재밌어 보여서 줄을 서서 대기하면서 플레이를 구경

대기 인원이 많아서 한명당 2판 플레이 가능

처음에 아무거나 선택해서 플레이했는데 생각보다 많이 어려웠다~

다음에는 조금 쉬운난이도로 바꿔서 플레이

노래들이 박자감이 있고 큰 터치스크린으로 플레이해서 만족

이미 상용화된 게임이라 돌아오면서 몇 번 더 플레이했다~

라핀

토끼 캐릭터들이 주인공이었는데 각자만의 특성과 스토리가 있었다

2D 플랫포머 게임으로 다양한 퍼즐과 스토리가 있어 좋았다

스토리를 중요시하는 플레이어라면 힐링게임이 될 수도 있다

게임의 컨트롤이 어려울 경우 난이도 설정이 가능하다(이지모드)

중간중간 다른 토끼들이 뛰어 넘어가는 맵이 나오는데

경쟁 아닌 경쟁과 가이드라인을 제시해 주는 느낌이라 신선했다

환세취호전

어린 시절에 재밌게 했던게임이라 반가운 마음에 플레이

지하던전에서 시작했는데 자꾸 죽어서 최대 HP가 계속 줄어들었다..

중간에 멧돼지들 잡으면서 맹호난무 기술레벨업~

마을로 도망친 다음 해변가가서 스마슈 구하고 병원에다가 데려다줬다

게임의 스토리라인은 크게 비슷한 느낌이고 그래픽이  많이 좋아졌다

실제 출시하게 되면 어떻게 바뀔지 궁금하다

이상한나라의 Ragnarok

방치형 힐링게임느낌이고 가이드를 따라가면 이것저것 할 수 있다

주목적은 이그드라실이라는 나무를 성장시키는 게임 같다

퀘스트 동선이 너무 정신없어서 뭔가 어렵다는 느낌을 받았다.

성장하게 되면 각종 기능들이 해금되며 제한이 풀린다

느긋한 힐링게임을 좋아한다면 플레이해 볼만할 것 같다.

마리오카트

게임의 화질은 좋지 않아 눈이 어지러웠지만 재밌게 플레이했다.

생각보다 AI들이 너무 잘해서 이기기 어려웠다~

Remove : 범죄는 흔적을 남긴다

주어진 시간 동안 범죄의 흔적을 지워야 하는 게임

방탈출과 비슷하면서 조금 차별된 느낌이 들었다

핸드폰을 통해 시간 및 각종 상호작용이 가능

특히 사운드와 함께 플레이하면 몰입감이 올라간다

적당한 공포감과 추리를 좋아한다면 추천할만한 게임

후기

여러 게임을 체험해 볼 수 있어서 너무 좋았다

시간이 타이트해서 많이 즐기지 못해 아쉽다~

대회링크 : https://codeforces.com/contest/1805

A. We Need the Zero

문제 : 배열 원소를 특정 x로 xor한 원소들의 xor 값을 0으로 만드는 x값 출력 

조건 : x의 범위는 0~255, 만족하는 x가 없을 경우 -1 출력

해결방법 1 : 0~255까지 x를 대입하며 만족하는 x 값을 찾는다.

해결방법 2 : xor의 교환법칙이 성립함을 이용한다.

배열의 원소 개수 - 짝수

해당 경우에는 x는 최종결과에 영향을 미치지 못하게 된다

(같은 x를 짝수 번 xor 한 경우 0이 나오기 때문)

(x⊕x = 0)

즉, 짝수인 경우에는 주어진 배열의 xor 연산 결과가 0일 경우에만 성립한다.

(a⊕x)⊕(b⊕x)⊕(c⊕x)⊕(d⊕x)

= a⊕b⊕c⊕d⊕x⊕x⊕x⊕x

= a⊕b⊕c⊕d

배열의 원소 개수 - 홀수

해당 경우에는 x는 주어진 배열의 xor한 값에 x를 xor한 값과 같게 된다.

즉, x 는 주어진 배열의 xor 한 값이 되게 된다.

(a⊕x)⊕(b⊕x)⊕(c⊕x)

= a⊕b⊕c⊕d⊕x⊕x⊕x

= a⊕b⊕c⊕x

B. The String Has a Target

문제 : 주어진 문자열에서 두 문자를 한 번만 바꾸어 사전순으로 가장 앞에 오는 단어 출력

조건 : 두 문자가 같아도 된다.

주어진 문자열의 앞 부분 부터 탐색하며 사전순으로 가장 앞서는 문자의 위치를 기록한다.

이때 사전순으로 앞서는 단어가 여러 개 있을 경우 가장 뒤에 있는 문자의 위치를 기록한다.

마지막으로 기록된 위치의 문자를 출력하고

문자열을 다 돌면서 기록된 위치를 제외한 문자열을 출력하면 된다.

C. Place for a Selfie

문제 : 이차방정식이 주어진 일차방정식에 근을 갖지 않는 경우 판단

조건1 : 일차방정식은 원점을 지난다 (y=kx)

조건2 : 이차방정식은 항상 아래로 볼록하다 (a>0)

y = ax^2 + bx + c

y = kx

두 그래프가 근을 갖지 않으려면 판별식(D)에 의해 (b-k)^2 - 4ac < 0 이어야 한다.

이때 (b-k)^2은 항상 양수이기 때문에 (b-k)의 절댓값이 가장 작을 때 성립할 가능성이 높아진다.

따라서 b-k의 절대값이 가장 작은 경우를 구해 판별했을 때 음수가 나오면 근이 없음을 증명할 수 있다.

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int iT;
	cin >> iT;
	while (iT--)
	{
		int iN, iM;
		cin >> iN >> iM;
		vector<long long> vecSlope(iN);
		for (int i = 0; i < iN; ++i) cin >> vecSlope[i];
 
		sort(vecSlope.begin(), vecSlope.end());
 
		while (iM--)
		{
			long long lA, lB, lC;
			cin >> lA >> lB >> lC;
 
			int iLeft = 0;
			int iRight = iN - 1;
 
			long long lMulti = abs(lB - vecSlope[0]);
			long long lAns = vecSlope[0];
			while (iLeft <= iRight)
			{
				int iMid = (iLeft + iRight) / 2;
				if (lB >= vecSlope[iMid])
				{
					iLeft = iMid + 1;
				}
				else
				{
					iRight = iMid - 1;
				}
				if (lMulti > abs(lB - vecSlope[iMid]))
				{
					lMulti = abs(lB - vecSlope[iMid]);
					lAns = vecSlope[iMid];
				}
			}
			if (lMulti * lMulti - 4 * lA * lC < 0)
			{
				cout << "YES\n";
				cout << lAns << "\n";
			}
			else
			{
				cout << "NO\n";
			}
		}
	}
	return 0;
}

D, E.

F. Survival of the Weakest (easy version)

문제 : F(F(F(A)))... 즉 F를 A의 길이의 n-1번 반복했을 때 나오는 수 출력

조건1 : n은 2~3000 (easy version)

조건2 : 배열의 원소는 0~10억

F는 A의 두 서로 다른 원소의 합으로 나올 수 있는 수들 중에서 A의 개수보다 1개 적은 개수를 뽑는 함수

F(1, 2, 5, 7) =>  (1+2, 1+6, 2+5, ... ) => (3, 6, 7) 

원소의 개수를 모두 보며 최소 값을 계산하는 건 시간적 낭비가 매우 크다

즉 작아지는 순에서 커지는 순으로 잘라서 보면 연산 횟수가 매우 줄어든다.

i는 0번째 j는 i+1번째부터 시작하며 원소를 순회한다.

우선순위큐(내림차순)를 이용하여 i와 j번째 원소 합을 넣어주고

우선순위큐의 크기가 n-1보다 클 경우 원소 하나를 꺼내준다.

i를 증가시킬 때 우선순위큐에 가장 위에 있는 값보다 i번째와 i+1번째의 합이 클 경우에는

더 이상 우선순위큐에 들어갈 조건이 성립이 되지 않는다.

위에서 구한 값을 이용해 배열을 다시 재배치해준다.

A를 F함수를 통하여 F(A)를 구했다.

이때 배열의 원소가 모두 컸다고 가정하면 배열의 최댓값은 최대 2배씩 확장되게 된다.

long long 범위를 사용한다고 해도 10억 * 2^2999 는 감당할 수 가없다.

그래서 배열 재배치 후 첫 번째 원소의 값을 mod로 나눴을 때 나오는 정수만큼

배열의 모든 값을 빼서 F(A)를 계산해 준다.

6번의 배치를 끝내고 다행히 블루에 도달할 수 있었다.

부족한 점을 보완해서 더 나은 코드를 짤 수 있게 노력해야겠다.

대회링크 : https://codeforces.com/contest/1798

A. Showstopper

문제 : A배열 원소의 최댓값 = A배열의 마지막 원소값, B배열 원소의 최댓값 = B배열의 마지막 원소값 가능판단

조건 : A, B의 같은 위치의 원소는 서로 교환이 가능하다.

A와 B의 마지막 원소중 큰 값을 p, 작은 값을 q 라고 했을 때

조건에 의해서 그 이전의

같은 위치의 원소중 작은 값은 q보다 작거나 같아야 하고

같은 위치의 원소중 큰 값은 p보다 작거나 같아야 한다.

순차적으로 보면서 A, B의 크기를 비교해 교환 후에 마지막 원소보다 큰 값이 있는지 비교한다.

마지막 원소보다 큰 값이 있을 경우에는 문제의 조건을 만족시킬 수 없다.

불가능 ex)

A : 1 1 2 2 1 1 2

B : 1 2 1 2 1 2 1

===========

A : 1 1 1 2 1 1 1

B : 1 2 2 2 1 2 2

A의 4번째 원소가 마지막원소 보다 크기 때문에 불가능하다.

B. Three Sevens

문제 : 1일부터 m일까지 매일 열리는 복권의 예상 당첨자 출력

조건1 : 복권에 당첨 된 사람은 그 이후에 다시 복권을 구매하지 않는다.

조건2 : 매일 하루에 한명씩 복권을 구매한 사람중 한명은 당첨된다.

해당일자에 구매한 사람의 목록을 저장 해 둔다.

마지막 날 부터 거꾸로 돌아오며 다음과 같이 수행한다.

조건1에 의하여 당첨 하였을 경우 복권을 재구매 하지 않기 때문에

set을 이용하여 당첨후보로 선택했는지의 여부를 기록해둔다.

m일의 구매자를 순회하며 구매한 기록이 없을 경우 set에 넣고 후보에 등록한다.

(m 일의 경우 그 이후에 구매한 사람이 없으므로 무조건 후보에 등록된다)

m-1일의 구매자를 순회하며 set에 없을 경우 set에 넣고 후보로 등록한다.

m-2일의 구매자를 순회하며 set에 없을 경우 set에 넣고 후보로 등록한다.

...

2일의 구매자를 순회하며 set에 없을 경우 set에 넣고 후보로 등록한다.

1일의 구매자를 순회하며 set에 없을 경우 set에 넣고 후보로 등록한다.

위의 과정을 통해 예상되는 당첨자를 추려낼 수 있다.

C. Candy Store

문제 : 물품을 진열장에 올렸을 때 필요한 가격표의 개수

물품의 낱개 가격과 개수를 주어준다.

조건1 : 물품의 개수를 n으로 묶을 수 있을 경우 묶음으로 판매 할 수 있다.

조건2 : 그 이전과 같은 가격의 상품일 경우 가격표가 추가적으로 필요하지 않다.

물품 A의 개수와 가격을 a1, b1이라고 하고

물품 B의 개수와 가격을 a2, b2 라고 하고

물품 A, B의 물품 총가격을 s1 = a1*b1, s2 = a2*b2 라고 하면

다음과 같은 경우 하나의 가격표로 묶을 수 있다.

GCD(s1, s2) % LCM(b1, b2) = 0

묶을 수 있는 경우

GCD = GCD(s1, s2)가 되고

LCM = LCM(b1, b2)가 된다.

묶을 수 없는 경우

필요한 가격표가 하나 추가 되고

GCD = s2이 되고

LCM = b2가 된다.

이제 물품 C가 있다고 하면 위에서 계산한 GCD, LCM 값을 s1, b1으로 사용하여 계산하면 된다.

D. Shocking Arrangement

문제 : 주어진 배열의 원소를 재배치 했을 때 부분배열의 절댓값이

원소의 가장큰 값과 작은 값의 차이보다 작을 경우가 있을 때 그러한 배열 출력

조건 : 모든 원소의 합은 0 임이 보장된다.

모든 원소의 합이 0 이므로 불가능한 경우는

주어진 배열의 원소가 모두 0인 경우 부분배열의 값(0) 이 모두 차이(0) 과 같으므로 불가능 하다.

그 외의 상황에선 항상 만족하는 배열을 만들 수 있다.

누적합을 이용하며 시작은 0으로 한다.

누적합의 값이 0이상인 경우에는 음수의 원소를 하나 더해준다. 없을 경우 남아있는 0을 출력해준다.

누적합의 값이 0미만인 경우에는 양수의 원소를 하나 더해준다. 없을 경우 남아있는 0을 출력해준다.

이 때 누적합은 항상 (최댓값-최솟값)의 차이 이내에 존재하게 된다.

E,F. 아직 실력 부족으로 접근하지 못하였다.

대회링크 : https://codeforces.com/contest/1809

A. Garland

문제 : 모든 전구를 켜는데 필요한 최소 횟수 출력

조건 : 같은 종류의 전구를 이전에 활성/비활성 했을 경우 해당차례에 선택 불가

전구가 모두 같은 종류 일 경우 : 불가능(-1)

전구하나만 다른 종류일 경우 : 6 [aaab : b - a - b - a - b - a]

그 외 : 4

aabb : a - b - a - b

abcc : a - c - b - c

abcd : a - b - c - d

B. Points on Plane

문제 : n개의 물건을 좌표평면에 올렸을 때 원점으로부터 거리들의 최댓값이 최소가 될 때의 최댓값 출력

조건 : 임의의 두 물체 맨해튼 거리는 항상 2 이상이어야 한다. (유클리디안 X)

2가지 경우로 나누어 보면 쉽게 풀 수 있다.

거리들의 최댓값을 x라 했을 때

x가 짝수 : (0,0)로 시작 (2x,2y) -> x[0] = 1, x[2] = 9, x[4] = 25 ...

x가 홀수 : (±1,±1)로 시작(±1+2x,±1+2y) -> x[1] = 4, x[3] = 16, x[5] = 36 ...

즉 n이 1개일 때부터 최댓값(x)을 보면

(n,x) = (1,0), (2,1), (3,1), (4,1), (5,2), (6,2), (7,2), (8,2), (9,2), (10,3), (11,3) ...

즉 x = sqrt(n-1) 의 값을 나타낸다.

이때 주의 사항은 n의 값이 10^18까지 나올 수 있으므로

(long long)sqrt(n-1)을 할 경우 오차의 발생으로 틀리게 된다.

따라서 안정적인 이분탐색등을 사용하여 계산해 주면 된다.

//long long형 제곱근
long long sqrt(long long n) {
	if (n <= 1) return n;
	long long lo = 0, hi = n;
	while (lo <= hi) {
		long long mid = (lo + hi) / 2;
		if (mid > n / mid)
		{
			hi = mid - 1;
		}
		else {
			lo = mid + 1;
		}
	}
	return hi;
}

C. Sum on Subarrays

문제 : n개의 원소를 갖는 배열 이 있을 때 k 개의 원소의 합이 양수인 부분 배열을 갖는 배열 출력

조건 : 각 원소의 범위는 -1000에서 1000까지 가능하다.

주의사항 : 0은 양수도 음수도 아니다.

풀이에 다양한 방법이 있겠지만 다음과 같은 방법을 사용하였다.

우선 n=5, k=7이라고 가정했을 때 5칸의 배열을 다음과 같이 만들어준다.

(-1,-2,-3,-4,-5)

첫 번째부터 순회하며 k값이 0보다 클경우에만 수행한다.

k=7 -> 6 = (-1+2,-2,-3,-4,-5) = (1,-2,-3,-4,-5)  = 1개

k=6 -> 5 = (1+3,-2,-3,-4,-5) = (4,-2,-3,-4,-5) = 2개

k=5 -> 4 = (4+4,-2,-3,-4,-5) = (8,-2,-3,-4,-5) = 3개

k=4 -> 3 = (8+5,-2,-3,-4,-5) = (13,-2,-3,-4,-5) = 4개

k=3 -> 2 = (13,-2+3,-3,-4,-5) = (13,1,-3,-4,-5) = 5개

k=2 -> 1 = (13,1+4,-3,-4,-5) = (13,5,-3,-4,-5) = 6개

k=1 -> 0 = (13,5+5,-3,-4,-5) = (13,10,-3,-4,-5) = 7개

위와 같은 방법으로 계산할 경우 조건에 맞는 배열을 구 할 수 있다.

D. Binary String Sorting

문제 : 주어진 이진배열을 조작하여 오름차순을 만들 때의 비용의 최솟값 출력

조작 1 : 연속한 두 원소를 1000000000001의 비용으로 치환할 수 있다.

조작 2 : 임의의 원소를 1000000000000의 비용으로 삭제할 수 있다.

해당배열을 첫 번째부터 순차적으로 보며 다음과 같이 수행한다.

해당 위치보다 왼쪽에 있는 0은 제거할 필요가 없다.

해당 위치보다 오른쪽에 있는 1은 제거 할 필요가 없다.

즉 제거해야 되는 개수를 구해준다.

해당위치가 1인 경우 제거 대상에서 임시로 제외한다.

다음위치가 0인 경우 제거 대상에서 임시로 제외한다.

해당위치보다 다음위치가 더 작을 경우 교환을 통해 교체해 준다.

이렇게 차례대로 구한 비용들의 최솟값을 출력한다.

E,F,G  아직 실력 부족으로 접근하지 못하였다.

대회링크 : https://codeforces.com/contest/1794

A. Prefix and Suffix Array

문제 : 접두사와 접미사 목록을 주었을 때 원래 문자열이 팰린드롬인지 판단

원래 문자열의 길이가 n 일때

길이가 1인 경우에는 접두사와 접미사가 같은지 판단

길이가 2이상인 경우에는 길이가1인 문자열 2개와 길이가 n-1인 문자열 2개 저장하고

두 문자열을 조합했을 때 서로 같은 경우 해당 문자열이 기존 문자열 이므로

그 문자열이 팰린드롬인지 판단

B. Not Dividing

문제 : 주어진 배열을 조작하여 해당원소가 이전의 원소로 나누었을 때 정수로 떨어지지 않게 만들기

1번의 조작으로 특정 원소의 값을 1 증가 시킬 수 있으며 최대 2n번 까지 가능하다

주어진 원소에 모두 1을 더하고

다시 두 번째 원소 부터 보며 그 이전원소로 나누어 질 경우 1을 더해줌으로서 해결

C. Scoring Subsequences

문제 : 주어진 배열에서 각 원소마다 최대 점수를 만드는데 필요한 최대 비용 출력

에디토리얼은 O(nlogn)의 풀이가 있지만 O(n)으로 푸는 방법이 존재한다.

이 문제에서 블럭을 하나 씩 놓았을때 최대로 만들 수 있는 정사각형 크기와 같다

또한 각 원소는 모두 오름차순 이므로 그 이전에 만든 값보다 항상 비용이 크다

따라서 해당 원소에서 더 큰 정사각형을 만들 수 있는 경우에는 정사각형의 크기를 1 크게 하고

그렇지 않다면 그냥 넘어가면서 비용을 출력 하면 된다.

D. Counting Factorizations

문제 : 주어진 배열을 조합하여 식에 맞는 수를 만들고 중복되지 않은 수 의 개수를 출력

이 문제는 궁금해서 에디토리얼을 찾아보았다.

기본적으로 2n 까지의 팩토리얼과 역팩토리얼을 미리 계산 해 둔다.

역팩토리얼(inverse)의 경우 pow(n,p-2) % p 로 구해준다.

이제 주어진 원소를 소수가 아닌 것과 소수 인 것으로 분리 하고

소수인 경우에는 해당 소수를 사용할 경우와 사용하지 않는 경우로 나누고 해당 값을 더 한다.

이때 dp를 이용해 계산 된 값을 메모이제이션 해주는게 핵심이었다.

계산할 때 n개중 p가 a개, q가 b개 r이 c개 일경우 n!/(a!b!c!) 이 되며

이것을 역팩토리얼 계산한것을 이용해 n! * inverse(a) * inverse(b) * inverse(c) 로 치환

치환하여 나머지 계산해도 같은 값을 얻을 수 있다.

E.  아직 실력 부족으로 접근하지 못 하였다.

대회링크 : https://codeforces.com/contest/1800

A. Is It a Cat?

문제 : 주어진 문자열에서 m, e, o, w 가 순차적으로 나오는지 판별

간단하게 meow가 순차적으로 나왔는지 판단하고

해당차례에 해당 문자 혹은 해당 이전의 문자가 아닌 다른문자가 나올 경우 불가능으로 판단

B. Count the Number of Pairs

문제 : 대, 소문자의 같은 알파벳끼리 최대로 이루는 짝의 개수 출력

대문자에서 소문자, 소문자에서 대문자로 최대 K번 바꿀 수 있음

각 알파벳 별로 대문자와 소문자를 나누고

이때 짝을 이루는 개수는 각 알파벳별로 min(대문자, 소문자) 이고

대소문자를 치환하여 짝을 만들수 있는 경우는 abs(대문자 - 소문자)/2 가 되며

K번 초과 해서 짝을 만들 수 있는 경우엔 최대 K개의 짝을 만들 수 있다.

C. Powering the Hero

문제 : 카드를 순차적으로 뽑아 얻을 수 있는 최대 파워 출력

0번 카드(히어로)를 뽑은 경우 더미 가장 위의 에너지카드 만큼 파워를 얻는다.

그외의 카드(보너스)인 경우 더미 위에 카드를 올리거나 버릴 수 있다.

우선순위큐를 사용하여 보너스 카드인 경우에는 항상 넣어주며

히어로 카드인 경우에는 우선순위큐가 비어있지 않다면 하나를 꺼내 파워를 얻는다.

D. Remove Two Letters

문제 : 주어진 문자열에서 연속된 2글자를 제거했을 때 나올 수 있는 문자열의 개수 출력

해당 문제에서 substr을 이용해 단순하게 구현 했을 때 메모리초과를 당하였다.

길이가 N인 문자열에서 문자열을 2개 제거 했을 경우 만들 수 있는 경우는 총 N-1가지 이며

문자열을 처음부터 비교했을때 2칸 뒤의 문자열이 현재 문자열과 같은 경우에 중복되므로 1가지씩 줄인다.

ex) @aba# -> @(ab)a# = @a#, @a(ba)# = @a# 로 중복되게 된다. 

E. Unforgivable Curse

문제 : 주어진 문자열을 이동시켜 원하는 문자열로 변환 할 수 있는지 판별

해당 위치의 문자열은 K칸 앞, 뒤 혹은 (K+1)칸 앞, 뒤 문자와 교환 할 수 있으며 횟수 제한은 없다.

해당 위치에서 BFS탐색을 통해 연결 된 곳은 모두 서로 하나의 집합에 속하게 된다.

따라서 BFS를 통해 집합을 나누고 각 집합의 알파벳 개수가 동일하다면 A문자열에서 B문자열로 치환이 가능하다.

F, G - 아직 실력이 부족해 풀지 못하였다.

2021 Dev-Matching: 웹 백엔드 개발자(하반기) 코딩 테스트

코딩 테스트는 총 120 분간 진행되었으며 4문제(SQL 1문제 포함)로 구성되어 있었다.

전체적인 문제의 난이도는 높지 않고 기본적인 구현을 할 수 있는지

역량을 확인하는 것 같고 기본적으로 문제의 n 값이 작기 때문에

다양한 방법으로 주어진 문제를 풀 수 있었을 것 같다.

SQL의 경우 항상 공부를 하고 난 뒤 실제로 사용할 일 이 없기에

금방 다시 까먹게 되는 것 같아 이러한 점은 보완해야겠다고 생각을 먹은 테스트였다.

1번 문제

새로운 문자열이 기존에 있던 문자열 목록에 포함되면 새로운 문자열을 반환하고

기존에 없는 문자열이라면 해당 문자를 반환하는 문제였다.

우선 기존 문자열을 HashSet<String> 을 이용하여 모두 넣어준 후에

해당 셋에 새로 원하는 문자열이 들어있다면

새로운 문자열을 정규표현식을 이용하여 문자부와 숫자부로 나눈다.

문자부 : str.replaceAll("[^0-9]","")

숫자부 : str.replaceAll("[^a-z]","")

문자와 숫자로 나눠진 문자열은 주어진 규칙에 의해 새로운 문자열을 만들고

위 과정을 반복하여 HashSet에 포함되어 있지 않다면 해당 문자열을 반환한다.

2번 문제

문제에 대한 직접적인 언급은 하면 안 될 거 같아 비슷하게 만들어 보면

제한된 길이의 일자로 된 공간이 동일한 길이로 나누어져 있고

몇몇 공간에는 통로가 있으며 양옆의 통로끼리는 연결될 수 있다.

이때 주어진 횟수만큼 통로를 추가 설치하여 가장 긴 통로를 만들라는 식의 문제였다.

누적합을 이용해 왼쪽 끝부터 해당 위치까지의 통로가 없는 개수를 계산해주고

투포인터를 이용하여 처음 투포인터의 간격을 한 칸으로 시작하여

주어진 구간에 추가적으로 설치해야 될 경우 왼쪽 포인터와 오른쪽 포인터를 오른쪽으로 한 칸

주어진 구간에 추가적으로 설치하지 않아도 될 경우 오른쪽 포인터를 오른쪽으로 움직이며

오른쪽 포인터와 왼쪽 포인터의 위치 차이를 이용하여 최대길이를 계산해준다.

이때 주어진 n 값이 매우 작았으므로 누적합을 이용하지 않고 투포인터 만으로도 가능하다.

3번 문제

기본적인 BFS 문제에 구현이 추가된 문제였다.

해당 문제 특성상 여러 번의 변동이 있을 수 있으며

이 경우에는 while문을 통해 변동이 없을 때까지 진행해주면 된다.

BFS를 도는 과정 중에 중복된 곳을 처리하여 경우의 수를 줄일 수 있는데

n 값이 매우 작기 때문에 완전 탐색하여도 문제가 없을 것 같다.

처음에는 단순한 문제라고 생각하여 제출하였는데

계속 틀려 BFS를 잘 못 돌렸나 생각하며 코드를 이것저것 수정하며 시간을 많이 소모했는데

BFS 이후에 처리해주어야 하는 과정이 틀린 것을 마지막에 알게 되고 수정하여 맞췄다.

너무 당연히 맞다는 생각에 단순 구현이 틀릴 수 있다 라는 생각을 못했던 거 같다.

참고할만한 문제

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

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

4번 문제

A그룹 중 B그룹 특정 단어가 포함되지 않는 행을 골라서 출력하는 문제였다.

간단히 NOT IN 혹은 LEFT JOIN 등으로 해결할 수 있다.

3번 문제의 오류를 해결하고 나니 시간이 얼마 남지 않아 풀지 못하고 제출하였다.  

결과