[코테 후기] 쿠팡 코테 후기

date

Aug 29, 2023

slug

2023-coupang-tech-coding-test-public

author

status

Public

테스트 환경

180분 4문제 (문제당 약 45분)

프로그래머스

자료참고&검색 불가

IDE 사용 불가

프로그래머스 IDE 간 복붙 가능

화면공유 + 웹캠 + 모니토(폰캠)

정답 여부 미공개(테스트케이스 제공)

테스트케이스 3개만 주어지고 결과를 알 수 없기 때문에 엣지케이스, 예외케이스를 잘 찾아야 할 것으로 보인다

(나는 시간이 없어서 이 단계를 생략했음ㅠ)

체감 난이도

ㅤ	체감 난이도	사용한 알고리즘
1번	실버 3~4	HashMap
2번	실버 1~2	그리디
3번	골드 3~4	비트마스킹, DFS
4번	골드 3~4	BFS

각 문제에 대한 간단한 후기(문제가 된다면 삭제)

1번 - 사내메신저

HashMap을 사용하면 금방 풀리는 문제였다.

각 팀원의 팀을 저장하는 HashMap<String, String>

각 팀에 속한 팀원수를 저장하는 HashMap<String, Integer>

각 팀 당 메시지 수신 명단에 들어가는 팀원수를 저장하는 HashMap<String, Integer>

전체 사원 명단을 돌면서 해당 사원의 팀을 해시맵으로 저장하고(추후 메신저 목록에서 사원의 팀을 바로 확인하기 위함), 메시지 수신 명단을 돌면서 각 팀의 수신인 수를 저장한다.

그리고 각 팀에 대하여, 만약 해당 팀 수신자 명수가 팀 전체 명수/2 보다 많다면 이는 곧 팀 사원들을 한 명 한 명 넣는 것보다 팀 전체를 넣은 후 나머지를 삭제하는 것이 더 빠르다는 의미이므로 ans += 1(팀 전체 추가) + (팀전체명수-수신자명수)(개별삭제)를 하고, 반대의 경우 ans += (수신자명수)(개별추가)를 한다.

문제 자체가 간단해서, 아마 반례는 없을 것으로 예상된다…

2번 - Queue 숫자 개수 맞추기

BFS로 가면 메모리를 너무 많이 쓸 것 같은데(String을 매번 생성해줘야 하므로) 다른 방법은 생각이 안 나서..

뭔가 그리디하게 풀어도 될 것 같은 느낌이 들어서 그리디로 풀었다. 예외 케이스가 있는지는 생각하지 못했음.. 근데 아마 무조건 있을 거라서, 스스로도 2번 문제는 잘못 풀었다고 생각하고 있다.

while문을 돌며 모든 숫자의 개수가 같아질 때까지 무조건 현재 가장 적은 숫자를 추가하는 방식으로 구현했다.

int[3] cnt : 현재 각 숫자들의 개수 카운트

int[3] ans : 현재 넣은 숫자들 카운트

while문 내부에서 cnt를 통해 가장 적은 개수의 숫자를 찾고, 그 숫자를 추가(ans, cnt 변경)하고 맨앞의 숫자를 삭제(cnt 변경)한다. 진짜 무조건 무조건 반례 있을 거다..ㅠ

3번 - 최대 그룹의 크기(클릭 문제)

일단 그래프 형태도 그렇고 DFS, BFS 중 하나로 풀어야 할 것 같았다. 그룹의 모든 사람이 서로 친구여야 하기 때문에 Union-Find도 알맞지 않고..

가지치기를 하기 어렵고 모든 분기를 다 확인해야 할 것 같았다. 예시의 경우에서 3-4를 선택한 후, 2-3을 선택하여 2-3-4 싸이클을 만들면 더 커질 수 없다. 하지만 3-4를 선택한 후, 3-5를 선택하면 3-6까지도 추가하여 3-4-5-6 싸이클을 만들 수 있다.

그래서 각 노드에서 시작하는 DFS를 돌면서 노드를 추가했다. 노드 추가는 현재 가지고 있는 모든 노드와 친구일 때만 추가하도록 했다. 현재 가지고 있는 노드 정보는 visited[] 로 저장하기엔 메모리가 많이 들 것 같아서 비트마스킹을 통해 저장했다. 어차피 people의 길이가 15이므로 int형으로 충분히 저장할 수 있을 것이라 생각했다. 끝나고 생각해보니 백트래킹으로 구현할 수도 있었을 것 같다.

답은 구할 수 있을 것 같은데.. 시간복잡도에서 터질 수도 있을 것 같아 불안하다.

4번 - 돌무더기

우선 현재가 미래를 보장하지 않으므로 그리디로는 풀 수 없고, 문자열을 저장해야 하기 때문에 dp로도 풀 수 없다고 생각했다. 따라서 완전탐색을 해야 하는데, 최소 횟수로 가야 하기 때문에 BFS를 선택했다. 또한 같은 길이의 정답들을 사전식으로 비교해야 하기 때문에 level을 기억하는 BFS로 구현했다.

각 BFS 단계에서는 1) 현재 경우가 조건을 충족했는지 확인 후 2-1) 충족했다면 정답 갱신, 2-2) 충족하지 않았다면 for문으로 각 돌무더기 중 선택 가능한 돌무더기 선택 후 큐에 넣기 를 반복했다.

BFS단계에서 넘길 인자

현재 단계의 문자열

1)에서 조건을 충족했는지 여부는

돌이 있는 돌무더기는 1개
그 하나의 돌무더기의 돌 개수는 k개

2-1)에서 현재 정답과 비교하여 갱신하지 않고 바로 갱신하는 이유는, 어차피 사전순으로 뒤에 있는 경우를 뒤에 만나기 때문에 무조건 갱신해도 될 것이라 판단했다.

2-2)에서 for문을 돌며 각 돌무더기를 선택하고, 해당 돌무더기 외에 다른 돌무더기 중 0개인 돌무더기가 있다면 불가능하므로 continue 하였다.

너무 오랜만에 보는 코테이기도 했고(약 4개월만), 정답 여부를 알 수 없었기 때문에 심리적으로 많이 불안했던 것 같다. 이유야 어쨌든 기량 부족이고, 꾸준한 알고리즘 공부 & 코테 모의 연습을 통해 실력을 기른다면 자연스럽게 극복할 수 있는 문제일 거라 생각한다.

이제부터 본격적인 하반기 서류 시작이다! 슬슬 포폴&이력서 정리, 자소서 내용 정리 병행 하며 코테 연습도 잊지 않고 해야겠다. 파이팅!

상반기 네이버 광탈했으니.. 이번 하반기에는 쿠팡 카카오 뚫어보자 아자아자!!