오늘은 백준 3052번 문제를 풀자! 해당 문제를 봤을 때, 바로 떠오른 방법이 두 가지가 있다.
MkWeb을 개발하면서 HashMap을 엄청나게 썼기 때문에, 첫 번째로 HashMap이 떠올랐고, 그 다음으로 Queue를 이용한 풀이가 떠올랐다.
해시맵의 경우, 중복되는 키를 허용하지 않기 때문에 나머지를 구한 다음에 HashMap에 각각 넣어준 뒤, HashMap의 사이즈를 반환하면 끝이다. 너무 쉽기 때문에, Queue를 이용하여 문제를 풀이하려 한다.
사실 큐를 이용하나 ArrayList, Stack 등 다른 자료구조를 이용하나 풀이는 비슷하지만, 큐의 풀이가 더 직관적이기 때문에 큐를 선택했다.
이쯤 되면 나머지 수를 구하는 것은 쉬우니, 설명은 넘어가도록 하겠다.
val = 입력값 % 42
우리는 큐에 값을 하나 씩 넣어줄 예정인데, 이전에 큐에 이미 값이 존재하는지 확인해야 한다. 이 때, 값이 존재하지 않는다면 값을 추가하고, 존재한다면 해당 값은 따로 추가하지 않을 것이다.
이때 '하나의 큐로 어떻게 가능하지?'라는 의문이 들텐데, 당연히 두 개의 큐를 사용할 것이다. (물론, 하나는 배열, 하나는 큐 등 어떤 형태를 취하든 상관 없으나, 위에서 말한대로 큐가 직관적이기 때문에 큐를 사용할 것이다.)
mainQueue: 나머지가 저장될 큐
tempQueue: mainQueue에 존재하지 않는 val들을 임시적으로 저장할 큐
매 회차마다 mainQueue로부터 tempQueue로 하나씩 옮겨담을 것이다. 이 때, val이 mainQueue에 존재하는지 확인하고, 존재하지 않는다면 값을 추가할 것이다.
따라서 mainQueue에서는 dequeue가 주로 사용될 것이며, tempQueue에는 enqueue가 주로 사용될 것이다.
While size of mainQueue > 0 Then
peek is mainQueue.dequeue();
If peek is not val Then
tempQueue.enqueue(peek);
End If
End While
수도 코드를 표현하려 했는데.. VB의 아련한 기억이...
while 반복문이 끝나면, queue를 tempQueue로 바꿔주고, queue에 val을 추가해주면 된다. val을 추가하는 이유는 while문 내에서 val을 제외한 값들만 옮겨 넣었기 때문에, mainQueue에는 val이 없다.
최종적으로 mainQueue의 size를 출력해주면 해당 문제는 끝!
전체 코드
import java.io.*;
import java.util.*;
public class Number3052 {
public static void main(String args[]) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < 10; i++) {
int val = (Integer.parseInt(bufferedReader.readLine())) % 42;
Queue<Integer> tempQueue = new LinkedList<>();
while(queue.size() > 0) {
int peek = queue.poll();
if(peek != val){
tempQueue.add(peek);
}
}
queue = tempQueue;
queue.add(val);
}
System.out.println(queue.size());
}
}결과는 정답!
'공부 > 알고리즘' 카테고리의 다른 글
| [Java 코딩테스트] 백준 2775 부녀회장이 될테야 / Dynamic Programming (0) | 2021.08.18 |
|---|---|
| [Java 코딩테스트] 백준 2292번 문제 풀이 / 백준 벌집 문제 (0) | 2021.08.10 |
| [Java 코딩테스트] 백준 10818 문제풀이 / 배열 없이 최소 최대 구하기 (0) | 2021.07.22 |
| [Java 코딩테스트] 백준 1110 문제풀이 / 더하기 사이클 (0) | 2021.07.22 |
| [Java 코딩테스트] 백준 2438 문제풀이 Dynamic Programming (0) | 2021.07.19 |
