코테
산업기능요원 준비를 하면서 이력서도 써보고 지난 월요일에 이력서까지 넣게 되었다. 그중 C사에서 확인 후 1분만에 (아마 서류는 확인하지 않은 듯 하다. 코테로 한번 거른다는 의미일 것 같다.) 바로 서류합을 알린 후 코테 링크를 보내왔다. 알고리즘 대회는 많이 나가봤지만 기업 코테는 처음이라 설레임 반 긴장 반으로 코테를 시작했다.
근데?
난이도가 생각했던 것 보다 어려웠다. 기껏해야 bfs,dfs 기초적인 구현 정도만 물을 줄 알았지만 은근 까다로운 문제들이 많았다. 시간은 4시간이 주어졌고 5문제가 출제 되었다. 시험은 HackerRank 사이트에서 출제되었으며 웹 IDE(VSC를 닮은)에서 풀 수 있었다.
1번
1번 문제는 주어진 String에서 "AWS" 문자열을 찾아 삭제하고 이어붙여 다시 "AWS" 문자열을 찾아 삭제,반복하는 문제였다. 처음에는 단순히 string.find() 메소드를 사용해 계속 AWS를 찾고 erase해서 풀었는데 시간 초과가 나왔다. 이 때부터 뭔가 심상치 않음을 느꼈는데 시간을 고려해 넘긴후 나중에 다시 AWS를 삭제한 자리에서 계속 탐색, 만들어지지 않으면 다시 find해 찾는 방법으로 All Pass 하였다.
2번
2번 문제는 주어진 숫자 n에서 특정 숫자를 바꿔 Max, Min값을 찾아 그 차이를 출력하는 문제였다. 예를 들어 80812라는 숫자가 주어지면 가장 큰 숫자는 90912 (8을 9로) 가장 작은 숫자는 10112(8을 1로) 바꾸는 방식으로 해결하면 되었다. 단순한 구현 문제였기 때문에 쉽게 풀었던 것 같다. 하지만 역시 중간중간 함정에 조금 빠져서 무난하게 풀어내지는 못했던 것 같다. 역시 All Pass
3번
3번 문제는 주어진 집합의 부분집합 중 그 합이 n을 넘지 않으면서 원소의 개수가 가장 많은 집합을 찾아내는 문제였다. 처음에 문제 해석을 잘못해서 세그먼트 트리로 풀고 있던 중 부분합이 아니라 부분 집합임을 확인하고는 멘붕에 빠졌다. 내가 생각하기에는 DP문제인 것 같은데 해결 방법을 찾아내지 못했다.
4번
4번 문제는 DP라고도 볼 수 있는 구현 문제였는데 문자열의 집합이 주어지고 각 문자열들에서 한 문자를 뺀 값이 주어진 집합에 들어 있으면 link가 1씩 올라가고 이를 모든 문자열에 대해 행했을 때 가장 Link가 높은 값을 출력하는 문제였다.
예시로 집합 {"a","b","ab","cd","abc"} 가 주어지면 "a", "b"는 크기가 1이므로 link는 1, "ab" -> "a" or "b"이므로 "ab" 는 2, "cd"는 없으므로 1, "abc" -> "ab"이므로 3이여서 답이 3이 된다.
문자열 비교는 비트마스크로 했다. "abc"는 a,b,c자리에 1 나머지 0, "cd"는 c,d 자리에 1 나머지 0으로 한다. 이 때 "abc"와 "ab"를 비교하려면 비트마스크값에 and연산을 해 크기가 작은 비트마스크값과 일치하는지 확인한다. 그럼 O(1)만에 비교가 가능하다.
문자는 하나만 뺄 수 있으므로 크기별로 리스트에 담은 후 자기보다 길이가 1 작은 리스트를 조사해 link값을 올려주면 된다.
근데 내가 생각해내지 못한 반례가 있었는지 10개의 테스트중 7개만 통과하였다. 아쉬운 결과이다.
5번
5번 문제는 제대로 읽지도 못했고 다 읽었어도 풀지 못할 것이라 생각한다. 그래프 문제였는데 처음 노드 1, 도착 노드 n이 주어지고 반드시 도착해야 하는 노드 리스트 visit이 존재한다. 이때 visit에 들어있는 노드를 모두 통과하고 1부터 n에 도착하는 가장 짧은 경로를 찾아야 한다. n이 인걸 보아 아마 다익스트라를 응용해서 풀어야 할 듯 싶었는데 건드리지 못했다.
마지막으로
이렇게 5문제중 2.7개만 풀어내었다. 이 회사에 코테가 어려운건지 내 실력이 모자란 건지는 잘 모르겠지만 붙더라도 알고리즘 공부를 더 해야 하겠다는 생각이 들었다. 백준을 많이 안풀긴 했는데 역시 꾸준히 하는 사람이 더 잘하는 듯 하다. 토요일에 icpc가 있는데 코테에서부터 이러면 icpc는 제대로 풀 수 있을까 걱정이 많이 된다. 다른 기업 코테도 보고 나서 올려봐야지
