들어가기 앞서
현대자동차그룹 SW 검정 시험 느낌이다.
해당 시험을 통과하면, 정해진 레벨에 따라
코딩테스트 전형이 면제되기도 한다.
현재 정답률은 아래 사진과 같다!
(순서대로 방문하기 문제의 썸네일이 귀엽다.)
문제는 아래 소프티어 사이트에서 확인할 수 있다.
https://softeer.ai/practice/index.do
1번 자동차 테스트
문제
자동차 제조 과정에서는 다양한 테스트를 통해 해당 자동차가 잘 만들어졌는지를 평가합니다.
이러한 평가 지표 중 하나는 자동차의 연비입니다.
자동차의 연비가 높을수록 연료 소비가 적고, 더 많은 거리를 주행할 수 있으므로 이는 자동차가 잘 만들어졌는지의 지표로 사용될 수 있습니다.
만약 3대의 자동차를 테스트하고, 각각의 연비를 측정한다고 가정해봅시다.
첫 번째 자동차의 연비는 9km/L,
두 번째 자동차의 연비는 15km/L,
세 번째 자동차의 연비는 20km/L이라고 합시다.
이 경우, 중앙값은 15km/L이 됩니다.
따라서 이 데이터에서는 중앙값을 이용하여 자동차의 평균적인 연비를 파악할 수 있으며,
이는 자동차 제조 과정에서 테스트의 결과를 평가하는 데 활용될 수 있습니다.
n대의 자동차를 새로 만들었지만 여건상 3대의 자동차에 대해서만 테스트가 가능한 상황입니다.
n대의 자동차의 실제 연비 값이 주어졌을 때, q개의 질의에 대해 임의로 3대의 자동차를 골라 테스트하여 중앙값이 mi값이 나오는 서로 다른 경우의 수를 구하는 프로그램을 작성해보세요.
TC
입력예제1
5 3
5 2 3 1 6
1
3
6
출력예제1
0
4
0
입력예제2
6 8
7 4 3 2 6 1
1
2
3
4
5
6
7
1000000000
출력예제2
0
4
6
6
0
4
0
0
물론 문제를 잘 읽어서 이해하는것도 풀이중 중요한 요소지만,
바쁜 현대인을 위해 요약하자면
자동차의 여러 연비값들이 주어진다 (n개).
어떤 연비값 x가 주어진다.
해당 모든 연비값들 중에서 3개의 연비를 뽑았을때 (n개중 3개),
x가 그 3개의 값중 중간값일 경우의 수를 구하시오.
이다.
예를 들어
연비값 123
어떤 연비값 2이면,
3개를뽑는 경우가 123 한가지인데, 해당 경우의 중간값이 2이므로
경우의 수는 1이 된다.
풀이
풀이는 아래와 같다.
연비값 배열을 정렬한다.
(중간값이 될 경우를 찾아야 하므로 더 작은값, 더 큰값의 개수를 index로 찾기 위해)
경우의 수를 찾기 위해 주어진 입력값의 index를 찾는다.
해당 index가 유효하면 (해당 연비값이 주어진 값들중에 존재한다면)
중간값의 경우를 찾아야 하므로,
해당 연비값보다 작은값들의 수 * 큰값들의 수
를 구하면 된다.
유효하지 않다면 0을 출력하면 된다.
예를 들어 설명하자면,
12345의 정렬된 배열이 있다.
여기서, 3개를 뽑았는데 3이 중간값이 되는 경우의 수를 생각해보면,
ㅁ3ㅁ 에서, ㅁ에 들어갈 경우의 수를 생각해보자.
첫번째 ㅁ 에서는 1과 2
두번째 ㅁ 에서는 4와 5.
총 2 * 2 = 4의 경우의 수가 나온다.
이 예시가 위 두꺼운 글씨의 풀이를 설명한 것이다.
여기서, 더 알아야 할 내용이 크기가 오름, 내림차순으로 정렬된 숫자들중 원하는 숫자를 찾는 로직인 이분탐색을 사용했다
코드
코드는 다음과 같고, 주석을 통해 설명하겠다
import java.util.*;
import java.io.*;
public class Main {
static int n,q;
static int[] cars;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st1 = new StringTokenizer(br.readLine());
n = Integer.parseInt(st1.nextToken()); //전체 차의 수
q = Integer.parseInt(st1.nextToken()); //케이스 경우의 수
cars = new int[n]; //자동차 연비들
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i = 0 ; i < n ; i++) {
cars[i] = Integer.parseInt(st2.nextToken());
}
Arrays.sort(cars); //정렬
for(int i = 0 ; i < q ; i++) {
int want = Integer.parseInt(br.readLine());
int idx = findIdx(want);
//처음과 끝이라면 중간값일 수 없음
if(want == cars[0] || want == cars[n-1]) {
bw.write(String.valueOf(0) + "\n");
}
//해당 매서드에서 -1이 나온다면 유효하지 않은 값
else if(findIdx(want) == -1) {
bw.write(String.valueOf(0) + "\n");
}
//유효한 값이 나왔다면, 중간값의 경우의 수를 입력해줌
else {
bw.write(String.valueOf(idx * (n-idx-1)) + "\n");
}
}
bw.flush();
bw.close();
}
static int findIdx(int want) { //index를 찾는 이분탐색
int s = 0;
int e = n;
while(s < e) {
int m = (s+e)/2;
if(cars[m] > want) {
e = m;
}
else if(cars[m] < want) {
s = m+1;
}
else {
return m;
}
}
//-1은 유효하지 않은 값.
return -1;
}
}2번 순서대로 방문하기
문제
Sam은 팀장님으로부터 차량이 이동 가능한 시나리오의 수를 찾으라는 업무 지시를 받았습니다. 이동은 숫자 0과 1로만 이루어져 있는 n x n 크기의 격자 위에서 일어납니다. 숫자 0은 빈 칸을 의미하며, 숫자 1은 해당 칸이 벽으로 막혀 있음을 의미합니다. 아래는 n이 3인 경우의 예시입니다.
0 0 0
0 0 0
0 0 1
차량은 n x n 격자 내에서 m개의 지점을 순서대로 방문하려고 합니다. 이 때 이동은 항상 상하좌우 중 인접한 칸으로만 이동하되 벽은 지나갈 수 없으며, 한 번 지났던 지점은 다시는 방문해서는 안 됩니다. 이러한 조건 하에서 차량이 이동 가능한 서로 다른 가지 수를 구하는 프로그램을 작성해보세요.
방문해야 하는 지점의 첫 지점이 출발점이며, 마지막 지점이 도착점임에 유의합니다.
위의 예에서 m = 3, 방문해야 하는 지점이 순서대로 (3행, 1열), (1행, 2열), (2행, 3열)이라면, 다음과 같이 5가지의 시나리오가 가능합니다.
- (3행, 1열) → (3행, 2열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)
- (3행, 1열) → (3행, 2열) → (2행, 2열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)
- (3행, 1열) → (2행, 1열) → (2행, 2열) → (1행, 2열) → (1행, 3열) → (2행, 3열)
- (3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (1행, 3열) → (2행, 3열)
- (3행, 1열) → (2행, 1열) → (1행, 1열) → (1행, 2열) → (2행, 2열) → (2행, 3열)
해당 그림의 입출력 예제는 아래와 같다.
입력예제1
3 3
0 0 0
0 0 0
0 0 1
3 1
1 2
2 3
출력예제1
5
문제의 요약은 다음과 같다.
그래프와 여러 점들이 주어질 때, 해당 점들을 주어진 순서대로 방문하며 마지막 점까지 도달할 수 있는 경로의 수를 구해라.
풀이
정답률을 보면 사람들은 1번을 더 많이 헷갈려 하는 것 같지만,
나는 이 문제를 애먹었다.
흔히 모든 경로를 구하는 백트래킹 문제는 풀 줄 알았지만,
단 두 점의 경로를 구할 줄 알았지(ex : A -> B) ,
여러 점들의 경로 (ex : A -> B -> C -> D) 를 구하는 방법은 미숙했다.
해당 미숙한 방법을 다음과 같이 해결했다.
- 방문할 모든 점들을 배열로 저장한다. (goals)
- 해당 점들을 백트래킹의 깊이(idx)로 표현한다.
(goals.get(idx) == idx번째로 방문해야 할 점)
이렇게 쪼개면, idx에 따라 목표하는 점이 달라지게 된다.
예를 들어
idx = 2 일때는 주어진 점들의 index중 0, 1, 2 세번째 점이 목표지점이고, 해당 점을 향해 백트래킹으로 전진한다.
idx = 4 일때는 주어진 점들의 index중 0, 1, 2, 3, 4 다섯번째 점이 목표지점이고, 해당 점을 향해 백트래킹으로 전진한다.
즉,
이동하며 goals.get(idx)의 점을 밟게 되면 goals.get(idx+1)의 점을 찾아 떠나는 로직이다.
이동은 여타 다른 그래프 문제와 같이
r + dr[i], c + dc[i] 로 해결했다.
코드
코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
static int n; //행과 열의 크기
static int[][] map;
static boolean[][] visited;
static ArrayList<int[]> goals; //방문점 순서대로
static int answer = 0;
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st1 = new StringTokenizer(br.readLine());
n = Integer.parseInt(st1.nextToken());
int a = Integer.parseInt(st1.nextToken());
map = new int[n][n];
visited = new boolean[n][n];
for(int i = 0 ; i < n ; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int j = 0 ; j < n ; j++) {
map[i][j] = Integer.parseInt(st2.nextToken());
}
}
goals = new ArrayList<>();
for(int i = 0 ; i < a ; i++) {
StringTokenizer st3 = new StringTokenizer(br.readLine());
goals.add(new int[] {Integer.parseInt(st3.nextToken()), Integer.parseInt(st3.nextToken())});
}
//맨 처음 점 방문체크해주기 (백트래킹 로직에 없으니)
visited[goals.get(0)[0]-1][goals.get(0)[1]-1] = true;
backTracking(1, goals.get(0)[0]-1, goals.get(0)[1]-1);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
//백트래킹
static void backTracking(int idx, int r, int c) {
if(idx == goals.size()-1) { //마지막 점을 목표로 갈 때
//해당 마지막 점에 도달한다면
if(goals.get(idx)[0]-1 == r && goals.get(idx)[1]-1 == c) {
answer++;
return;
}
}
//마지막 점이 아닌 점을 목표로 갈때 해당 점에 도달한다면
else if(goals.get(idx)[0]-1 == r && goals.get(idx)[1]-1 == c) {
backTracking(idx+1, r, c);
return;
}
for(int i = 0 ; i < 4 ; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if(isValid(nr, nc)) {
visited[nr][nc] = true;
backTracking(idx, nr, nc);
visited[nr][nc] = false;
}
}
}
//행렬 index유효한지, 방문안했는지, map 값이 유효한지지
static boolean isValid(int r, int c) {
if(r >= 0 && r < n && c >= 0 && c < n && map[r][c] == 0 && !visited[r][c]) return true;
return false;
}
}backTracking(idx, nr, nc); -> 현재 점에서, 그래프를 탐색하기
backTracking(idx+1, r, c); -> 다음 점(idx+1)을 목표로 시작하기
이 둘의 차이가 이해가 간다면, 해당 문제는 쉽게 이해가 갈 것이다.
개선해야 할 부분 :
여러 점의 경로의 수를 구하는법 기억하기
(A -> B -> C -> ...),
이동하며 visited를 true로 만들어줄 때, 가장 처음 점 또한 true 로 만들어주기
(visited[goals.get(0)[0]-1][goals.get(0)[1]-1] = true;)
위 안해서 많이 시간 잡아먹음
r, c는 시작할 때, 0행 0열이라는 점 기억하기2번 문제에서 배워가는것이 많다고 생각한다.
너무 아쉽다.
실제 코테에서 아쉬운 상황을 줄이기 위해,
숙지하고 있고 계속해서 노력해야겠다.
