#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
for (int i = 1000; i < 10000; i++) {
vector<int> binary;
vector<int> hexadecimal;
vector<int> decimal;
int n = i;
while (n != 0) {
binary.push_back(n % 12);
n /= 12;
}
n = i;
while (n != 0) {
int a = n % 16;
hexadecimal.push_back(a);
n /= 16;
}
n = i;
while (n != 0) {
decimal.push_back(n % 10);
n /= 10;
}
int hexadecimalSum = 0;
int decimalSum = 0;
int binarySum = 0;
for (int num : decimal)
decimalSum += num;
for (int num : hexadecimal) {
hexadecimalSum += num;
}
for (int num : binary)
binarySum += num;
if (binarySum == decimalSum && decimalSum == hexadecimalSum)
cout << i << '\n';
}
return 0;
}
정말 오늘따라 더 느끼는 문제 똑바로 읽기의 중요성.
2진수인줄 알고 2진수, 10진수 16진수로 했는데 답이 안 나와서 이걸가지고 한 시간을 헤맸다. 그런데 12진수였다.
#include <iostream>
using namespace std;
int main() {
int l, p;
cin >> l >> p;
for (int i = 0; i < 5; i++) {
int a;
cin >> a;
cout << a - p * l << " ";
}
return 0;
}
오늘 다시 한 번 느낀 것. 문제를 똑바로 읽자. l이 기사의 개수인 줄 알고 for문을 i =0부터 i < l까지 돌려서 틀렸었다.
지난 포스팅의 내용을 간단히 정리하자면 컬렉션 프레임워크는 인터페이스와 클래스로 구성되어 있는데 Collection, List, Queue, Set, Map 이 5가지가 인터페이스이다. (이 인터페이스 5가지는 꼭 알아두자.)
List 인터페이스의 ArrayList는 자주 사용하므로 꼭 알아놔야 하고 LinkedList의 특이한 점은 List의 구현 클래스이자 Queue의 구현 클래스라는 거. Vector는 ArrayList와 똑같은데 Vector는 동기화를 지원하고 ArrayList는 동기화를 지원한다는 거, 따라서 동기화가 필요한 멀티스레딩이 아니라면 ArrayList를 쓰는 게 낫다. 멀티스레딩이 아닌데 굳이 Vector를 쓰면 performance가 더 떨어진다.
Set은 순서가 중요하지 않고 동일한 데이터가 없는 자료구조이다. Set에는 HashSet과 TreeSet이 있다는 것 정도는 알아두자. 굳이 HashSet과 TreeSet의 차이점을 말하자면 HashMap은 동기화를 지원하지 않고 Hashtable은 동기화를 지원한다. 그리고 HashMap은 key 값이든 value 값이든 null을 사용할 수 있는데 Hashtable은 null의 사용이 불가능하다.
List는 인터페이스이기 때문에 객체를 생성하지 못한다. 따라서 자식 클래스인 ArrayList 등을 사용해야 하는데 선언할 때에는
List<Integer> list = new ArrayList<>();
ArrayList가 아니라 이렇게 List 타입으로 많이 선언하는 것 같다. 그리고 나서 객체를 생성할 때에 구현 클래스로 생성하는 것이다. 대부분 이렇게 많이 쓰므로 그냥 관습에 따르는 것이 좋다.
List와 Set은 서로 반대되는 성질을 가지고 있다.
List는 순서가 있고 중복될 수 있는 반면 Set은 순서가 없고 중복될 수 없다.
Collection 인터페이스에서는 여러가지 메소드로 다양한 기능들을 제공한다. (지난 포스팅에 메소드들을 정리해놓았다.) 하지만 배열은 그렇지 않다. 메소드가 없다. 즉 기능이 별로 없다. 배열의 크기를 알고 싶으면 배열이름.length()가 아니라 배열이름.length이다. 메소드가 아니다. 하지만 String은 문자열의 길이를 알고 싶으면 문자열.length()이고 컬렉션도 컬렉션에 저장된 원소의 개수를 알고 싶다면 컬렉션객체.size()이다. 이렇게 크기를 알아내는 방법만 봐도 기능이 많은 String과 Collection은 메소드로 크기를 알아낸다.
따라서 가능하면 기초형보다는 참조형이 좋다. 사실 배열도 참조형인데 기초형의 데이터를 여러개 모아놓은 정도이기 때문에 기능이 별로 없다.
컬렉션은 제네릭 타입이기 때문에 <> 사이에 타입을 써주는 것이 좋다. <> 사이에는 int, double, boolean과 같은 기초타입은 쓰면 안 되고 참조 타입을 써줘야 한다. 기초타입을 쓰고 싶다면 Integer, Double, Boolean과 같은 Wrapper 클래스로 써줘야 한다. 그래도 자동 형변환이 되어 오류가 안 난다.
이제 본격적으로 Map을 배워보자. 일단 기본적인 Map의 메소드들부터 살펴보자.
void clear()
맵에 있는 모든 엔트리를 삭제한다.
boolean containsKey(Object key)
key라는 키를 가진 엔트리가 있는지 없는지를 반환한다.
boolean containsValue(Object value)
value라는 값을 가진 엔트리가 있는지 없는지 반환한다.
Set> entrySet()
맵에 있는 모든 엔트리를 원소로 하는 Set 객체를 만든다.
V get(Object key)
key에 해당하는 value를 반환한다.
boolean isEmpty()
맵 객체가 비어있는지 아닌지를 반환한다.
Set keySet()
key값들을 모아 Set 객체를 만든다.
V put(K key, V value)
key-value 엔트리를 맵 객체에 추가한다.
V remove(Object key)
key에 해당하는 엔트리를 삭제한다.
int size()
맵 객체에 저장된 엔트리의 개수를 반환한다.
Collection values()
맵에 저장된 value들을 모아 컬렉션 객체를 만든다.
Map 인터페이스는 키와 값을 쌍으로 저장한다. 메소드만 봐도 containsKey(), containsValue()라는 메소드가 있다.
Map에 저장된 객체 중에 해당 key 또는 value가 있는지를 알아낼 수 있다.
get 메소드는 key를 주면 value가 나오는 메소드이다. key가 유일하기 때문에 key로 접근해서 value를 얻어올 수 있다.
isEmpty()는 굳이 외우지 않아도 당연히 알테고 put 메소드는 Collection으로 따지면 add와 같은 메소드이다. Map 객체가 타입이고 맵 객체 이름이 map이라면 map.put("one", 1); 이렇게 하면 one을 key로, 1을 value로 하는 하나의 쌍이 Map에 추가된다.
Map은 key와 value 이렇게 두 가지 데이터를 하나의 쌍으로 저장하기 때문에 Collection과는 조금 다르다. 하지만 Map 타입을 Collection으로 바꿔야 할 수도 있다. Map을 Collection처럼 이용하고 싶다면 3가지 방법이 있다.
① keySet()
keySet()을 이용하면 결과는 Set이 나온다. 맵이 Map<K, V> 였다면 Set은 Set<K>가 반환타입으로 나온다.
맵의 key값들을 모으니 당연히 Set의 원소들의 타입은 Map의 key 타입이 나올 것이다.
즉, Map에서 key 타입이 String이었다면 keySet()의 반환타입은 Set<String>이라는 것이다.
Map에서 key 값들은 유일하기 때문에 중복된 값이 없는 자료구조인 Set이 딱이다.
다음 코드는 Map 객체에서 key값들만 뽑아내서 Set에 저장하는 코드이다.
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class CollectionTest {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("김철수", 15);
map.put("김영희", 15);
map.put("홍길동", 40);
System.out.println(map);
Set<String> names = map.keySet();
System.out.println(names);
}
}
Map 객체에 데이터를 추가하려면 put() 메소드를 쓰면 된다. 첫 번째 원소는 key, 두 번째 원소는 value.
위 코드의 실행 결과
Map에서의 key값이었던 이름들을 모아서 Set으로 잘 만들어진 것을 볼 수 있다.sfdasfafasfaf
2. values()
key값이 아니라 value 값들만 모아서 Collection으로 만들고 싶다면 values() 메소드를 사용하면 된다.
Map에서 key값과 달리 value 값들은 중복이 있을 수도 있고 순서가 중요할 수도 있으므로 Set으로는 못 만든다. 그리고 사용자가 Queue로 바꾸고 싶은지 Set으로 바꾸고 싶은지 List로 만들고 싶은지 모르기 때문에 일단 가장 최상위 클래스인 Collection 타입으로 반환한다. 그 후에 사용자가 원하는 타입으로 바꾸면 된다. ArrayList로 바꾸고 싶으면 ArrayList로 바꿀 수 있다. (그 방법은 뒤에서 설명할 것이다.)
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
public class CollectionTest {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("김철수", 15);
map.put("김영희", 15);
map.put("홍길동", 40);
System.out.println(map);
Collection<Integer> ages = map.values();
System.out.println(ages);
}
}
위 코드의 실행 결과
여기에서 영희와 철수의 나이는 모두 15살인데 정보가 손실되지 않고 15가 두 개 다 들어간 것을 볼 수 있다.
Map에서 value 값들은 중복될 수 있다는 것을 잊지말자.
3. entrySet()
entrySet()은 Map의 key-value 한 쌍을 하나의 원소로 보는 Collection으로 바꿔준다. 이는 Map과 다르게 하나의 원소 자체가 pair이다. Map.Entry 이렇게 쓴 것에서 알 수 있듯이 Entry는 Map 인터페이스의 내부 인터페이스이다. (내부인터페이스 또는 내부클래스는 외부인터페이스.내부인터페이스 이렇게 쓴다.)
entrySet()은 Map을 key와 value를 합쳐서 한 개의 데이터로 사용하는 Collection으로 바꾸겠다는 것이다.
반환타입은 Set<Map.Entry<K, V>>이다. 왜 Set일까? value는 중복이 있을 수 있지만 key값과 value값을 합치면 유일하다.
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
public class CollectionTest {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("김철수", 15);
map.put("김영희", 15);
map.put("홍길동", 40);
System.out.println(map);
Collection<Map.Entry<String, Integer>> nameAndAges = map.entrySet();
System.out.println(nameAndAges);
}
}
위 코드의 실행 결과
위의 출력 결과는 {}인 것을 봐서 Map이고 아래는 []인 것을 봐서 Collection인 것을 알 수 있다. Map을 Collection으로 바꾼 것이다.
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> student[32001];
for (int i = 0; i < m; i++) {
int shorter, taller;
cin >> shorter>> taller;
student[taller].push_back(shorter);
}
vector<int> result;
while(result.size() < n) {
for (int i = 1; i <= n; i++) {
if (student[i].size() == 0 && result.size() < n) {
result.push_back(i);
for (int j = 1; j <= n; j++) {
for (int k = 0; k < student[j].size(); k++) {
if (student[j][k] == i) student[j].erase(student[j].begin() + k);
}
}
}
}
}
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
return 0;
}
딱 봐도 시간초과가 날 것인게, while문 안에 3중 for문을 썼다. 반복문을 4개를 중첩해서 쓰니까 당연히 그럴 수밖에 없다.
그래서 다시 풀었다.
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> student[32001];
vector<int> inDegree(n + 1);
for (int i = 0; i < m; i++) {
int shorter, taller;
cin >> shorter>> taller;
student[shorter].push_back(taller);
inDegree[taller]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) q.push(i);
}
while(!q.empty()) {
int cur = q.front();
q.pop();
cout << cur << " ";
for (int i = 0; i < student[cur].size(); i++) {
inDegree[student[cur][i]]--;
if (inDegree[student[cur][i]] == 0) q.push(student[cur][i]);
}
}
return 0;
}
역시 알고리즘은 정석대로 자료구조 책에 있는 방법대로 해야 하나보다. 그래도 자료구조 수업에서 위상정렬을 배운지 거의 6개월이 넘었는데 방법을 잊지 않고 스스로 구현했다는 것이 대단하다.
