문제

https://programmers.co.kr/learn/courses/30/lessons/17680


코드

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
private static final int MISS_RUN_TIME = 5;
public int solution(int cacheSize, String[] cities) {
if (cacheSize == 0) {
return cities.length * MISS_RUN_TIME;
}

Map<String, Integer> lru = new LinkedHashMap<String, Integer>(cacheSize, 1, true){
@Override
public boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
return size() > cacheSize;
}
};

int answer = 0;
for(String key : cities) {
key = key.toLowerCase();

if(lru.containsKey(key)) {
lru.get(key);
answer += 1;
} else {
lru.put(key, 0);
answer += MISS_RUN_TIME;
}
}

return answer;
}

흐름

  1. 캐시가 0인 경우엔 캐시에 저장 할 수 없으니 항상 miss 이므로 배열의 크기 만큼 5를 곱해서 return 한다.
  2. LinkedHashMap의 경우 accessOrder parameter를 통해 Map의 순서를 access 기준으로 변경 할 수 있는데 우리는 LRU, 즉 가장 오래 사용되지 않은 데이터를 삭제 해야하므로 accessOrder를 true로 갖는 생성자로 LinkedHashMap 인스턴스를 생성한다.
  3. 그 후 removeEldestEntry()를 override해서 캐시의 크기보다 Map의 사이즈가 커질 경우 가장 오래 사용되지 않은 데이터를 삭제하도록 수정한다.
  4. 배열에서 문자열을 가져오면서 Map에 저장되어 있는지 비교한다.
  5. Map에 저장되어 있다면, get()을 통해 access하고 1초를 더한다.
  6. 저장되어 있지 않다면, put 하는데 이 때 Map의 크기가 캐시보다 크다면 아까 Override 한 removeEldestEntry()에 의해 가장 오래 사용되지 않은 값이 삭제되면서 지금 put한 데이터가 추가한다.
  7. 캐시에 없는 데이터를 추가했으니 5초를 더한다.
  8. 모든 초를 더한 값을 return 한다.

결과

번호 속도
테스트 1 통과 (1.11ms, 52.1MB)
테스트 2 통과 (1.20ms, 52.2MB)
테스트 3 통과 (1.08ms, 50.9MB)
테스트 4 통과 (1.23ms, 51.7MB)
테스트 5 통과 (0.94ms, 52.4MB)
테스트 6 통과 (0.78ms, 50.2MB)
테스트 7 통과 (0.78ms, 52.2MB)
테스트 8 통과 (1.12ms, 52.7MB)
테스트 9 통과 (1.15ms, 50.8MB)
테스트 10 통과 (1.34ms, 52.4MB)
테스트 11 통과 (45.53ms, 89.6MB)
테스트 12 통과 (1.45ms, 52.5MB)
테스트 13 통과 (1.43ms, 52.5MB)
테스트 14 통과 (1.69ms, 52.7MB)
테스트 15 통과 (2.42ms, 50.5MB)
테스트 16 통과 (2.85ms, 52.9MB)
테스트 17 통과 (0.78ms, 52MB)
테스트 18 통과 (4.34ms, 53.5MB)
테스트 19 통과 (4.28ms, 53.3MB)
테스트 20 통과 (4.15ms, 50.9MB)

테스트 케이스

1
2
3
4
5
6
7
8
assertEquals(42, test.solution(3, new String[]{"Jeju", "Pangyo", "Jeju", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
assertEquals(50, test.solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
assertEquals(21, test.solution(3, new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"}));
assertEquals(60, test.solution(2, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
assertEquals(52, test.solution(5, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
assertEquals(16, test.solution(2, new String[]{"Jeju", "Pangyo", "NewYork", "newyork"}));
assertEquals(25, test.solution(0, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
assertEquals(18, test.solution(1, new String[]{"LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA", "LA"}));

참고 사이트

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/42842


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] solution(int brown, int yellow) {
int sum = brown + yellow;
int[] answer = new int[2];

for (int i = 2; i < sum; i++) {
if (sum % i == 0) {
int x = ((sum / i) * 2) + ((i * 2) - 4);
int y = sum - x;

if (brown == x && yellow == y) {
answer = new int[] {sum / i, i};
break;
}
}
}
return answer;
}

흐름

  1. 갈색과 노란색을 더해 전체 크기를 구한다.
  2. 전체 크기를 2부터 반복한다. (1인 경우는 없으므로)
  3. i로 sum을 나눠서 떨어진다면, 즉 약수라면
  4. sum에서 i를 나눈 값에 2를 곱해서 위 아래 가로의 길이를 구하고
  5. i에 마찬가지로 2를 곱해서 좌 우 세로의 길이를 구하고
  6. 꼭지점들은 가로 세로가 겹치므로 -4를 한다.
  7. 이렇게 구한 갈색을 sum에서 빼서 노란색의 값을 구한다.
  8. 구한 갈색과 노란색 값이 넘겨받은 brown과 yellow와 같으면 끝
  9. 아니라면 반복한다.

결과

번호 속도
테스트 1 통과 (1.57ms, 52.3MB)
테스트 2 통과 (1.76ms, 51.1MB)
테스트 3 통과 (1.88ms, 50.1MB)
테스트 4 통과 (1.44ms, 52.7MB)
테스트 5 통과 (1.52ms, 50.5MB)
테스트 6 통과 (1.48ms, 49.8MB)
테스트 7 통과 (1.62ms, 50.8MB)
테스트 8 통과 (1.52ms, 52.6MB)
테스트 9 통과 (1.58ms, 52.4MB)
테스트 10 통과 (1.58ms, 50.4MB)
테스트 11 통과 (1.53ms, 53MB)
테스트 12 통과 (1.56ms, 52.3MB)
테스트 13 통과 (1.48ms, 53.3MB)

테스트 케이스

1
2
3
assertArrayEquals(new int[]{4, 3}, test.solution(10, 2));
assertArrayEquals(new int[]{3, 3}, test.solution(8, 1));
assertArrayEquals(new int[]{8, 6}, test.solution(24, 24));

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/42888


코드

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

private static final String ENTER = "Enter";
private static final String LEAVE = "Leave";
private static final String CHANGE = "Change";

private static final String MESSAGE_ENTER = "님이 들어왔습니다.";
private static final String MESSAGE_LEAVE = "님이 나갔습니다.";

public String[] solution(String[] record) {
List<String[]> list = new ArrayList<>();
Map<String, String> nickName = new HashMap<>();

int returnArraySize = 0;
for (String s : record) {
String[] split = s.split(" ");
String[] actionAndUid = new String[3];

actionAndUid[0] = split[0];
actionAndUid[1] = split[1];

if (!CHANGE.equals(split[0])) {
list.add(actionAndUid);
returnArraySize++;
}

if (!LEAVE.equals(split[0])) {
nickName.put(split[1], split[2]);
}
}

String[] answer = new String[returnArraySize];
int i = 0;
for (String[] array : list) {
switch (array[0]) {
case ENTER :
answer[i] = nickName.get(array[1]) + MESSAGE_ENTER;
break;
case LEAVE :
answer[i] = nickName.get(array[1]) + MESSAGE_LEAVE;
break;
}

i++;
}

return answer;
}

흐름

  1. 문자열을 공백으로 나눠서 행동과 유저의 아이디를 저장하는 배열에 담는다.
  2. 행동이 Change가 아닌 경우엔 채팅방에 입장했거나 나갓다는 문구룰 출력해야 하기 때문에 List에 담는다.
  3. 행동이 Leave가 아닌 경우엔 닉네임이 변경되었거나, 새로 방에 들어온 것이므로 유저 아이디를 key로하는 map에 value로 닉네임을 저장한다.
  4. 모두 저장했으면 List만큼 돌면서 해당 행동에 맞는 문자열을 만들어 저장한다.

결과

번호 속도
테스트 1 통과 (18.70ms, 54.1MB)
테스트 2 통과 (17.35ms, 52.4MB)
테스트 3 통과 (17.84ms, 54.4MB)
테스트 4 통과 (19.81ms, 54MB)
테스트 5 통과 (27.75ms, 56.1MB)
테스트 6 통과 (30.38ms, 56.1MB)
테스트 7 통과 (35.26ms, 54.4MB)
테스트 8 통과 (27.59ms, 55.2MB)
테스트 9 통과 (30.72ms, 56.5MB)
테스트 10 통과 (28.67ms, 56.1MB)
테스트 11 통과 (25.16ms, 56.2MB)
테스트 12 통과 (26.04ms, 56.6MB)
테스트 13 통과 (26.07ms, 55MB)
테스트 14 통과 (43.84ms, 57.2MB)
테스트 15 통과 (20.35ms, 52.4MB)
테스트 16 통과 (18.03ms, 52.8MB)
테스트 17 통과 (19.77ms, 54.2MB)
테스트 18 통과 (18.86ms, 52.5MB)
테스트 19 통과 (35.94ms, 56.7MB)
테스트 20 통과 (26.22ms, 55.5MB)
테스트 21 통과 (30.18ms, 56.5MB)
테스트 22 통과 (28.53ms, 52.5MB)
테스트 23 통과 (29.40ms, 57.5MB)
테스트 24 통과 (37.73ms, 57.3MB)
테스트 25 통과 (262.95ms, 158MB)
테스트 26 통과 (292.57ms, 158MB)
테스트 27 통과 (333.29ms, 169MB)
테스트 28 통과 (324.94ms, 163MB)
테스트 29 통과 (282.87ms, 157MB)
테스트 30 통과 (286.21ms, 153MB)
테스트 31 통과 (225.37ms, 147MB)
테스트 32 통과 (255.96ms, 137MB)

테스트 케이스

1
2
3
String[] actual = {"Enter uid1234 Muzi", "Enter uid4567 Prodo","Leave uid1234","Enter uid1234 Prodo","Change uid4567 Ryan"};
String[] expected ={"Prodo님이 들어왔습니다.", "Ryan님이 들어왔습니다.", "Prodo님이 나갔습니다.", "Prodo님이 들어왔습니다."};
assertArrayEquals(expected, test.solution(actual));

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/12949


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[][] solution(int[][] arr1, int[][] arr2) {
int[][] answer = new int[arr1.length][arr2[0].length];

for (int i = 0; i < arr1.length; i++) {
for(int j = 0; j < arr2[0].length; j++){
for (int k = 0; k < arr2.length; k++) {
answer[i][j] += arr1[i][k] * arr2[k][j];
}
}
}

return answer;
}

흐름

  1. 행렬의 곱은 앞 행렬의 행과 뒤 행렬의 열을 곱한 것과 같다.
    • ex) 앞 행렬이 m x n 크기이고 뒤 행렬이 n x r 크기인 경우 곱은 m x r크기의 행렬이 된다.
  2. 곱 행렬(0, 0)은 앞 행렬의 (0, 0) X 뒷 행렬 (0, 0) + 앞 행렬 (0, 1) X 뒷 행렬 (1, 0)
  3. (0, 1)은 (0, 0) X (0, 1) + (0, 1) X (1, 1)
  4. (1, 0)은 (1, 0) X (0, 0) + (1, 1) X (0, 1)
  5. (1, 1)은 (1, 0) X (0, 1) + (1, 1) X (1, 1)
  6. (2, 0)은 (2, 0) X (0, 0) + (2, 1) X (0, 1)
  7. (2, 1)은 (2, 0) X (0, 1) + (2, 1) X (1, 1)
  8. 이런식으로 진행된다.

결과

번호 속도
테스트 1 통과 (2.93ms, 54.1MB)
테스트 2 통과 (10.09ms, 54.3MB)
테스트 3 통과 (17.85ms, 56.7MB)
테스트 4 통과 (2.02ms, 50.9MB)
테스트 5 통과 (8.78ms, 53.7MB)
테스트 6 통과 (9.40ms, 56.2MB)
테스트 7 통과 (1.56ms, 52.3MB)
테스트 8 통과 (1.80ms, 50.7MB)
테스트 9 통과 (1.79ms, 50.1MB)
테스트 10 통과 (8.66ms, 54.9MB)
테스트 11 통과 (3.37ms, 52.3MB)
테스트 12 통과 (2.05ms, 54.6MB)
테스트 13 통과 (9.96ms, 54.1MB)
테스트 14 통과 (10.60ms, 54.3MB)
테스트 15 통과 (7.94ms, 54.1MB)
테스트 16 통과 (4.86ms, 54.6MB)

테스트 케이스

1
2
assertArrayEquals(new int[][] {{15, 15}, {15, 15}, {15, 15}}, test.solution(new int[][] {{1, 4}, {3, 2}, {4, 1}}, new int[][] {{3, 3}, {3, 3}}));
assertArrayEquals(new int[][] {{22, 22, 11}, {36, 28, 18}, {29, 20, 14}}, test.solution(new int[][] {{2, 3, 2}, {4, 2, 4}, {3, 1, 4}}, new int[][] {{5, 4, 3}, {2, 4, 1}, {3, 1, 1}}));

참고 사이트

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/12913


코드

1
2
3
4
5
6
7
8
9
10
11
12
int solution(int[][] land) {
for (int i = land.length - 2; i >= 0; i--) {
int rowIndex = i + 1;
land[i][0] += max(land[rowIndex][1], max(land[rowIndex][2], land[rowIndex][3]));
land[i][1] += max(land[rowIndex][0], max(land[rowIndex][2], land[rowIndex][3]));
land[i][2] += max(land[rowIndex][0], max(land[rowIndex][1], land[rowIndex][3]));
land[i][3] += max(land[rowIndex][0], max(land[rowIndex][1], land[rowIndex][2]));
}

int answer = max(land[0][0], max(land[0][1], max(land[0][2], land[0][3])));
return answer;
}

흐름

  1. 마지막 행 전행 부터 반복문을 시작해서 i가 0이 될 때까지 반복한다.
  2. i행의 각 인덱스에는 자기 자신의 열을 제외한 이전 행의 값 중 가장 큰 값과 자기 자신의 값을 더한 값을 저장한다.
  3. 위 과정을 반복하면 0번째 행들의 index에 계산된 값들이 할당되어 있을 테니
  4. 0 번째 행 중에서 가장 큰 값을 return한다.

결과

정확성

번호 속도
테스트 1 통과 (1.05ms, 51.1MB)
테스트 2 통과 (1.16ms, 52.7MB)
테스트 3 통과 (1.16ms, 50.8MB)
테스트 4 통과 (1.18ms, 53MB)
테스트 5 통과 (1.18ms, 52.7MB)
테스트 6 통과 (1.14ms, 52.9MB)
테스트 7 통과 (1.18ms, 51.4MB)
테스트 8 통과 (1.13ms, 52.7MB)
테스트 9 통과 (1.25ms, 53.3MB)
테스트 10 통과 (1.21ms, 50.7MB)
테스트 11 통과 (1.18ms, 52.4MB)
테스트 12 통과 (4.25ms, 52.5MB)
테스트 13 통과 (1.19ms, 53.2MB)
테스트 14 통과 (1.16ms, 53.1MB)
테스트 15 통과 (1.19ms, 51MB)
테스트 16 통과 (1.16ms, 52.5MB)
테스트 17 통과 (1.14ms, 55.3MB)
테스트 18 통과 (1.16ms, 52.2MB)

효율성

번호 속도
테스트 1 통과 (28.10ms, 94.3MB)
테스트 2 통과 (28.01ms, 95.7MB)
테스트 3 통과 (25.28ms, 97.6MB)
테스트 4 통과 (25.93ms, 101MB)

테스트 케이스

1
2
3
4
5
6
7
8
assertEquals(16, test.solution(new int[][] {{1,2,3,5},{5,6,7,8},{4,3,2,1}}));
assertEquals(20, test.solution(new int[][] {{4, 3, 2, 1}, {2, 2, 2, 1}, {6, 6, 6, 4}, {8, 7, 6, 5}}));
assertEquals(115, test.solution(new int[][] {{1, 2, 3, 5}, {5, 6, 7, 8}, {4, 3, 2, 1}, {100, 0, 9, 8}}));
assertEquals(33, test.solution(new int[][] {{1, 2, 3, 5}, {10, 11, 12, 11}, {16, 15, 13, 13}}));
assertEquals(409, test.solution(new int[][] {{1, 100, 15, 3}, {1, 2, 3, 4}, {100, 99, 98, 97}, {97, 98, 99, 100}, {4, 3, 2, 1}, {100, 100, 100, 100}, {1, 1, 1, 1}}));
assertEquals(16, test.solution(new int[][] {{1, 2, 3, 4}, {5, 6, 7, 9}, {4, 3, 2, 1}}));
assertEquals(125, test.solution(new int[][] {{9, 5, 2, 3}, {9, 8, 6, 7}, {8, 9, 7, 1}, {100, 9, 8, 1}}));
assertEquals(20, test.solution(new int[][] {{4, 3, 2, 1}, {2, 2, 2, 1}, {6, 6, 6, 4}, {8, 7, 6, 5}}));

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/67257


코드

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
private static final char PLUS = '+';
private static final char MINUS = '-';
private static final char MULTIPLICATION = '*';

public long solution(String expression) {
char[] chars = expression.toCharArray();

Object[] numberAndOperator = getNumbersAndOperatorSet(chars);
List<Long> numberList = (List<Long>) numberAndOperator[0];
List<Character> operatorList = (List<Character>) numberAndOperator[1];

char[] operators = getExpressionIncludeOperators(operatorList);
List<String> operatorSetList = getOperatorSetList(operators);

return getMax(numberList, operatorList, operatorSetList);
}

private Object[] getNumbersAndOperatorSet(char[] expression) {
List<Long> numberList = new ArrayList<>();
List<Character> operatorList = new ArrayList<>();

StringBuilder sb = new StringBuilder();
for (char c : expression) {
switch (c) {
case PLUS:
case MINUS:
case MULTIPLICATION:
numberList.add(Long.valueOf(sb.toString()));
operatorList.add(c);

sb.setLength(0);
break;
default:
sb.append(c);
break;
}
}

numberList.add(Long.valueOf(sb.toString()));

return new Object[] {numberList, operatorList};
}

private char[] getExpressionIncludeOperators(List<Character> operatorList) {
Set<Character> set = new HashSet<>();
List<Character> list = new ArrayList<>();

for (char c : operatorList) {
if (set.add(c)) {
list.add(c);
}
}

char[] operators = new char[list.size()];
int i = 0;
for (char c : list) {
operators[i++] = c;
}

return operators;
}


private List<String> getOperatorSetList(char[] chars) {
List<String> operatorSetList = new ArrayList<>();
Set<String> set = new HashSet<>();

for (int i = 1; i <= chars.length; i++) {
perm(chars, 0, i, operatorSetList, set);
}

return operatorSetList;
}

private void perm(char[] array, int depth, int length, List<String> operatorList, Set<String> set) {
if (depth == length) {

StringBuilder sb = new StringBuilder();
for (char c : array) {
sb.append(c);
}

if (set.add(sb.toString())) {
operatorList.add(sb.toString());
}

return;
}

for (int i = depth; i < array.length; i++) {
swap(array, i, depth);
perm(array, depth + 1, length, operatorList, set);
swap(array, i, depth);
}
}

private void swap(char[] arrary, int i, int j) {
char temp = arrary[i];
arrary[i] = arrary[j];
arrary[j] = temp;
}

private Long getMax(List<Long> numberList, List<Character> operatorList, List<String> operatorSetList) {
long max = 0;

for (String operatorSet : operatorSetList) {
char[] operators = operatorSet.toCharArray();

LinkedList<Long> numberQueue = new LinkedList<>(numberList);
LinkedList<Character> operatorQueue = new LinkedList<>(operatorList);

for (char operatorToCalculate : operators) {
Stack<Long> numberStack = new Stack<>();
Stack<Character> operatorStack = new Stack<>();

long first = numberQueue.poll();
numberStack.push(first);
numberQueue.offer(first);

Stack[] stacks = new Stack[] {numberStack, operatorStack};
LinkedList[] queues = new LinkedList[] {numberQueue, operatorQueue};

calculatePriority(stacks, queues, operatorToCalculate);
}

max = (max > Math.abs(numberQueue.peek())) ? max : Math.abs(numberQueue.poll());
}

return max;
}

private void calculatePriority(Stack[] staks, LinkedList[] queues, char operatorToCalculate) {
Stack<Long> numberStack = staks[0];
Stack<Character> operatorStack = staks[1];

LinkedList<Long> numberQueue = queues[0];
LinkedList<Character> operatorQueue = queues[1];

int limit = operatorQueue.size();
for (int i = 0; i < limit; i++) {
long currentNumber = numberQueue.poll();
numberStack.push(currentNumber);

Character currentOperator = operatorQueue.poll();
operatorStack.push(currentOperator);

if (operatorStack.peek() == operatorToCalculate) {
long n1 = numberStack.pop();
long n2 = numberStack.pop();
char op = operatorStack.pop();

long sum = sum(n2, n1, op);
numberStack.push(sum);

numberQueue.pollLast();
numberQueue.offer(sum);
} else {
numberQueue.offer(currentNumber);
operatorQueue.offer(currentOperator);
}
}
}

private Long sum(long n2, long n1, char op) {
long sum = 0;

switch (op) {
case '*' :
sum = n2 * n1;
break;
case '+' :
sum = n2 + n1;
break;
case '-' :
sum = n2 - n1;
break;
}

return sum;
}

흐름

  1. 수식으로 넘어온 문자열을 숫자와 연산자로 나눈다.
  2. 연산자들을 중복되지 않게 저장한다.
  3. 문자열에 포함되어 있는 연산자들을 재귀로 반복하면서 모든 순열을 구한다.
    1. 0번째와 1번째를 교환하고 0번째와 2번째를 교환하고 하는 식으로 모든 순열을 구한다.
    2. 연산자의 개수만큼 순열로 만들어서 경우의 수를 구하기 위해 연산자가 2개인 경우엔 2! = 2개, 3개인 경우엔 3! = 6개가 된다.
  4. 모든 경우의 수를 구했으면 우선 순열의 수 만큼 반복해서 모든 경우의 수의 값을 구해야 하므로 순열의 수 만큼 반복한다.
  5. 돌면서 숫자를 담은 리스트와 연산자를 담은 리스트의 사이즈와 같은 큐를 만들고 각각 값들을 저장해서 초기화한다.
  6. 이번에 계산 할 순열(ex) * + -)을 char[]로 나눠서 그 갯수만큼 loop 돈다.
  7. 돌면서 숫자와 연산자를 저장 할 Stack를 각각 만든다.
  8. 숫자를 저장한 큐에서 하나를 꺼내서 stack에 저장하고 꺼낸 놈을 다시 큐의 맨 마지막에 저장한다.
  9. 그 후 큐의 개수만큼 loop 돌면서 큐들에서 하나씩 꺼내고 마찬가지로 스택에 저장한다.
  10. 그리고 꺼낸 연산자가 지금 계산 해야할 연산자라면 stack들에서 숫자 2개와 연산자를 pop하고 연산자에 맞게 계산해준다.
  11. 계산 한 값은 뒤에 또 그 값을 다른 값과 계산해야하므로 stack와 queue에 저장한다.
  12. 그리고 8번에서 큐에 초기값을 먼저 저장해서 큐의 맨 앞값과 큐의 맨 마지막 값이 계산된 것이므로 큐의 맨 마지막 값을 꺼낸다.
  13. 이번에 계산 할 연산자가 아니라면 지금 꺼낸 값과 연산자는 다시 큐에 저장한다.
  14. 4번부터 13번 까지를 모두 반복하면 끝

* + - 일 경우 Queue와 Stack의 변화

  1. 초기화
1
2
LinkedList<Long> numberQueue = new LinkedList<>(numberList);
LinkedList<Character> operatorQueue = new LinkedList<>(operatorList);
1 2 3 4 5
숫자 100 200 300 500 20
연산자 - * - +
  1. 숫자 초기값 저장
1
2
3
long first = numberQueue.poll();
numberStack.push(first);
numberQueue.offer(first);
1 2 3 4 5
숫자 200 300 500 20 100
연산자 - * - +

숫자 연산자
5
4
3
2
1 100
  1. 이후 반복
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for (int i = 0; i < limit; i++) {
long currentNumber = numberQueue.poll();
numberStack.push(currentNumber);

Character currentOperator = operatorQueue.poll();
operatorStack.push(currentOperator);

if (operatorStack.peek() == operatorToCalculate) {
long n1 = numberStack.pop();
long n2 = numberStack.pop();
char op = operatorStack.pop();

long sum = sum(n2, n1, op);
numberStack.push(sum);

numberQueue.pollLast();
numberQueue.offer(sum);
} else {
numberQueue.offer(currentNumber);
operatorQueue.offer(currentOperator);
}
}

1회 반복

1 2 3 4 5
숫자 300 500 20 100 200
연산자 * - + -
숫자 연산자
5
4
3
2 200
1 100 -

2회 반복

1 2 3 4 5
숫자 500 20 100 60000
연산자 - + -
숫자 연산자
5
4
3
2 60000
1 100

3회 반복

1 2 3 4 5
숫자 20 100 60000 500
연산자 + - -
숫자 연산자
5
4
3 500
2 60000
1 100 -

4회 반복

1 2 3 4 5
숫자 100 60000 500 20
연산자 - - +
숫자 연산자
5
4 20
3 500 -
2 60000 +
1 100 -
  • 이런 식으로 반복되고 queue 크기 만큼 돌았다는건 우선 계산해야 될 연산자를 다 계산 했다는 것이므로 다시 스택을 비우고 처음부터 위 계산을 반복한다.
  • 다시 계산해도 큐에 계산 된 값이 저장되어 있으므로 정상적으로 계산된다.

결과

번호 속도
테스트 1 통과 (1.22ms, 52.9MB)
테스트 2 통과 (1.25ms, 51.9MB)
테스트 3 통과 (1.54ms, 51.7MB)
테스트 4 통과 (1.62ms, 52.6MB)
테스트 5 통과 (1.70ms, 52.8MB)
테스트 6 통과 (1.73ms, 52.9MB)
테스트 7 통과 (1.69ms, 52.1MB)
테스트 8 통과 (1.76ms, 52.9MB)
테스트 9 통과 (1.81ms, 52.3MB)
테스트 10 통과 (1.86ms, 52.1MB)
테스트 11 통과 (1.70ms, 50.6MB)
테스트 12 통과 (1.90ms, 52.3MB)
테스트 13 통과 (2.62ms, 52.2MB)
테스트 14 통과 (2.17ms, 53.2MB)
테스트 15 통과 (2.15ms, 53.1MB)
테스트 16 통과 (1.36ms, 52.7MB)
테스트 17 통과 (1.57ms, 52.8MB)
테스트 18 통과 (1.28ms, 52.9MB)
테스트 19 통과 (1.30ms, 51.3MB)
테스트 20 통과 (1.33ms, 52.6MB)
테스트 21 통과 (1.53ms, 52.5MB)
테스트 22 통과 (1.47ms, 54.3MB)
테스트 23 통과 (1.21ms, 52.3MB)
테스트 24 통과 (2.11ms, 50.7MB)
테스트 25 통과 (2.17ms, 52.2MB)
테스트 26 통과 (1.39ms, 52.3MB)
테스트 27 통과 (2.70ms, 53MB)
테스트 28 통과 (1.74ms, 52.6MB)
테스트 29 통과 (1.59ms, 50.4MB)
테스트 30 통과 (1.58ms, 50.2MB)

테스트 케이스

1
2
assertEquals(60420, test.solution("100-200*300-500+20"));
assertEquals(300, test.solution("50*6-3*2"));

댓글 공유

상황

프로덕션 환경에서 Mariadb를 활용하고 있었는데, 프로덕션 환경의 DB로 Repository class를 테스트를 진행하니 테스트 데이터는 롤백되어 DB 남지 않았지만, Auto increment로 지정한 ID가 증가돼서 실제 서비스에서 데이터 저장 시 증가된 ID로 데이터가 저장되는 문제가 발생했다.

해서 Test할 때는 사용 할 데이터베이스 H2를 이용하기로 했다.
H2 데이터베이스는 인메모리 관계형 데이터베이스로 메모리 안에서 실행되기 때문에 어플리케이션을 시작할 때마다 초기화되어 테스트 용도로 많이 사용된다.
하지만 테스트 환경도 프로덕션 환경과 비슷하게 만들어서 테스트 하는 경우에는 테스트환경에도 프로덕션 DB를 생성해서 사용하는 경우도 있다고 한다.

필자가 okky에 올린 질문글
Repository Test시 ID 자동 증가


Test 환경에서 H2 적용

우선 H2 DB를 POM.xml에 추가하여 의존성을 등록한다.

1
2
3
4
5
6
<!-- https://mvnrepository.com/artifact/com.h2database/h2 -->
<dependency>
<groupId>com.h2database</groupId>
<artifactId>h2</artifactId>
<scope>test</scope>
</dependency>

그 후 Test 환경에서 사용하는 appication.properties에서 데이터베이스 설정을 H2로 설정해준다.

application-test.properties 위치

application-test.properties 내용

1
2
3
4
5
6
7
8
9
spring.datasource.url=jdbc:h2:mem:testdb;MODE=MySQL;DB_CLOSE_DELAY=-1
spring.datasource.driverClassName=org.h2.Driver
spring.datasource.username=sa
spring.datasource.password=
spring.h2.console.enabled=true

spring.jpa.hibernate.dialect=org.hibernate.dialect.MariaDBDialect
spring.jpa.database-platform=org.hibernate.dialect.H2Dialect
spring.jpa.hibernate.ddl-auto=create-drop
  • 프로덕션 환경에서 Mariadb를 사용하기 때문에 dialect를 Mariadb로 설정하고 MODE=Mysql로 설정했다.
  • spring.jpa.hibernate.ddl-auto=none으로 설정하면 시작 시 마다 초기화되지 않기 떄문에 테스트 환경에선 꼭 create-drop으로 설정해준다.

Repository Test class

1
2
3
4
5
6
@ExtendWith(SpringExtension.class)
@DataJpaTest
@TestPropertySource("classpath:application-test.properties")
class WordRepositoryTest {
...
}
  • JPA Test를 위해 JPA 관련된 설정을 불러오는 @DataJpaTest
  • Test환경에선 프로덕션 환경과 다르게 H2 DB를 사용하므로 H2 DB설정을 지정한 application-test.properties를 호출하기 위한 @TestPropertySource

이 정도로 설정하고 Test하면 정상적으로 H2를 이용한 테스트가 성공할 것이다.


여담

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@BeforeEach
void setUp() {
user = new User();
user.setUsername("jgji");
user.setPassword("qwe123");

userRepository.save(this.user);

user1 = new User();
user.setUsername("haha");
user.setPassword("qwe123");

userRepository.save(this.user1);

List<Word> givenWordList = getWordGiven();
this.word = givenWordList.get(0);
this.word1 = givenWordList.get(1);
}

위 처럼 @Before 메서드를 지정해놓았는데, 각각 Test 메서드를 실행하였을 땐 Auto increment로 지정한 user의 id가 정상적으로 1, 2 이런식으로 생성되었지만 test class 전체로 test를 실행하니 DB가 메서드 마다 각각 실행하고 초기화 되는 것이 아닌지 User Id가 계속 증가해서 테스트가 실패하는 문제가 있었다.

테스트 시 꼭 메서드 각각으로하고 성공한다고 넘어가는게 아니라 클래스 전체로 테스트를 해봐야 할 것 같다.


프로젝트 전체 코드


참고 사이트

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/64065


코드

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
public int[] solution(String s) {
String[] strArray = getStringArray(s);
List<Integer[]> list = convertStringArrayToIntegerArrayList(strArray);
sortByArraylength(list);

List<Integer> tuple = getTuple(list);
int[] answer = convertIntegerArrayToIntArray(tuple);

return answer;
}

private String[] getStringArray(String s) {
String[] array = s.substring(2, s.length()-2).replace("},{", "@").split("@");

return array;
}

private List<Integer[]> convertStringArrayToIntegerArrayList(String[] strArray) {
List<Integer[]> list = new ArrayList<>();
for (String str : strArray) {
String[] stringNumbers = str.split(",");
Integer[] array = convertStringArrayToIntegerArray(stringNumbers);

list.add(array);
}

return list;
}

private Integer[] convertStringArrayToIntegerArray(String[] stringNumbers) {
Integer[] array = new Integer[stringNumbers.length];
int i = 0;
for (String str2 : stringNumbers) {
array[i++] = Integer.parseInt(str2);
}

return array;
}

private void sortByArraylength(List<Integer[]> list) {
Collections.sort(list, new Comparator<Integer[]>() {
@Override
public int compare(Integer[] o1, Integer[] o2) {
return o1.length - o2.length;
}
});
}

private List<Integer> getTuple(List<Integer[]> list) {
List<Integer> tuple = new ArrayList<>();

for (int i = 0; i < list.size(); i++) {
Integer[] elements = list.get(i);

for (Integer element : elements) {
if (!tuple.contains(element)) {
tuple.add(element);
}
}
}

return tuple;
}

private int[] convertIntegerArrayToIntArray(List<Integer> list) {
int[] answer = new int[list.size()];
int j = 0;
for (int i : list) {
answer[j++] = i;
}

return answer;
}

흐름

  1. 문자열을 각각 숫자를 저장한 문자열 배열로 만든다. (getStringArray)
  2. 만든 문자열 배열에 저장된 문자열을 “,”로 나눠서 각각 Integer 배열에 저장하고 그 Integer 배열을 담는 List에 저장한다. (convertStringArrayToIntegerArrayList)
  3. List에 저장된 Integer 배열을 배열의 길이가 짧은 순으로 sorting 한다. (sortByArraylength)
  4. 정렬한 list를 돌면서 Integer 배열을 꺼내고 다시 배열을 돌면서 튜플을 저장할 List에 담는데, 이 때 저장하기 전에 이미 List에 저장된 숫자인 경우엔 담을 필요가 없으므로 contain() 를 사용해서 List에 저장되지 않은 숫자만 add 한다.
  5. List형 이었으므로 문제에 맞게 int 배열 형으로 변환해서 return한다.

최다 좋아요 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] solution(String s) {
Set<String> set = new HashSet<>();
String[] arr = s.replaceAll("[{]", " ").replaceAll("[}]", " ").trim().split(" , ");
Arrays.sort(arr, (a, b)->{return a.length() - b.length();});
int[] answer = new int[arr.length];
int idx = 0;
for(String s1 : arr) {
for(String s2 : s1.split(",")) {
if(set.add(s2)) answer[idx++] = Integer.parseInt(s2);
}
}
return answer;
}
  1. 마찬가지로 우선 String을 String[]로 만들고
  2. 배열 길이 순으로 정렬한 다음에
  3. 2중 for문을 돌면서 숫자를 배열에 저장하는데,
  4. Set을 통해 이미 저장된 숫자는 저장하지 않는다.

결과

번호 속도
테스트 1 통과 (2.12ms, 52.3MB)
테스트 2 통과 (2.16ms, 52.2MB)
테스트 3 통과 (2.03ms, 50.3MB)
테스트 4 통과 (2.58ms, 52.4MB)
테스트 5 통과 (6.02ms, 52.4MB)
테스트 6 통과 (7.96ms, 50.9MB)
테스트 7 통과 (38.39ms, 53.8MB)
테스트 8 통과 (68.47ms, 61.7MB)
테스트 9 통과 (51.85ms, 57.6MB)
테스트 10 통과 (142.71ms, 62.2MB)
테스트 11 통과 (91.56ms, 65.7MB)
테스트 12 통과 (111.69ms, 74.1MB)
테스트 13 통과 (104.26ms, 72.1MB)
테스트 14 통과 (113.99ms, 74.5MB)
테스트 15 통과 (1.84ms, 50MB)

테스트 케이스

1
2
3
4
5
6
7
assertArrayEquals(new int[]{2,1,3,4}, test.solution("{{2},{2,1},{2,1,3},{2,1,3,4}}"));
assertArrayEquals(new int[]{2,1,3,4}, test.solution("{{1,2,3},{2,1},{1,2,4,3},{2}}"));
assertArrayEquals(new int[]{111,20}, test.solution("{{20,111},{111}}"));
assertArrayEquals(new int[]{123}, test.solution("{{123}}"));
assertArrayEquals(new int[]{3,2,4,1}, test.solution("{{4,2,3},{3},{2,3,4,1},{2,3}}"));
assertArrayEquals(new int[]{3,2,4,1,100}, test.solution("{{4,2,3},{3},{2,3,4,1},{2,3},{2,3,4,1,100}}"));
assertArrayEquals(new int[]{3,2,4,1,100}, test.solution("{{4,2,3},{3},{2,3,4,1},{2,3},{2,3,4,1,100}}"));

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/12924


코드

삽질 코드

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
public int solution(int n) {
int answer = 0;
int[] sumArray = new int[n + 1];

Queue<Integer> queue = initQueue(n);

int sum = 0;
for (int i = 1; i < n + 1; i++) {
sum += i;
sumArray[i] = sum;

if (sum == n) {
++answer;

int nextValue = i+1;

while (!queue.isEmpty()) {
int sumValue = sumArray[queue.peek()];

if (nextValue <= sumValue) {
i = queue.peek();
sum = 0;
break;
}

queue.poll();
}
} else if (sum > n) {
int value = sum - n;

while (!queue.isEmpty()) {
int sumValue = sumArray[queue.peek()];

if (value <= sumValue) {
i = queue.poll();
sum = 0;
break;
}

queue.poll();
}
}
}

return answer;
}
  1. 합계를 저장 할 array와 배열의 index를 저장 할 queue를 생성하고 queue에 index를 순서대로 할당해놓는다.
  2. i를 증가 시키면서 sum을 저장하고 sum == n 이 되면 answer을 증가시키고, 그 다음 index의 값을 구해서 그 다음 값 만큼 이전에 더한 값들을 빼고 뺀 값 다음 index부터 실행하기 위해 index를 queue에서 가져온다.
    • 1 + 2 + 3 + 4 + 5 = 15 였으면 다음 값은 6 이므로 6을 만큼을 빼기 위해 1, 2 3을 뺀다.
  3. sum이 n보다 크다면 sum에서 n을 뺀 값 만큼 더했던 값에서 빼고 뺀 값 다음 index부터 실행하기 위해 index를 queue에서 가져온다.
    • 5 + 6 + 7 = 18 이므로 15를 뺀 3보다 크거나 같은 값을 앞에서부터 빼야되는데 5는 이미 3보다 크므로 5를 queue에서 poll해서 뺀다.
  4. 위를 반복해서 연속된 자연수의 개수를 구한다.

숫자가 커지면 반복 할 때 효율성에서 걸릴까 싶어서 큐도쓰고 해봤는데 보기도 안좋고 속도도 안좋고 모든 면에서 안좋았다

정석 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int solution(int n) {
int answer = 0;

for(int i = 1; i <= (n / 2) ; i++) {
int sum = 0;
int index = i;

while (sum < n) {
sum += index;
++index;
}

if (sum == n) {
++answer;
}
}

return answer + 1;
}
  1. n의 절반을 넘어가면 그 이상 더 해봤자 n을 넘어가므로 n / 2까지만 반복한다.
  2. sum이 n 보다 작으면 반복해서 sum에 index를 증가시켜 가며 더한다.
  3. sum이 n보다 작지 않아지면 빠져나와서 sum == n이 판단하고 같으면 answer을 증가시킨다.
  4. 마지막에 자기자신이 들어가므로 + 1을 하고 return한다.

결과

뻘짓 코드

정확성

번호 속도
테스트 1 통과 (1.02ms, 52.4MB)
테스트 2 통과 (2.01ms, 50.3MB)
테스트 3 통과 (1.64ms, 52.5MB)
테스트 4 통과 (1.83ms, 50.7MB)
테스트 5 통과 (1.13ms, 52.5MB)
테스트 6 통과 (0.95ms, 52.5MB)
테스트 7 통과 (1.68ms, 52.3MB)
테스트 8 통과 (1.41ms, 50.1MB)
테스트 9 통과 (0.93ms, 50MB)
테스트 10 통과 (2.25ms, 52.8MB)
테스트 11 통과 (2.15ms, 50.5MB)
테스트 12 통과 (1.78ms, 52.6MB)
테스트 13 통과 (1.86ms, 52MB)
테스트 14 통과 (1.68ms, 52.7MB)

효율성

번호 속도
테스트 1 통과 (9.68ms, 52.5MB)
테스트 2 통과 (6.16ms, 52.2MB)
테스트 3 통과 (7.96ms, 52MB)
테스트 4 통과 (7.72ms, 51MB)
테스트 5 통과 (8.29ms, 50.6MB)
테스트 6 통과 (10.67ms, 52.4MB)

정석 코드

정확성

번호 속도
테스트 1 통과 (0.77ms, 50.2MB)
테스트 2 통과 (0.94ms, 50.6MB)
테스트 3 통과 (0.81ms, 50.4MB)
테스트 4 통과 (0.86ms, 51MB)
테스트 5 통과 (0.80ms, 52.1MB)
테스트 6 통과 (0.77ms, 52.2MB)
테스트 7 통과 (0.90ms, 52.5MB)
테스트 8 통과 (0.84ms, 52.4MB)
테스트 9 통과 (0.69ms, 50.2MB)
테스트 10 통과 (0.87ms, 52.2MB)
테스트 11 통과 (0.91ms, 52.1MB)
테스트 12 통과 (0.89ms, 52.3MB)
테스트 13 통과 (0.79ms, 50.4MB)
테스트 14 통과 (0.84ms, 50.2MB)

효율성

번호 속도
테스트 1 통과 (1.48ms, 52.9MB)
테스트 2 통과 (1.12ms, 52.2MB)
테스트 3 통과 (1.21ms, 50.8MB)
테스트 4 통과 (1.28ms, 50MB)
테스트 5 통과 (1.52ms, 50.1MB)
테스트 6 통과 (1.50ms, 52.3MB)

테스트 케이스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
assertEquals(4, test.solution(15));
assertEquals(2, test.solution(20));
assertEquals(4, test.solution(30));
assertEquals(2, test.solution(106));
assertEquals(2, test.solution(1567));
assertEquals(1, test.solution(16));
assertEquals(4, test.solution(782));
assertEquals(5, test.solution(10000));
assertEquals(12, test.solution(9999));
assertEquals(4, test.solution(7787));
assertEquals(8, test.solution(4578));
assertEquals(2, test.solution(1234));
assertEquals(1, test.solution(1));
assertEquals(2, test.solution(5));
assertEquals(3, test.solution(49));

P.S

주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다.


  • 이 문제의 최다 좋아요를 받은 코드는 위의 정수론 정리를 이용한 풀이가 있는데 정의의 출처를 찾지 못했다.
  • 해당 정의를 가지고 푼 코드가 가장 짧고 가장 빠르게 실행된다.
  • 한참 멀었구나 싶다.

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/12945


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static final int DIVIDE_NUMBER = 1234567;

public int solution(int n) {
int[] cache = new int[n+1];

cache[1] = 1;

for (int i = 2; i < n+1; i++) {
cache[i] = ((cache[i-1]) % DIVIDE_NUMBER + (cache[i-2]) % DIVIDE_NUMBER) % DIVIDE_NUMBER;
}

int answer = cache[n];
return answer;
}

흐름

  1. n+1 크기 배열을 생성하는데 이 때 이번 문제에서 n은 1 <= n <= 100,000 이하이다.
  2. n이 1 일땐 1을 return 해야하므로 배열 1 번째엔 1을 할당 해놓아야 한다.
  3. 2부터 n + 1 까지 반복하면서 피보나치 수열 계산하는 것 처럼 i - 1, i - 2 배열에 저장된 값을 더하는데
  4. 문제에서 1234567을 나눈 나머지 값을 return 하라고 하였으므로 % 1234567을 해준다.
  5. cache 배열에서 n 번째에 있는 값을 return하면 끝

결과

번호 속도
테스트 1 통과 (0.85ms, 52.8MB)
테스트 2 통과 (0.80ms, 52.2MB)
테스트 3 통과 (0.78ms, 51.3MB)
테스트 4 통과 (0.81ms, 53.1MB)
테스트 5 통과 (0.84ms, 52.6MB)
테스트 6 통과 (0.85ms, 50.3MB)
테스트 7 통과 (0.95ms, 52.4MB)
테스트 8 통과 (0.86ms, 50.5MB)
테스트 9 통과 (0.86ms, 52MB)
테스트 10 통과 (0.89ms, 51.4MB)
테스트 11 통과 (0.84ms, 51MB)
테스트 12 통과 (0.86ms, 52.4MB)
테스트 13 통과 (3.99ms, 52.7MB)
테스트 14 통과 (3.98ms, 50.4MB)

테스트 케이스

1
2
3
4
5
6
7
assertEquals(2, test.solution(3));
assertEquals(5, test.solution(5));
assertEquals(987, test.solution(16));
assertEquals(256379, test.solution(1234156));
assertEquals(473509, test.solution(100001));
assertEquals(1168141, test.solution(100000));
assertEquals(547662, test.solution(124126347));

참고 사이트

댓글 공유

Junggu Ji

author.bio


author.job