Category: 자료구조

0

백준 1158 - 요세푸스 문제

백준 1158 - 요세푸스 문제https://www.acmicpc.net/problem/1158 문제 풀이해당 문제에서는 두가지 입력 N, K가 주어진다. N : 사람 수 K : 원에서 사람이 제거되는 간격 N, K의 최대 5000 이므로, 최대 O(N^2)의 시간복잡도내에서 문제를 해결해야 한다. 전체 소스 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arguments = br.readLine().split(" "); int N, K; N = Integer.parseInt(arguments[0]); K = Integer.parseInt(arguments[1]); List<Integer> list = new ArrayList<>(); for (int i = 0; i < N; i++) { list.add(i + 1); } int index = 0; StringBuilder sb = new StringBuilder(); sb.append("<"); // 사람을 간격에 맞게 하나씩 제거해준다. while (list.size() > 1) { index += K - 1; index %= list.size(); int removedValue = list.remove(index); sb.append(Integer.toString(removedValue)); sb.append(", "); } // 마지막 숫자를 제거한다. index += K - 1; index %= list.size(); int removedValue = list.remove(index); sb.append(Integer.toString(removedValue)); sb.append(">"); System.out.println(sb.toString()); br.close(); }}

0

백준 3015 - 단어 정렬

https://www.acmicpc.net/problem/1181 백준 3015 단어 정렬문제 풀이자료구조 Set을 사용하기 좋은 문제이다. 다만 Set에서 사용하는 정렬방식을 조건에 맞게 변형해줄 필요가 있다. 소스코드#include <bits/stdc++.h>using namespace std;set<pair<int, string>> s;int n;int main(void) { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); cin >> n; while (n--) { string word; cin >> word; s.insert({word.length(), word}); } for (auto iter = s.begin(); iter != s.end(); iter++) { cout << iter->second << '\n'; } return 0;} 자바 소스 코드Comparator 인터페이스를 이용해 set의 정렬기준을 사용자가 정의한 정렬기준으로 변경할 수 있다. Comparator 인터페이스를 사용하게 되면 compare 메소드를 오버라이딩해 원하는 정렬 기준을 적용할 수 있다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Comparator;import java.util.Set;import java.util.TreeSet;public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int count = Integer.parseInt(br.readLine()); Set<String> words = new TreeSet<String>(new Comparator<String>() { @Override public int compare(String o1, String o2) { if (o1.length() < o2.length()) { return -1; } else if (o1.length() > o2.length()) { return 1; } else { return o1.compareTo(o2); } } }); for (int countIdx = 0; countIdx < count; countIdx++) { String word = br.readLine(); words.add(word); } words.stream().forEach(x -> System.out.println(x)); }}

0

백준 3015 - 오아시스 재결합

백준 3015 - 오아시스 재결합https://www.acmicpc.net/problem/1920 문제 해설입력되는 값이 총 50만개이다. 이 문제는 O(N) or O(NlogN)의 시간복잡도를 갖고 해결을 해야하는 문제이다. 현재 값을 이전 값과 비교해가면서 문제를 해결 하는 방식이다. 스택의 역할은 서로불 수 있는 값의 쌍을 저장하기 위한 역할을 한다. 스택내의 값은 점점 작은 값이 추가 되야 한다. 들어오는 값이 top보다 클 경우 들어오는 값보다 큰 값이 나타날 때까지 pop을 진행하면서 pop을 진행할 때 해당 인원수 만큼 값을 더해준다. 같은 값이 들어올 경우을 어떻게 해결하는 것이 이 문제의 어려운 점이다. 자료구조 pair를 이용한다. first에는 사람의 키를 second에는 같은 키인 사람의 수를 저장한다. 키가 같은 사람이 들어올 경우 같은 키를 갖는 사람만큼 값을 추가해주고 사람수를 + 1 해주고 해당 키를 다시 push해준다. 소스 코드#include <bits/stdc++.h>using namespace std;long long solution(vector<int> heights) { stack<pair<int, int>> st; long long result = 0; for (int heightsIndex = 0; heightsIndex < heights.size(); heightsIndex++) { int height = heights[heightsIndex]; while (!st.empty() && height > st.top().first) { result += st.top().second; st.pop(); } if (!st.empty()) { if (st.top().first == height) { pair<int, int> temp = st.top(); st.pop(); result += temp.second; if (!st.empty()) { result += 1; } st.push({height, temp.second + 1}); } else { result += 1; st.push({height, 1}); } } else { st.push({height, 1}); } } return result;}int main(void) { int numOfPeople; vector<int> heights; cin >> numOfPeople; for (int peopleIndex = 0; peopleIndex < numOfPeople; peopleIndex++) { int height; cin >> height; heights.push_back(height); } cout << solution(heights) << '\n'; return 0;}

0

백준 1406 - 후위표기식

https://www.acmicpc.net/problem/1918 문제 해설문제를 해결할 때 후위 표기식에 대한 명확한 이해와 연산자 우선순위에 대해 고려 해야 한다. 연산자를 별도의 stack에 쌓아가면서 후위 표기식을 만든다. stack에 연산자를 넣기 전에 연산자 비교를 통해 stack에 넣을 려는 연산자 우선순위 보다 stack에 있는 연산자의 우선순위가 작을 때까지 계속해서 stack에서 연산자를 꺼내 후위 표기식에 추가해준다. 연산자 우선순위 (가 제일 높은 우선순위다. * 와 /가 그 다음 우선순위 + 와 -가 다음 우선순위를 갖고 있다. )가 제일 낮은 우선순위다. (를 만날때까지 모든 연산자를 stack에서 꺼낸다. 소스 코드#include <bits/stdc++.h>using namespace std;string str;string result;int main(void) { cin >> str; stack<char> operation; for (int i = 0; i < str.length(); i++) { char cntChar = str[i]; if (cntChar == '(') { operation.push(cntChar); } else if (cntChar == '*' || cntChar == '/') { while (!operation.empty() && (operation.top() == '*' || operation.top() == '/')) { result += operation.top(); operation.pop(); } operation.push(cntChar); } else if (cntChar == '+' || cntChar == '-') { while (!operation.empty() && (operation.top() != '(')) { result += operation.top(); operation.pop(); } operation.push(cntChar); } else if (cntChar == ')') { while (!operation.empty() && operation.top() != '(') { result += operation.top(); operation.pop(); } operation.pop(); } else { result += cntChar; } } while (!operation.empty()) { result += operation.top(); operation.pop(); } cout << result << '\n'; return 0;}

0

백준 1406 - 에디터

https://www.acmicpc.net/problem/1406 문제 해설Stack을 이용한 문제 풀이기본적인 자료구조를 사용해 문제를 해결하는 문제이다. 두개의 스택을 이용해서 커서를 기점으로 커서 왼쪽에 있는 것들은 left 스택에 커서 오른쪽에 있는 단어들은 right 스택에 넣어서 관리를 한다. import java.io.IOException;import java.util.Scanner;import java.util.Stack;public class Main { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); Stack<Character> left = new Stack<>(); Stack<Character> right = new Stack<>(); for (int i = 0; i < str.length(); i++) { left.push(str.charAt(i)); } int numOfCmd = sc.nextInt(); for (int i = 0; i < numOfCmd; i++) { String cmd = sc.next(); if (cmd.equals("L")) { if (!left.isEmpty()) { right.push(left.peek()); left.pop(); } } else if (cmd.equals("D")) { if (!right.isEmpty()) { left.push(right.peek()); right.pop(); } } else if (cmd.equals("B")) { if (!left.isEmpty()) { left.pop(); } } else if (cmd.equals("P")) { char value = sc.next().charAt(0); left.push(value); } } while (!left.isEmpty()) { right.push(left.peek()); left.pop(); } StringBuilder stringBuilder = new StringBuilder(); while (!right.isEmpty()) { stringBuilder.append(right.peek()); right.pop(); } System.out.println(stringBuilder.toString()); }} LinkedList와 ListIterator를 이용한 문제 풀이해당 문제는 LinkedList를 이용해서도 문제를 해결할 수 있다. LinkedList의 원소에 List로 접근을 하게 되면 O(n) 의 시간이 걸려 시간 초과가 뜨게 된다. 때문에 다행이 문제는 Cursor위치를 한칸씩 밖에 못 움직이므로 ListIterator 라는 객체를 이용해 LinkedList를 관리하도록 한다. public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out)); String[] str = br.readLine().split(""); List<Character> charList = new LinkedList<>(); ListIterator<Character> iter = charList.listIterator(); for (int i = 0; i < str.length; i++) { iter.add(str[i].charAt(0)); } int index = charList.size(); int numOfCmd = Integer.parseInt(br.readLine()); for (int i = 0; i < numOfCmd; i++) { char[] inputs = br.readLine().toCharArray(); if (inputs[0] == 'L') { if (iter.hasPrevious()) { iter.previous(); } } else if (inputs[0] == 'D') { if (iter.hasNext()) { iter.next(); } } else if (inputs[0] == 'B') { if (iter.hasPrevious()) { iter.previous(); iter.remove(); } } else if (inputs[0] == 'P') { char value = inputs[2]; iter.add(value); } } for (char c : charList) { wr.write(c); } wr.flush(); }}