선형 자료구조 연습문제
문제 설명
프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’,
즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다.
하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
- 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
- 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다.
- 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 코드를 작성하세요.
예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.
입출력 예시
| 문서 개수 | 출력 대상 번호 | 우선순위 | 출력 |
|---|---|---|---|
| 1 | 0 | 5 | 1 |
| 4 | 2 | 1 2 3 4 | 2 |
| 6 | 0 | 1 1 9 1 1 1 | 5 |
import java.util.LinkedList;
import java.util.Queue;
class Doc {
int no;
int priority;
public Doc(int no, int priority) {
this.no = no;
this.priority = priority;
}
}
public class Practice1 {
public static void solution(int docs, int target, int[] priority) {
Queue<Doc> queue = new LinkedList();
for (int i = 0; i < docs; i++) {
queue.add(new Doc(i, priority[i]));
}
int cnt = 1;
while (true) {
Doc cur = queue.poll();
Doc[] highP = queue.stream().filter(x -> x.priority > cur.priority).toArray(Doc[]::new);
if (highP.length > 0) {
queue.add(cur);
} else {
if (cur.no == target) {
System.out.println(cnt);
break;
}
cnt++;
}
}
}
public static void main(String[] args) {
// Test code
int docs = 1;
int target = 0;
int[] priority = {5};
solution(docs, target, priority);
docs = 4;
target = 2;
priority = new int[]{1, 2, 3, 4};
solution(docs, target, priority);
docs = 6;
target = 0;
priority = new int[]{1, 1, 9, 1, 1, 1};
solution(docs, target, priority);
}
}
1
2
5
문제 설명
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다.
스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같다.
제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
- 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다.
- 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자.
임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지,
있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 계산하는 프로그램을 작성하시오.
같은 정수가 두 번 나오는 경우는 없다.
입출력 예시
| 입력 | 결과 |
|---|---|
| 4 3 6 8 7 5 2 1 | + + + + - - + + - + + - - - - - |
| 1 2 5 3 4 | NO |
import java.util.ArrayList;
import java.util.Stack;
public class Practice2 {
public static void solution(int[] nums) {
Stack<Integer> stack = new Stack<>();
ArrayList<String> result = new ArrayList<>();
int idx = 0;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (num > idx) {
for (int j = idx + 1; j < num + 1; j++) {
stack.push(j);
result.add("+");
}
idx = num;
} else if (stack.peek() != num) {
System.out.println("NO");
return;
}
stack.pop();
result.add("-");
}
for (String item: result) {
System.out.println(item);
}
}
public static void main(String[] args) {
int[] nums = {4, 3, 6, 8, 7, 5, 2, 1};
solution(nums);
System.out.println("=====");
nums = new int[]{1, 2, 5, 3, 4};
solution(nums);
}
}
+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-
=====
NO
문제 설명
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다.
노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
- 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
- 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
- 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.
제한사항
genres[i]는 고유번호가i인 노래의 장르입니다.plays[i]는 고유번호가i인 노래가 재생된 횟수입니다.genres와plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.
입출력 예시
| genres | plays | return |
|---|---|---|
| [“classic”, “pop”, “classic”, “classic”, “pop”] | [500, 600, 150, 800, 2500] | [4, 1, 3, 0] |
- 입출력 예 설명:
classic장르는 1,450회 재생되었으며,classic노래는 다음과 같습니다.- 고유 번호 3: 800회 재생
- 고유 번호 0: 500회 재생
- 고유 번호 2: 150회 재생
pop장르는 3,100회 재생되었으며,pop노래는 다음과 같습니다.- 고유 번호 4: 2,500회 재생
- 고유 번호 1: 600회 재생
- 따라서
pop장르의 [4, 1]번 노래를 먼저,classic장르의 [3, 0]번 노래를 그다음에 수록합니다.
import java.util.*;
class Song {
int no;
int play;
public Song(int no, int play) {
this.no = no;
this.play = play;
}
}
public class Practice3 {
public static void solution(String[] genres, int[] plays) {
Hashtable<String, ArrayList<Song>> ht = new Hashtable();
for (int i = 0; i < genres.length; i++) {
if (ht.containsKey(genres[i])) {
ArrayList<Song> cur = ht.get(genres[i]);
int idx = -1;
for (int j = 0; j < cur.size(); j++) {
if (plays[i] > cur.get(j).play ||
(plays[i] == cur.get(j).play && i < cur.get(j).no)) {
idx = j;
break;
}
}
if (idx == -1) {
cur.add(new Song(i, plays[i]));
} else {
cur.add(idx, new Song(i, plays[i]));
}
ht.put(genres[i], cur);
} else {
Song s = new Song(i, plays[i]);
ht.put(genres[i], new ArrayList<>(Arrays.asList(s)));
}
}
Hashtable<String, Integer> htPlay = new Hashtable<>();
for (String item: ht.keySet()) {
int sum = 0;
ArrayList<Song> cur = ht.get(item);
for (int i = 0; i < cur.size(); i++) {
sum += cur.get(i).play;
}
htPlay.put(item, sum);
}
ArrayList<Map.Entry<String, Integer>> htPlaySort = new ArrayList<>(htPlay.entrySet());
htPlaySort.sort((x1, x2) -> x2.getValue() - x1.getValue());
// 출력
for (Map.Entry<String, Integer> item: htPlaySort) {
ArrayList<Song> songs = ht.get(item.getKey());
for (int i = 0; i < songs.size(); i++) {
System.out.print(songs.get(i).no + " ");
if (i == 1) {
break;
}
}
}
System.out.println();
}
public static void main(String[] args) {
// Test code
String[] genres = {"classic", "pop", "classic", "classic", "pop"};
int[] plays = {500, 600, 150, 800, 2500};
solution(genres, plays);
}
}
4 1 3 0
문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는participant의 길이보다 1 작습니다.- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예시
| participant | completion | return |
|---|---|---|
| [“leo”, “kiki”, “eden”] | [“eden”, “kiki”] | “leo” |
| [“marina”, “josipa”, “nikola”, “vinko”, “filipa”] | [“josipa”, “filipa”, “marina”, “nikola”] | “vinko” |
| [“mislav”, “stanko”, “mislav”, “ana”] | [“stanko”, “ana”, “mislav”] | “mislav” |
- 입출력 예에 대한 설명:
- 예제 1: “leo”는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
- 예제 2: “vinko”는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
- 예제 3: “mislav”는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
import java.util.Hashtable;
public class Practice4 {
public static String solution(String[] participant, String[] completion) {
String result = "";
Hashtable<String, Integer> ht = new Hashtable();
for (String item: participant) {
if (ht.containsKey(item)) {
ht.put(item, ht.get(item) + 1);
} else {
ht.put(item, 1);
}
}
for (String item: completion) {
ht.put(item, ht.get(item) - 1);
}
for (String item: participant) {
if (ht.get(item) > 0) {
result = item;
break;
}
}
return result;
}
public static void main(String[] args) {
// Test code
String[] participant = {"leo", "kiki", "eden"};
String[] completion = {"eden", "kiki"};
System.out.println(solution(participant, completion));
participant = new String[]{"marina", "josipa", "nikola", "vinko", "filipa"};
completion = new String[]{"josipa", "filipa", "marina", "nikola"};
System.out.println(solution(participant, completion));
participant = new String[]{"mislav", "stanko", "mislav", "ana"};
completion = new String[]{"stanko", "ana", "mislav"};
System.out.println(solution(participant, completion));
}
}
leo
vinko
mislav
문제 설명
개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.
| 진열대 번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 보석 이름 | DIA | RUBY | RUBY | DIA | DIA | EMERALD | SAPPHIRE | DIA |
진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.
진열대의 3, 4, 6, 7번의 보석만 구매하는 것은 중간에 특정 구간(5번)이 빠지게 되므로 어피치의 쇼핑 습관에 맞지 않습니다.
진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.
제한사항
gems배열의 크기는 1 이상 100,000 이하입니다.gems배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.gems배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.gems배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.
입출력 예시
| gems | result |
|---|---|
| [“DIA”, “RUBY”, “RUBY”, “DIA”, “DIA”, “EMERALD”, “SAPPHIRE”, “DIA”] | [3, 7] |
| [“AA”, “AB”, “AC”, “AA”, “AC”] | [1, 3] |
| [“XYZ”, “XYZ”, “XYZ”] | [1, 1] |
| [“ZZZ”, “YYY”, “NNNN”, “YYY”, “BBB”] | [1, 5] |
- 입출력 예에 대한 설명:
- 입출력 예 #1
- 문제 예시와 같습니다.
- 입출력 예 #2
- 3종류의 보석(AA, AB, AC)을 모두 포함하는 가장 짧은 구간은 [1, 3], [2, 4]가 있습니다.
- 시작 진열대 번호가 더 작은 [1, 3]을 return 해주어야 합니다.
- 입출력 예 #3
- 1종류의 보석(XYZ)을 포함하는 가장 짧은 구간은 [1, 1], [2, 2], [3, 3]이 있습니다.
- 시작 진열대 번호가 가장 작은 [1, 1]을 return 해주어야 합니다.
- 입출력 예 #4
- 4종류의 보석(ZZZ, YYY, NNNN, BBB)을 모두 포함하는 구간은 [1, 5]가 유일합니다.
- 그러므로 [1, 5]를 return 해주어야 합니다.
- 입출력 예 #1
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.stream.Stream;
public class Practice5 {
public static ArrayList<Integer> solution(String[] gems) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
HashSet<String> set = new HashSet<>();
Stream.of(gems).forEach(x -> set.add(x));
int n = set.size();
if (n == 1) {
result.add(new ArrayList(Arrays.asList(1, 1)));
return result.get(0);
}
Hashtable<String, Integer> ht = new Hashtable();
boolean isCandidate = false;
int left = 0;
int right = 0;
ht.put(gems[0], 1);
while (true) {
if (isCandidate == false) {
right += 1;
if (right >= gems.length) {
break;
}
if (ht.containsKey(gems[right]) == false) {
ht.put(gems[right], 1);
} else {
ht.put(gems[right], ht.get(gems[right]) + 1);
}
if (ht.size() == n) {
isCandidate = true;
result.add(new ArrayList(Arrays.asList(left + 1, right + 1)));
}
} else {
left += 1;
int cnt = ht.get(gems[left - 1]) - 1;
if (cnt == 0) {
ht.remove(gems[left - 1]);
isCandidate = false;
} else {
ht.put(gems[left - 1], cnt);
result.add(new ArrayList(Arrays.asList(left + 1, right + 1)));
}
}
}
int minIdx = 0;
int minNum = Integer.MAX_VALUE;
for (int i = 0; i < result.size(); i++) {
ArrayList<Integer> cur = result.get(i);
left = cur.get(0);
right = cur.get(1);
if (right - left < minNum) {
minNum = right - left;
minIdx = i;
}
}
return result.get(minIdx);
}
public static void main(String[] args) {
// Test code
String[] gems = {"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"};
System.out.println(solution(gems));
gems = new String[]{"AA", "AB", "AC", "AA", "AC"};
System.out.println(solution(gems));
gems = new String[]{"XYZ", "XYZ", "XYZ"};
System.out.println(solution(gems));
gems = new String[]{"ZZZ", "YYY", "NNNN", "YYY", "BBB"};
System.out.println(solution(gems));
}
}
[3, 7]
[1, 3]
[1, 1]
[1, 5]
Leave a comment