23년 8월 11일에 Softeer 7차 정기 역량 진단 시험을 보게 되었다.
Softeer 역량 진단을 보고 취득을 하게 되면 Level 3 인증서를 발급해주는데 해당 인증서가 있으면 다음과 같은 혜택이 있다.
현대자동차, 기아, 현대모비스, 현대오토에버, 현대차증권, 현대엔지비 SW 분야 지원 시, 코딩테스트 면제
(면제 혜택을 적용하는 채용의 경우 채용공고에 명시)
1) 참가 자격 : Softeer 회원 누구나 참여 가능 (단, Talent pool 내 기초 정보, 학력 정보를 입력해야 접수 가능)
2) 일정 (접수/평가 온라인 진행) : 2023년 8월 11일(금) 17:00 ~ 20:00
3) 세부 사항 (시험 참여 방법 안내는 접수 마감 후 8/10(목) 일괄 안내 예정)
- 언어: C, C++, Java, Python, Javascript 중 자유롭게 선택하여 풀이
(테스트 지원언어 : C11, C++17, Java 11, Python 3.6, Node.js 12.18.3)
- 출제 문항: 2문항
- 자격 부여: 2문항 전부를 맞춘 인원에게 Lv. 3 인증서 발급
- 유효 기간: 발급일로부터 2년
Softeer
softeer.ai
다른 회차 Softeer 문제는 위의 링크에서 풀어볼 수 있다.
이번 7회차 시험은 다른 회차에 비해서 난이도가 쉬워진 것을 느꼈다. 시간적으로 많이 여유가 있었고, 시간 복잡도를 생각해보면 쉽게 접근할 수 있었던 문제였던 거 같다.
[1번 문제] 자동차 테스트
Softeer
연습문제를 담을 Set을 선택해주세요. 취소 확인
softeer.ai
* 1 ≤ n ≤ 50,000
* 1 ≤ q ≤ 200,000
* 1 ≤ 자동차의 연비 ≤ 1,000,000,000
* 1 ≤ mi ≤ 1,000,000,000 (i는 1 이상 q 이하입니다. 즉, mi 는 각 질의에 대응하는 중앙값을 의미합니다.)
문제를 보면 알겠지만, 쿼리는 200,000번 그리고 n의 개수는 총 50,000이다.
만약 시간 복잡도를 고려하지 않은채 질의마다 선형탐색을 하면 50,000 * 200,000 으로 10,000,000,000 (100억) 의 연산이 발생한다.
Java 기준, 3초의 시간이 주어졌으므로 알고리즘을 활용해야한다.
크게 두가지로 이 문제를 해결할 수 있는데, 이분 탐색과 해시 맵 활용이다.
1. 이분 탐색
- n개의 값을 정렬 (N*logN) = 50,000 X log 50,000 = 약 800,000 (80만)
- n개의 값만큼 isExist 맵에 저장
- 질의마다 이분 탐색 = 200,000(질의개수) X log 50,000(이분탐색) = 약 3,200,000 (320만)
최악의 경우여도 최대 400만(80만 + 320만)의 연산으로 해당 문제를 해결할 수 있다.
import java.io.*;
import java.util.*;
public class Main {
static int n, q;
static int [] info;
static Map <Integer, Integer> isExist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
q = Integer.parseInt(st.nextToken());
isExist = new HashMap<>();
info = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) info[i] = Integer.parseInt(st.nextToken());
Arrays.sort(info);
for (int i = 0; i < n; i++) isExist.put(info[i], i);
for (int i = 0; i < q; i++) {
int number = Integer.parseInt(br.readLine());
if(isExist.get(number)!=null) sb.append(binarySearch(number)).append("\n");
else sb.append(0).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
static int binarySearch(int number) {
int l = 0;
int h = n-1;
while (l <= h) {
int mid = (l+h)/2;
if (info[mid] == number) {
if(mid==0||mid==n-1)return 0;
return mid * (n - 1 - mid);
}
else if(info[mid]<number) l = mid+1;
else if(info[mid]>number) h = mid-1;
}
return 0;
}
}
2. 해시맵
- n개의 값을 정렬 (N*logN) = 50,000 X log 50,000 = 약 800,000 (80만)
- n개의 값만큼 isExist 맵에 특정 값에 대한 인덱스 위치 저장
- 질의마다 해시맵 탐색 = 200,000(질의개수) X 1(맵 탐색)
return index * (n - 1 - index);
위의 코드는 주어진 넘버의 정렬된 위치의 인덱스 값인데, 해당 인덱스 위치의 왼쪽의 숫자 개수와 오른쪽 숫자 개수를 곱한 연산이다.
1, 2, 3, 4, 5, 6 (n의 개수 = 6개)
만약 4가 중간값일 때 만들 수 있는 경우의 수는 왼쪽 서브 (3개) X 오른쪽 서브 (2개) = 총 6개이다.
4의 인덱스 값은 3이니 위의 식에 대입해보면,
3 * (6 - 1 - 3) = 6
import java.io.*;
import java.util.*;
public class Main {
static int n, q;
static int [] info;
static Map <Integer, Integer> isExist;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
q = Integer.parseInt(st.nextToken());
isExist = new HashMap<>();
info = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) info[i] = Integer.parseInt(st.nextToken());
Arrays.sort(info);
for (int i = 0; i < n; i++) isExist.put(info[i], i);
for (int i = 0; i < q; i++) {
int number = Integer.parseInt(br.readLine());
if(isExist.get(number)!=null) sb.append(hashMap(number)).append("\n");
else sb.append(0).append("\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
static int hashMap(int number) {
int index = isExist.get(number);
if(index==0||index==n-1)return 0;
return index * (n - 1 - index);
}
}
[2번 문제] 순서대로 방문하기
Softeer
연습문제를 담을 Set을 선택해주세요. 취소 확인
softeer.ai
[조건 1] 2 ≤ n ≤ 4
[조건 2] 2 ≤ m ≤ n^2
1. 차량은 n x n 격자 내에서 m개의 지점을 순서대로 방문해야한다.
2. 이동은 항상 상하좌우 중 인접한 칸으로만 이동하되 벽은 지나갈 수 없다.
3. 한 번 지났던 지점은 다시는 방문해서는 안 된다.
이 문제는 백트랙킹을 활용하여 dfs로 푸는 문제이다 .
백트랙킹을 잘 활용하기 위해서 맵을 살짝 수정을 해줘야하는데, 필자는 다음과 같이 수정했다.
이게 무슨말이냐면, 최초에 맵이 주어질 때 0과 1(벽)만 주어진다. 그 후에 M의 개수만큼 방문해야 하는 지점이 순서대로 주어진다. 이때, m이 순서대로 주어지는 그 좌표값에 방문해야할 지점의 순서를 기록하는 것
m이 3일 때,
첫 번째 좌표 값은 시작 지점 (3행 1열)
두 번째 좌표 값은 2번째로 방문해야할 지점 (1행 2열)
세 번째 좌표 값은 3번째로 방문해야할 지점 (2행 3열)
즉, 3행 1열에서 start가 된다면 숫자 2를 찾으러 가는 것이다.
1. 방문했던 지역을 만났을 때 가면 안된다. (visited 2차원 좌표 값이 1일 때)
2. 벽일 때 가면 안된다. (map 2차원 좌표 값이 1일 때)
3. 맵을 초과하면 가면 안된다. (map 2차원 배열 범위를 넘어갔을 때)
4. 방문해야할 순서가 아닌 값에 가면 안된다. (숫자 2를 찾으러 가는데 숫자 3이나 4를 만나면 가면 안된다.)
5. DFS (백트랙킹)
- 방문 처리 1
- 방문해야할 순서 지점에 도착한다면 다음 순서 전달 (2에 도착했다면, 다음 순서는 3 값을 전달)
- 방문해야할 순서 지점이 아니면서 갈 수 있으면 그대로 (다음 순서는 그대로 2 전달)
- 방문 처리 0
import java.io.*;
import java.util.*;
public class Main {
static int [][] map;
static int [][] visited;
static int[] dx = {0, 0, -1, 1};
static int[] dy = {1, -1, 0, 0};
static int n, m;
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][n];
visited = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) map[i][j] = Integer.parseInt(st.nextToken());
}
int[] start = new int[2];
int seq = 2;
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken())-1;
int x = Integer.parseInt(st.nextToken())-1;
if(i==0){
start[0] = y;
start[1] = x;
visited[y][x] = 1;
}
else map[y][x] = seq++;
}
backTracking(start[0], start[1], 2);
sb.append(answer);
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
static void backTracking(int curY, int curX, int next) {
if (next == m+1) {
answer++;
return;
}
for (int i = 0; i < 4; i++) {
int nx = curX + dx[i];
int ny = curY + dy[i];
if(ny<0||ny>=n||nx<0||nx>=n)continue;
if(visited[ny][nx]==1||map[ny][nx]==1) continue;
if(map[ny][nx]>1&&map[ny][nx]!=next)continue;
visited[ny][nx] = 1;
if(map[ny][nx]==next) backTracking(ny, nx, next + 1);
else backTracking(ny, nx, next);
visited[ny][nx] = 0;
}
}
}
댓글