문제
프로그래머스 > 2022 SK ICT Family 신입 개발자 채용 챌린지 > 세번째 문제
언어
JAVA
푼 문제
1 / 4
(해당 문제는 풀지 못했습니다. 시험 끝나고 복기해서 풀었습니다.😭)
풀이시간
4시간
후기
테스트에 사용된 문제를 남기는 것은 저작권에 위배된다고 하여 문제를 올리진 못합니다.
프로그래머스의 '2022 SK ICT Family 신입 개발자 채용 챌린지' 에 대한 자료가 없어서 기록하려고 올립니다.
테스트 보셨던 분들 계시면 댓글 달아주시면 감사하겠습니다.😀
저는 세번째 문제를 4시간에 걸쳐 풀었습니다.
시험 시간에 2시간 시험 끝나고 2시간 정도 풀었네요.
※ 이번 문제에서 시간이 오래 걸렸던 이유
1. BigInteger 사용에 대한 의심.
- 경우의 수를 구하는 문제였는데 단위가 20자리가 넘어갔습니다.
- 계속 다른 값이 나와서 'BigInteger라도 단위가 너무 크면 안되나..'라는
근거없는 의문이 들어 테스트하느라 시간이 좀 걸렸습니다.
2. 주어진 width, height 값은 거리인데 좌표 값으로 계산.
- 시작점 좌표가 ( 1, 1 )이므로 width, height 값에도 +1을 하고 시작했어야 했습니다.
- 테스트가 끝나고 발견하게 되었습니다.
3. 대각선 왼쪽 위에 점을 지나는 경우 대각선 아래 점에서 도착점까지 계산
- 오래걸렸던 주 이유입니다.
- 이것을 발견하는데 3시간이 걸렸네요.
- 대각선 왼쪽 위에 점을 지날 때 반드시 대각선 아래로 내려가는 것이
문제 조건에 있었는데 아주 간단히 지나쳐버렸네요..
- 발견하지 못했던 이유 중 하나는 결과값이 많이 차이가 났었습니다.
- 그렇기 때문에 이런 사소한 문제가 아닌 뭔가 큰 문제가 있을 거라 생각해서
처음부터 다시 보고 다시 보고 했습니다.
- 발견하지 못했던 이유중 두번째는 case를 주어진 2개로만 테스트했던 것입니다.
- 하다 하다 안 돼서 격자 3개짜리로 그려보니 바로 문제를 찾았습니다.
- 앞으로 코딩 테스트할 때 주어진 case 이외에 다른 case를 많이 적용해서
풀어야겠다는 교훈을 얻었습니다. 😡
- 예외나 bug 사항이 많을 만한 case를 생성해보자.
- 내가 손으로 직접 체감이 오는 case를 생성해보자.
그럼 소스 코드 공유드리면서 글 마치겠습니다.
해당 소스는 풀이 방법의 접근이 잘못됐다는 생각도 하고 있어서
혹시나 정답에 가까운 코드나 알고리즘이 있다면 공유 부탁드립니다.!!
소스 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
package SKICTFamily_BE_20220312;
import java.math.BigInteger;
public class PathCntOnGrid {
public static void main(String[] args) {
// (1.1)이 시작점이므로 좌표로 계산하기 위해 width, height 각 +1
// Case1)
// int width = 2;
// int height = 2;
// width += 1;
// height += 1;
// int[][] diagonals = {{1,1},{2,2}};
// Case2)
int width = 51;
int height = 37;
width += 1;
height += 1;
int[][] diagonals = {{17,19}};
// Case3)
// int width = 3;
// int height = 3;
// width += 1;
// height += 1;
// int[][] diagonals = {{1,2}};
// 대각선까지 도달하는 경우의 수 총합
BigInteger sumMinToDiagLeft = new BigInteger("0");
BigInteger sumMinToFinalLeft = new BigInteger("0");
// 대각선부터 도착점까지 도달하는 경우의 수 총합
BigInteger sumMinToDiagRight = new BigInteger("0");
BigInteger sumMinToFinalRight = new BigInteger("0");
BigInteger sumTotalLeft = new BigInteger("0");
BigInteger sumTotalRight = new BigInteger("0");
BigInteger sumTotal = new BigInteger("0");
for (int i = 0; i < diagonals.length; i++) {
int dx = diagonals[i][0];
int dy = diagonals[i][1];
/*
* [ 시작점 ~ 대각선 왼쪽 위의 점까지 거리 ]
* 시작점 좌표 1,1부터 시작하므로 -1해준다.
* ex) ( 1, 1 ) ~ ( 17, 20 ) => { 17 - 1, 20 - 1 } => { 16, 19 }
*
*/
int xToDiagLeft = dx - 1;
int yToDiagLeft = dy + 1 - 1;
/*
* 위에서 구한 x, y좌표 사용.
* 최단 거리의 수 구하는 방법으로 순열을 사용. (!=팩토리얼)
* 공식 : ( x, y )! / (x! * y!)
* ex) ( 16 + 19 )! / (16! * 19!)
*
*/
sumMinToDiagLeft = makeMinPath( xToDiagLeft, yToDiagLeft, xToDiagLeft + yToDiagLeft );
/*
* [ 대각선 오른쪽 아래 점 ~ 도착점까지 경우의 수 ]
* 대각선 왼쪽 위의 점에 도착한 후엔 무조건 오른쪽 아래점으로 이동해야된다.
* 그러므로 오른쪽 아래점부터 ~ 도착점까지 경우의 수 구하면 된다.
* ex) 왼쪽 위의 점 : { 17, 20 } , 오른쪽 아래점 : { 18, 19 }
* ex) (18,19)(51,37) => { 51 - 18, 37 - 19 } => { 33 , 18 }
*
*/
int xToFinalLeft = width - ( dx + 1 );
int yToFinalLeft = height - dy;
// 최단 거리의 수 (위 공식과 동일)
sumMinToFinalLeft = makeMinPath( xToFinalLeft, yToFinalLeft, xToFinalLeft + yToFinalLeft );
/*
* [ 시작점 ~ 대각선 왼쪽 위 * 대각선 왼쪽 위 ~ 도착점까지 경우의 수 ]
* 각 도착점까지의 경우의 수이므로 곱하기를 해준다.
* ex) (1,1)~(17,20) * (17,20) ~ (51,37)
*
*/
sumTotalLeft = sumMinToDiagLeft.multiply(sumMinToFinalLeft);
/*
* [ 시작점 ~ 대각선 오른쪽 아래점까지 거리 ]
* 시작점 좌표 1,1부터 시작하므로 -1해준다.
* ex) ( 1, 1 ) ~ ( 18, 19 ) => { 18 - 1, 19 - 1 } => { 17, 18 }
*
*/
int xToDiagRight = dx + 1 - 1;
int yToDiagRight = dy - 1;
// 최단 거리의 수 (위 공식과 동일)
sumMinToDiagRight = makeMinPath( xToDiagRight, yToDiagRight, xToDiagRight + yToDiagRight );
/*
* [ 대각선 왼쪽 위의 점 ~ 도착점까지 경우의 수 ]
* 대각선 오른쪽 아래점에 도착한 후엔 무조건 왼쪽 위의점으로 이동해야된다.
* 그러므로 왼쪽 위의 점부터~도착점까지 경우의 수 구하면 된다.
* ex) 오른쪽 아래점 : { 18, 19 }, 왼쪽 위의 점 : { 17, 20 }
* ex) (17,20)(51,37) => { 51 - 17, 37 - 20 } => { 34 , 17 }
*
*/
int xToFinalRight = width - dx;
int yToFinalRight = height - ( dy + 1 );
// 최단 거리의 수 (위 공식과 동일)
sumMinToFinalRight = makeMinPath( xToFinalRight, yToFinalRight, xToFinalRight + yToFinalRight );
/*
* [ 시작점 ~ 대각선 왼쪽 위 * 대각선 왼쪽 위 ~ 도착점까지 경우의 수 ]
* 각 도착점까지의 경우의 수이므로 곱하기를 해준다.
*
*/
sumTotalRight = sumMinToDiagRight.multiply(sumMinToFinalRight);
/*
* [대각선 왼쪽 위점을 지나는 경우의 수, 오른쪽 아래점을 지나는 각각 경우의 수를 더해준다.]
*
*/
sumTotal = sumTotal.add(sumTotalLeft);
sumTotal = sumTotal.add(sumTotalRight);
}
// 문제에 나온 총 경우의 수를 10000019로 나눠준다.
BigInteger divide = new BigInteger("10000019");
System.out.println("mod:"+sumTotal.mod(divide));
}
public static BigInteger makeMinPath(int diagX, int diagY, int diagXY) {
BigInteger diagXFac = factorial(diagX);
BigInteger diagYFac = factorial(diagY);
BigInteger diagXYFac = factorial(diagXY);
/*
* 격자 최단 거리 구하기
* 도착점까지 거리가 x, y 인 경우 ( x + y )! / (x! * y!)
*
*/
BigInteger minPath = diagXYFac.divide((diagXFac.multiply(diagYFac)));
return minPath;
}
public static BigInteger factorial (int num) {
BigInteger bigInteger = new BigInteger("1");
for ( int i = 1; i <= num; i++ )
{
bigInteger = bigInteger.multiply(bigInteger.valueOf(i));
}
return bigInteger;
}
}
|
cs |
출처
프로그래머스 2022 SK ICT Family 신입 개발자 채용 챌린지
혹시나 코드 공유해주실 분 댓글 달아주시면 감사하겠습니다~🐢🐢🐢
필기 내용
 |
'코딩 테스트' 카테고리의 다른 글
| [프로그래머스] 신고 결과 받기 (0) | 2023.06.04 |
|---|---|
| [프로그래머스] 기능 개발 (0) | 2022.03.17 |
| [프로그래머스] 2022 SK ICT Family 신입 개발자 채용 챌린지(BE직무) - 첫번째 문제 (0) | 2022.03.14 |
| [프로그래머스] 2022 Dev-Matching: 게임 프로그래머 테스트 (0) | 2022.03.08 |
| [프로그래머스] 숫자 문자열과 영단어 (0) | 2022.03.01 |
