큐에다가 순서대로 집어넣는데 만약 같은 사람이 한번 더 신청하면 인덱스번호를 변경해서 큐에다 한번 더 넣는다. 나중에 큐에서 뺄때 해시에 저장된 인덱스번호와 다르면 그냥 넘어가고 같으면 해당 순서가 맞으므로 출력한다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int k, l; unordered_map hash; cin >> k >> l; string num; queue q; for (int i = 0; i > num;..
1인곳을 만나서 visit상태가 아니면 bfs를 돌린다. bfs돌리게 되는 횟수 = 지렁이 개수 #define _CRT_SECURE_NO_DEPRECATE #include #include #include using namespace std; #define MAX 51 int n,t,m,k; int map[MAX][MAX]; bool vis[MAX][MAX]; int ypos[] = { 0,0,1,-1 }; int xpos[] = { 1,-1,0,0 }; int cnt = 0; void bfs(int i,int j) { queue q; q.push({ i,j }); vis[i][j] = true; while (q.size() > 0) { int y, x; tie(y, x) = q.front(); q.pop..
뒤집힌 상태를 나타내는 BOOL 변수 HEAD를 가지고 뒤집힌 상태면 뒤를 삭제하고 아니면 앞을 삭제한다. 속도를 위해 deque을 사용한다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); freopen("input.txt","r",stdin); int t,n; cin >> t; string p; for (int tc = 0; tc > p>>n; string arr; cin >> arr; string tmp = ""; for (int i = 0; i ..
왼쪽으로 빼는게 더 적은지 오른쪽으로 빼는게 더 빠른지 본 뒤 해당 위치로 이동시켜준다 (덱 사용) 뒤로 빼는 경우 맨 뒤 위치에서 앞으로 이동시켜주는 것까지 포함이라 (앞에서만 빼므로) +1 해준다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include #include using namespace std; int n; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int n,m,x; deque dq; cin >> n >> m; for (int i = 0; i < n; i++) { dq.push_back(i+1); } int sum = 0; for (int i = 0; i ..
스택에는 현재 인덱스 i를 집어넣는다. 그 전에 스택이 비어있지 않으면 스택의 최상단(위치 prev)과 현재 높이(위치 i)의 차이 -1(자기자신은 빼줌) 개수 만큼의 빌딩을 볼 수 있다는 이야기이다. n=80000이고 자기 위치 다음 빌딩들이 모두 자기보다 작다하면 80000+ 79999 + 79998 +... 이런 예시가 들어온다 대략 n^2으로 계산하면 6.4*10^9 으로 int 범위가 넘어가므로 ans는 long long 형으로 해준다. #include #include #include #include using namespace std; int n; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; vector v(n)..
https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 커서 (현재 보고 있는 위치)에 동적으로 추가 삭제, 그리고 링크 이동을 연습하는 문제 #include #include #include #include using namespace std; int t; string s; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> t; while (t--) { list li; ci..
https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 두 가지 방법으로 풀 수 있다. 하나는 원소 체크(기록)을 해서 배열의 원소 a에 대해서 x-a가 배열에 있는 지 체크하는 법 또 하나는 정렬 후 투포인터를 이용하는 법. 1. 기록 #include using namespace std; int num[100001]; int cnt[2000001]; int main(void) { ios::syn..
https://www.acmicpc.net/problem/1919 1919번: 애너그램 만들기 두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs www.acmicpc.net #include #include #include using namespace std; int num[26]; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); string s; cin >> s; for (auto c : s) { num[c - 'a']++; } cin >> s; for (auto c : s) { n..
https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 9의 경우는 6인 것처럼 카운팅해준다. 0부터 9까지 몇 개 나왔는지 확인하고 6은 6과 9의 카드 모두 쓸 수 있으니 2로 나눠서 몇 팩이 필요한지 본다. 만약 6이 홀수로 남으면 한 팩이 더 필요하므로 +1 해준다. 나머지 숫자는 한 팩당 카드 하나씩 있으므로 카운팅한 갯수가 필요한 팩의 수이다. 각 숫자가 필요한 팩의 개수 중 가장 큰 수가 답이다. #include #include using namespace std; int num[10]; int main(void) { ios::..
www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net O(n)시간으로 현재 위치 수보다 더 큰 수를 찾는 문제 스택으로 푸는 걸 알고있어서 구현은 금방했는데도 시간 초과가 나서 헤맸다. 배열을 모두 출력할 때 모두 system.out을 쓰기보다 Stringbuilder로 문자열로 만든 다음에 한 번 출력해야 시간초과가 나지 않는다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStr..