안녕하세요. Softeer 운영 담당자 입니다.

지난 12월 21일에 Softeer 3회 정기 인증평가가 실시되었습니다.

이번 역량 진단에도 많은 분들께서 관심을 가지고 참여하여 주셨습니다.

인증을 받으신 분들께는 축하의 말씀을 전하고, 아깝게 떨어지신 분들께는 안타까운 마음을 전합니다.

금번 평가문제는 연습문제를 통해 확인하실 수 있으며, 문제 해설과 풀이 방법을 공유하오니 역량을 키우시는 데 조금이나마 도움이 되셨으면 좋겠습니다.

향후 정기 인증평가 문제도 연습문제와 문제해설을 업로드 할 계획이니, 많은 관심을 가지고 인증평가에 참여해주시면 감사하겠습니다.

1번 문제

플레이페어 암호

풀이 권장 시간 : 75 분

풀이방법

문제의 설명대로 키를 5X5크기의 표로 만들고, 메시지를 두 글자로 나눈 다음, 표를 보며 두 글자를 암호문으로 바꾸어 출력하면 됩니다.

1) 표 만들기

표를 만들기 위해서는 알파벳 대문자를 행과 열 위치로 바꾸는 배열 aToTable과, 행과 열 위치를 받아서 알파벳 대문자로 바꾸는 배열 tableToA두 개를 만들어야 합니다.

우선 각각의 알파벳 대문자가 키에서 나타났는지를 저장하는 배열을 만들어둡니다.

키를 앞에서부터 한 글자씩 읽으면서, 전에 나타난 적이 없는 문자라면 표의 왼쪽 위부터 채워나갑니다.

지금까지 표에 적은 알파벳 수를 idx라는 변수로 저장하면서, idx / 5 를 행 번호로, idx % 5를 열 번호로 하여 aToTable 에 알파벳 대문자를 저장하면 됩니다.

aToTable 배열은 pair 자료구조를 사용하여 행과 열 번호 두 개를 저장하셔도 되고, idx를 그대로 저장하신 뒤 나중에 idx / 5로 행 번호를, idx % 5로 열 번호를 찾으셔도 됩니다.

tableToA는 반대로 행과 열 위치마다 알파벳 대문자를 저장합니다.

키를 다 읽은 후, 알파벳 A 부터 Z 까지 전에 나타난 적이 있었는지를 확인하고, 그렇지 않다면 idx를 통해 위치를 판단하면서 남은 표를 채웁니다.

이 때 문제의 조건상 J가 등장하지 않기 때문에, J일 때는 표를 채우지 않고 생략합니다.

2) 메시지를 두 글자씩 나누기

쌍을 만들기 위해 반복문을 돌며 메시지를 앞부터 읽어나갑니다. 다음의 조건을 만족하는지 확인합니다.

메시지의 마지막 문자만 남은 경우, 두 번째 문자로 X를 추가하여 쌍을 만듭니다.

현재 문자와 다음 문자가 같은 경우, 현재 문자가 X라면 Q를, 아니라면 X를 추가합니다. 다음 반복에서는 다음 문자를 읽습니다.

그 밖의 경우에는 현재 문자와 다음 문자 그대로 쌍을 만들면 됩니다. 이 때 다음 반복에서는 다다음 문자를 읽습니다.

3) 메시지 암호화 하기

tableToA를 참고하여 쌍을 이룬 두 문자의 행과 열 위치를 확인합니다. 같은 행, 같은 열, 행과 열이 모두 다른 경우 각각에 맞추어 암호화된 문자 두 개를 출력합니다.

행이 같은 경우를 예시로 들겠습니다. 암호화된 문자는 같은 행의 오른쪽 한 칸 옆에, 위치가 다섯 번째 열이라면 첫 번째 열에 있는 글자입니다.

행과 열 번호 모두 0부터 4의 값으로 저장했으므로, 기존 행의 위치를 r, 열의 위치를 c라고 할 때, 암호화된 문자는 표에서 r행 (c+1) % 5열에 있습니다.

이런 방식으로 암호화된 문자들을 모두 출력하면 됩니다.

2번 문제

교차로

풀이권장 시간 : 75분

풀이방법

방향별 도로의 상황을 네 개의 큐로 관리하며, 시간 순서대로 시뮬레이션을 진행합니다.

1) 초기화

각각의 도로에서는 먼저 진입한 차가 먼저 통과하므로 도로를 큐로 구현합니다.

또한 차량을 진행할 때 오른쪽 도로의 상황을 살펴보므로 4개의 도로는 큐의 배열로 구현합니다.

이 때 도로를 방향별로 d-'A'번 위치에 저장하여, d방향 도로에서 오른쪽에 있는 (d+3) % 4방향의 도로를 확인하도록 합니다.

차량별로 통과한 시각 배열을 만들어서 -1로 초기화한 다음, 시뮬레이션을 하면서 차량이 통과할 때마다 그 시각으로 값을 바꾸어줍니다.

2) 차량 진입시키기

문제의 입력은 시간 순서이므로, 그대로 차량을 진입시킵니다.

같은 시간대에 진입한 차량은 동시에 처리해야하므로, 다른 시간대의 차량이 진입할 때까지는 도로의 차량을 진입시키기만 하고 통과시키지는 않습니다.

이 때, 차량이 진입한 시간대를 비교하기 위해 이전에 진입한 차량 시간을 prevTime이라는 변수에 저장해두고,

지금 진입하려는 차량의 시간 time과 비교한 다음 차량을 진입시킨 후 갱신하면 됩니다.

차량을 진입시킬 때는 해당하는 도로 큐에 현재 차량 번호를 넣으면 됩니다.

3) 차량 통과시키기

prevTime초와 다른 time초에 새로운 차량이 진입하려고 한다면, 진입시키기 전에 현재 도로에 있는 차량들을 살펴봅니다.

prevTime 이상 time미만 매 초 current마다, d방향 도로에 차가 있으면서 (d+3) % 4가 있다면, d도로에 통과할 차량이 있다고 기록합니다.

만약 모든 도로가 비어있다면, 통과시킬 기존 차량이 없으므로 바로 time초에 차량을 진입시킵니다.

만약 모든 도로에 차가 있지만, 통과할 차량이 없다면 교착 상태입니다. 현재 차량을 포함하여 더 이상 차량이 통과하지 못하므로 차량 진입과 통과를 중단합니다.

그 밖의 경우에는 통과할 수 있는 방향마다 차량을 한 대씩 통과시킵니다.

도로를 구현한 큐에서 차량 번호를 꺼내어, 위에서 만든 차량별로 통과한 시각 배열에 차량이 통과한 시각 current를 기록합니다.

time 시간 전까지 통과할 수 있는 차량을 모두 통과했다면, time초에 들어올 차량을 진입시키면 됩니다.

마지막으로 차량별로 통과한 시각 배열을 읽으며 값을 출력합니다.