99클럽 코테 스터디 15일차 TIL : 그리디 알고리즘(백준 13417번)
2024. 11. 11. 14:00ㆍAlgorithm/항해99(4기)
https://www.acmicpc.net/problem/13417
🔎 문제
N장의 카드 (알파벳)
태욱: 가장 왼쪽 카드부터 한장씩 가져올 수 있다.
첫번째 들고온 카드는 자신앞에 놓는다. 그다음 가져온 것들은 가장왼쪽 또는 가장 오른쪽에 놓는다.
태욱이가 만들 수 있는 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하세요.
카드갯수 1<=N<=1000
💡 풀이
- 문자를 받아왔을 때 이전에 있던 카드 왼쪽, 오른쪽을 확인 한 후 왼쪽 문자열보다 빠르면 왼쪽, 느리면 오른쪽에 삽입.
- 양쪽으로 넣기 위해 deque 자료구조를 사용
package greedy;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Ex13417 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int caseSu = Integer.parseInt(br.readLine()); //case
for(int i=0;i<caseSu;i++) {
int n = Integer.parseInt(br.readLine());
String s = br.readLine();
StringTokenizer st= new StringTokenizer(s);
Deque<Character> queue = new ArrayDeque<Character>();
for(int j=0;j<n;j++) {
char c = st.nextToken().charAt(0);
if(queue.isEmpty()) {
queue.add(c);
} else {
int first = queue.getFirst();
if(first<c)
queue.addLast(c);
else
queue.addFirst(c);
}
}
queue.forEach(t -> sb.append(t));
sb.append("\n");
queue = new ArrayDeque<Character>();
}
System.out.println(sb);
}
}
📌 오늘의 회고
사전 가장앞에 위치할 문자열을 찾아야 하기 때문에, 사전순서로 앞에있는 알파벳이 나오면 바로 앞으로 위치시키는 방식으로 해결했다.
자료구조는 양방향으로 넣기위해 deque를 사용했는데, 효율성 측면에서 더 좋은 자료구조가 있는지 다른 사람들의 풀이도 도 확인해봐야지
'Algorithm > 항해99(4기)' 카테고리의 다른 글
99클럽 코테 스터디 17일차 TIL : 그리디 알고리즘(백준 31926번 밤양갱) (0) | 2024.11.13 |
---|---|
99클럽 코테 스터디 16일차 TIL : 그리디 알고리즘(백준 2847번) (0) | 2024.11.12 |
99클럽 코테 스터디 14일차 TIL : 그리디 알고리즘(백준 14916번) (0) | 2024.11.11 |
99클럽 코테 스터디 11일차 TIL : BFS/DFS(백준 25195번) (1) | 2024.11.07 |
99클럽 코테 스터디 8일차 TIL : DFS(백준 2644번) (1) | 2024.11.04 |