2020 선발고사 2주차(멘토교육 5주차)

1번과 4번은 푼 문제여서 2번과 3번 두 문제를 생각했고, 그 중 2번을 풀었습니다.

2번: 문제를 요약하면 A[i]=3,A[j]=2,A[k]=1 or A[i]=1,A[j]=2,A[k]=3인 i,j,k 쌍을 최대한 고르는데, 한 인덱스는 한 번만 쓸 수 있는 문제입니다.구현이 발상에 비해 간단한 편인 그리디 문제입니다. 가장 먼저 할 관찰은 A[i]=3,A[j]=2,A[k]=1인 것을 몇개 쓰고, A[i]=1,A[j]=2,A[k]=3인 것을 몇 개 쓸지를 투 포인터로 체크해야 한다는 것입니다. 그 다음으로는 A[i]=3,A[j]=2,A[k]=1인 것의 개수와 A[i]=1,A[j]=2,A[k]=3의 개수가 주어졌을 때, 이게 가능한지를 O(N)에 체크해야 합니다. A[i]=2인 i를 보면서, 3,2,1 순서인 걸로 넣을 때와 1,2,3 순서로 넣을 때를 체크해줍니다. 각각의 경우에서 2 왼쪽 원소는 가장 왼쪽에 있는 걸로, 2 오른쪽 원소는 가장 오른쪽에 있는 걸로 골라줍시다. 오른쪽 원소를 가장 오른쪽으로 골라도 2 왼쪽인 경우는 앞으로 2들을 체크해도 안 될 것이 분명하므로 불가능을 리턴해주고, 그렇지 않으면 두 순서중 하나만 가능할 때는 그 하나를, 둘 다 가능할 때는 끝이 오른쪽에 있는 것을 골라줍니다(증명은 안 했습니다). 구현에는 그리 어려운 점이 없었습니다

3번:트리에서 정점 a와 정점 b를 있는 기차가 있는데, 기차의 한쪽 끝 간선을 하나 없애고 다른 쪽 끝에 간선을 하나 넣는 연산을 반복해서 정점 c와 d를 있도록 하는데, 연산을 최소로 사용해야 하는 문제입니다. 아마 시작한 뒤 방향을 돌리고 도착점 근처로 쭉 간 뒤, 도착점에서 돌리는 식으로 해결이 가능하다고 생각했는데 답의 리턴 형식이 롱 롱인 것을 보고 다시 생각하려 했지만, 시간이 안 되어서 단순 bfs로 풀 수 있는 11점만 긁게 되었습니다.