공부정리 아카이브

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

int main() {
	// your code goes here
	char arr[105];

	for(;;){
		cin.getline(arr, 105);
		if(!strcmp(arr, ".")) break;
		stack<char> brr;

		for(int i = 0 ; arr[i] ; i++){
			if(arr[i] == '(' || arr[i] == '[') brr.push(arr[i]);
			else if(arr[i] == ')'){
				if(brr.empty() || brr.top() == '[') brr.push(arr[i]);
				else if(brr.top() == '(') brr.pop();
			}
			else if(arr[i] == ']'){
				if(brr.empty() || brr.top() == '(') brr.push(arr[i]);
				else if(brr.top() == '[') brr.pop();
			}
		}

		if(brr.empty()) cout << "yes\n";
		else cout << "no\n";
	}

	return 0;
}

- 이것저것 많지만 결론은 괄호 짝 찾기 문제다. 스택을 이용하면 간편하게 해결 가능.
- 다만 공백을 포함한 문자열 입력을 못하면 좀 까다로운 문제였다.

- 예제 입력이 이런데 그냥 cin이나 scanf로 입력을 받으면 맨 마지막줄의 " ." 이 앞 공백이 빠져서 종료 코드로 인식을 해버린다.
- <string> 객체를 쓰면 더 편하게 처리가 가능하지만 아직 배우기 전이므로 사용 가능한 cin.getline(문자열, 크기)를 사용한다. 크기는 넉넉잡아도 개행("\n")이 들어오면 알아서 끊어주니 공백이 있는 입력 처리에는 상당히 간편할 듯하다.

- 그림으로 그려보니 풀이가 확실히 보였던 문제.

- 예제 입력 2를 푼다고 해보자. 원형으로 배치한 순열이 입력 n=10이기 때문에 1~10으로 입력된 숫자이고, m은 길이 3의 숫자를 찾을 것이고, 두번째 줄의 2,9,5를 순서대로 찾을 예정이라고 한다.

- 원형 순열을 원형 다이얼을 돌려가면서 찾는다고 하면 꽤 괜찮은 풀이법이 나온다고 본다. 이 다이얼을 시계/반시계 중 어느쪽으로 돌려야 빠르게 찾을 수 있는가를 생각해보자. 결국 한쪽으로 돌릴 때랑 반대쪽으로 돌릴 때 중 짧은 길이를 더해가며 계산하면 간단히 풀리는 문제이다.

- 바킹독 님의 알고리즘 https://blog.encrypted.gg/935?category=773649 강의를 참조하며 풀었기 때문에 deque 자료구조로 문제를 해결했다.

#include <iostream>
#include <deque>
using namespace std;

int main() {
	// your code goes here
	deque<int> a, b;
	int n, m;
	cin >> n >> m;
	for(int i = 0 ; i < n ; i++){
		a.push_back(i+1);
	}
	for(int i = 0 ; i < m ; i++){
		int k;
		cin >> k;
		b.push_back(k);
	}
	
	int cnt = 0;
	int front=0, back=0;
	while(!b.empty()){
		if(a.front() == b.front()){
			back = a.size() - front;
			cnt += front > back ? back : front;
			a.pop_front();
			b.pop_front();
			front=back=0;
		}
		else{
			a.push_back(a.front());
			a.pop_front();
			front++;
		}
	}
	
	cout << cnt;
	return 0;
}

STL 연습겸 STL stack으로 풀긴 했지만 배열이 더 효율적일 듯한 문제.

1부터 n까지의 숫자가 순서대로 들어온다고 하니, 크게 답변 출력을 위한 문자 stack과 값 저장을 위한 int형 stack 두개를 선언한다.

int형 변수를 하나 선언해서 그거보다 큰 값이 들어오면 같아질때까지 stack에 push 후, 같아지면 pop하는 식으로 구현한다.

들어온 숫자가 int변수보다 작은 경우는 두가지일 것이다. top에 있어서 수열로 만들 수 있거나, 아니면 top에 없으므로 수열로 구현 불가능하거나.

#include <iostream>
#include <stack>
using namespace std;

int main() {
	// your code goes here
	stack<int> in;
	stack<char> ans, ans_;
	int a;
	cin >> a;
	
	for(int i = 0, j = 0 ; i < a ; i++){
		 int b;
		 cin >> b;
		 if(b > j){
		 	while(b != j){
		 		in.push(++j);
		 		ans.push('+');
		 	} 
		 }
		 if(b == in.top()){
		 	in.pop();
		 	ans.push('-');
		 }
		 else{
		 	cout << "NO";
		 	return 0;
		 }
	}
	
	
	while(!ans.empty()){
		ans_.push(ans.top());
		ans.pop();
	}
	while(!ans_.empty()){
		cout << ans_.top() << "\n";
		ans_.pop();
	}
	return 0;
}

요세푸스 순열은 여기서 그려볼 수 있다. Josephus Problem – GeoGebra

C++의 list STL로 풀고자 했던 문제. 처음 데이터를 저장하는 list와, 요세푸스 순열을 저장하는 list를 각각 선언 후, 저장 list를 하나씩 지워가며 순열 list로 옮기도록 코드를 작성했다.

그런데 list STL의 erase의 원리가 잘 이해되지 않아 한참을 헤메야 했다.
stl erase는 원소를 지운 후 다음 원소의 주소를 반환한다.
예를 들어 원소가 1,2,3,4일때 iterator가 3을 가리키는 상태에서 erase(iterator)를 하면, 원소는 3을 없애고 4를 가리킬 것이다.

이때 k번째 원소를 없앤다고 할 때 index i를 두고 나머지가 0이 되는 시점에 원소를 제거하게 했더니, index는 그대로인 채 원소만 제거되면서 코드가 생각한 대로 돌지 않는 문제가 발생해버렸다.

이를 해결하고자, erase가 발생하는 시점에서는 iterator를 하나 이전으로 돌려주는 방식으로 코드를 작성했다.
이상한 점은, erase 후 iterator를 --해 주는 코드를 한 줄에 작성했더니 동작이 또 이상하게 나타난다. 함수 내부에서 동작하면서 원래 값을 수정하는 게 있는건지...

#include <iostream>
#include <list>
using namespace std;

int main() {
	// your code goes here
	list<int> arr, ans;
	list<int>::iterator cur_arr;
	
	int n, k;
	cin >> n >> k;
	for(int i = 0 ; i < n ; i++){
		arr.push_back(i + 1);
	}
	int i = 1;
    cur_arr = arr.begin();
	while(!arr.empty()){
		if( i % k == 0){
			ans.push_back(*cur_arr);
			cur_arr = arr.erase(cur_arr);
			cur_arr--;
		}
		
		i++;
        cur_arr++;
        if(cur_arr == arr.end()) {
            cur_arr = arr.begin();
        }
	}
	list<int>::iterator c = ans.begin();
	cout << '<' << *c;
	for(c++ ; c != ans.end() ; c++){
		cout << ", " << *c;
	}
	cout << '>';
	return 0;
}

문제

피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다.

입력

첫 번째 줄에 A와 B(1≤A, B≤100,000), N(1≤N≤1,000,000)이 공백을 경계로 주어진다.

출력

A÷B를 했을 때, 소숫점 아래 N번째 수를 출력한다.

- 소숫점 문제라서 단순히 %연산을 썼는데 틀려버렸다.
- 생각해보니까 float/double은 부동소수점이라 아래 자리수가 커질수록 정확도가 낮아짐(1,000,000번째 자리수까지 따지고 있다...double이 지원하던가 애초에?)

- 컴퓨터 연산 대신 손으로 푸는 나눗셈 풀이로 풀어보기로 함

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int a, b, n;
	int res = 0;
	
	cin >> a >> b >> n;
	if( a % b == 0){
		cout << 0;
		return 0;
	}
	
	if( a > b ) a = a % b;
	
	for(int i=0;i<n;i++){
		a *= 10;
		res = (int)(a / b);	
		a = a % b;
	}
	cout << res;
}

만약 나눠 떨어지면(나머지가 0이면) 바로 0을 출력하고,
그렇지 않으면 a의 자리수를 하나 올린 후, 몫을 출력한다. a는 나머지로 갱신한다.
n번째 자리수까지 이를 반복한 후 마지막 연산의 몫이 n번째 자리수 소수가 된다.

import sys
input = sys.stdin.readline

l = int(input().strip())
arr = []

for iter in range(l):
    a = input().strip().split(' ')
    if(a[0] == 'push'):
        arr.append(a[1])
        
    elif(a[0] == 'pop' or a[0] == 'top'):
        if(len(arr) == 0) :
            print('-1')
            continue
        print(arr[-1])
        if(a[0] == 'pop') : del arr[-1]
        
    elif(a[0] == 'empty'):
        print('1' if len(arr) == 0 else '0')
        
    else:
        print(len(arr))

스택의 기본 동작인 push, pop 등을 구현하는 문제. python을 이용하면 쉽게 풀 수 있다.

그런데 아무리 해도 시간초과가 떠서 질문란을 살펴보니 sys.stdin.readline을 사용하라고 하는데, 흔히 입력에 쓰는 input() 함수의 경우 입력 > prompt 출력 > strip(개행 제거)의 과정을 거치므로 대량 입력 시 시간 지연이 심해질 가능성이 있다고 한다.

이것때문에 시간초과로 5번이나 실패했다 ㅜㅜ...