99클럽 코테 스터디 15일차 TIL : 그리디 알고리즘(백준 13417번)

 

 

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를 사용했는데, 효율성 측면에서 더 좋은 자료구조가 있는지 다른 사람들의 풀이도 도 확인해봐야지