입력 잘 읽기, 탐색 시 주의할 점

교정 내용

 

1. 정렬할 대상의 범위를 알고 있고, 충분히 작으면서 자연수라면 카운팅 정렬을 고려해보자.

2. 좌우 대칭을 물어보는 문제는 추 교환을 떠올려보자.

3. 깊이 문제는 BFS에서 처럼 queue를 이용하자.

4. 각 깊이, 케이스 순회할 때는 성공 여부를 따져보고 구하고자 하는 값에 반영하자.

---

 

2020년 5월 10일 우아한 테크 캠프 1차 코딩 테스트를 봤다.

 

 

 

 

 

1번 문제는 연속된 숫자를 세서 계속 만드는 문제였다.

 

탐욕법을 이용하면 간단히 풀 수 있는 문제였다.

 

 

 

 

 

 

 

2번 문제는 애너그램 만들기 문제였다. 애너그램을 만들고 중복을 피하기 위해서는 set을 사용해야 한다.

 

set을 이용해서 set안에 이번에 만든 애너그램이 있는지 탐색하는 것도 빠르다.

 

이 문제는 함정이 조금 있는 것 같다. 애너그램을 만들 때, 단순히 자릿수 별로 숫자를 쪼개서 정렬을 하게 되면 O(NlgN)의 시간 복잡도를 갖는다. 이걸 n번 반복하게 되니 O(N^2 * lgN)이 된다. 입력이 작으면 상관없지만 각 숫자들 자리랑 전체 데이터 크기도 꽤 컸다.

 

 그래서 이렇게 하면 아마 시간 초과가 날 것이다. 이 문제는 카운팅 정렬을 해야 한다. 자릿수 별 숫자는 0 ~ 9까지 밖에 존재하지 않으므로 카운팅 정렬을 하게 되면 O(N)만에 정렬을 끝낼 수 있다.

 

(정렬할 대상의 범위를 알고 있고, 충분히 작으면서 자연수라면 카운팅 정렬을 고려해보자)

 

 

 

 

 

 

3번 문제은 입출금 하는 기능을 단순 구현하는 문제였다. 이 문제는 map을 사용해야 한다.

 

케이스가 작은 경우는 상관없지만, 조금만 커지면 무조건 map을 사용해야 된다.

 

그냥 습관적으로 map을 사용하자. 심지어 편하다.

 

 

 

 

 

 

4번 문제는 모빌 좌우 대칭 이번 코테의 가장 어려웠던 문제였다.

 

 처음에 당황스러워서 5분 정도 생각했던 것 같다. 하지만 추 교환 문제랑 같은 문제였다. 

다른 점이라면 깊이를 따진 다는 것이다. 이 아이디어는 좌우 대칭이라는 힌트에서 얻게 되었다.

 

(좌우 대칭을 물어보는 문제는 추 교환을 떠올려보자.)

 

(밑에서부터는 물체의 무게를 추라고 하겠다.)

 추 교환 문제에서 큰 추가 가능한 무게라면 무조건 큰 추를 사용하는 것이 좋다. 반대로 모빌에서는

좌우대칭을 맞추기 위해서 현재 걸어야 하는 무게보다 절반인 추가 2개 이상 있다면 작은 추 두개를 거는 게 좋다.(탐욕법)

 

예를 들어, 4를 한쪽에 걸어야 한다면 4보다는 절반인 2, 2로 거는 게 더 좋다. 하지만 2짜리가 2개가 안된다면 4짜리를 걸면된다.

 

 

그리고 좌우대칭이기에 항상 좌우에 같은 무게가 걸리게 된다. 즉, 홀수 일 때는 추하나 거는 상황 외에는 깊이를 늘릴 수없다.

 

그래서 가장 많은 물체를 매달 수 있는 상황인 모든 물체를 다 더한 무게부터 시작해서 무게가 1인 상황까지 순회하면 된다.

 이 순회를 하면서 사용할 수 있는 큰 추가 있다면 사용하되, 없다면 다음 깊이로 넘겨주면 된다.

 

(깊이를 넘겨줄 때는 BFS에서 처럼 queue를 이용하자. 깊이 문제는 queue로 접근!)

 

그리고 각 깊이에서 추를 사용할 수 있을 때마다 카운트를 늘려준다. 그리고 추 무게가 홀수인데 해당 무게의 추가 없으면 끝내게 된다.

이때, 또 하나 주의할 점이 있다.

 

각 깊이에서 왼쪽 편 것은 달 수 있어서 카운트를 늘렸다고 하더라도, 오른쪽에서 홀수인데 추를 달 수 없으면 왼쪽 편 카운트 값을 반영하면 안 된다.

 

 

(각 깊이, 케이스를 별 성공 여부를 따져서 구하고자 하는 값에 반영하자.)

 

 

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~