iridescent

www.acmicpc.net/problem/1373

처음 생각했을 땐, 오 쉬운데 했다.

근데 2진수에서 8진수로 바꿔야 하니깐. 

지금 연습하고 있는 c++언어로 하기로 했다. 

먼저 내 생각은 문자열로 받아서

10개의 길이를 받는다면, 

만약 

1 0 1 1 0 1 1 0 1 0

을 받는다면 

이렇게 바꿔야 한다. 

그래서 나는 계산을 해보았다, 

사이즈를 가지고 처음부터 계산을 해보자 해서

일단 그럼 1 2 4를 가지는 배열(eight)을 정해놓고 이용하자라는 생각이 들었다.

(size - i) % 3을 하면 1이 남으니깐,

계산하기 위해 정해놓은 배열(eight)의 eight [0] == (1)이 된다. 

그런데 eight의 방은 0번방인데, (size - i) % 3 은 1이 나오니깐 단순히 -1을 하기에는

size가 10일때 i가 4이면,

(size - i) % 3 => 0이 나오는데 나의 의도로는 2가 나와야 한다. 

그래서 (((size - i) % 3 ) +2 )%3 을 해줬다. 

2를 넘으면 안 돼서 ,,,

그렇게 3자리를 더하고 

만약 (size - i) % 3 이 1이 나오면 == {1, 2, 4}에서 1까지 다 더한 후라면

다 더한 값을 vector를 통해 뒷부분에 넣었다. 

그랬더니 한번에 통과!

소스 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
	string input;
	vector<int> answer;
	int eight[4] = { 1,2,4};
	int size;
	int sum = 0; 
	
	//문자 받기
	cin >> input;

	size = input.length();
	for (int i =0; i <size; i++) {
		if (input[i] == '1') {
			sum += ((input[i]-'0') * eight[(((size - i) % 3) + 2) % 3]);
		}
		if ((size - i) % 3 == 1) {
			answer.push_back(sum);
			sum = 0;
		}
	}
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i];
	}
	return 0;
}

c++을 잘 안써봐서

많이 필요 없는 부분이 있을 수 있는데, 

그래도 쓰고 통과해서 좋았다. 

www.acmicpc.net/problem/10808

c언어와 c++을 같이 해보았다.

이 문제는 쉬웠는데 

확실히 같은 코드인데 

c++의 메모리가 많이 차지하는걸 알 수 있다. 

코드 c++ 

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

int main() {
	string input;
	int answer[26] = { 0 };
	
	cin >> input;
	for(int i = 0; i < input.length(); i++){
		answer[input.at(i) - 'a']+= 1;
	}
	for (int i = 0; i < 26; i++) {
		printf("%d ", answer[i]);
	}
	return 0;
}

코드 c

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

int main() {
	string input;
	int answer[26] = { 0 };

	cin >> input;
	for(int i = 0; i < input.length(); i++){
		answer[input.at(i) - 'a']+= 1;
	}
	for (int i = 0; i < 26; i++) {
		printf("%d ", answer[i]);
	}
	return 0;
}

https://www.acmicpc.net/problem/1874

이 문제는 처음에 내가 이해를 잘 못했다.

수열로 뭐 하는거지? 뭐라는거야...

왜 입력이 8개인데 출력이 이렇게 많을까? 이랬는데 이해를 해보니깐 아. 탄성이 나왔다.

먼저 설명을 하자면,

백준 예제로 보자. 

입력이 

8 4 3 6 8 7 5 2 1

들어왔다.

처음의 8은 testcase수이다. 

그럼 4부터 봐야한다. 

(4 3 6 8 7 5 2 1) 

여기 문제에서 

"1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓으로써,,,"를 잘 봐야한다. 

이 말은 1부터 스택에 넣는데 원하는 수가 보이면 pop한다는 말이다. 

예시를 들어보자면,

4부터 해보자

4가 나오기 위해 push(1), push(2), push(3), push(4)를 해야하고, 4를 pop해서 꺼내와야 문제에서 말하느 수열을 만들 수가 있다. 

4를 만들기위해서는  push(1), push(2), push(3), push(4), pop(4)를 해야하기 때문에 ++++-가 되는 것이다. 

그렇다면, 이어서 4다음의 수 3을 해보자

4가 pop한 상태이기 때문에 스택의 꼭대기 층에는 3이 있다. 

3을 원하기 때문에 여기서는 pop(3)만 해주면 된다. 

이렇게 해서 이 수열을 만들기 위해서 +,-가 어떻게 들어가는지를 출력하는 것인데,

수열을 못 만들때는 NO를 입력해라고 한다. 

이 말이 무엇이냐면,

여기서 간단히 말하자면, 꼭대기에는 4가 있는데 3을 원할때이다. 

스택은 먼저들어오는 수가 나중에 나가는 구조이기 때문에

꼭대기의 수 부터 나가야 밑의 수가 나갈 수 있다.

다시말해 3이 나가려면 4가 꼭 pop해줘야 나갈 수 있다는 말이다. 

그래서 저 상태에서 3을 원한다면, 이것은 만들 수 없는 구조이기 때문에 NO를 출려해야한다. 

이 문제를 이해하고 나서 알고리즘을 짰다. 

은근 알고리즘은 쉬웠는데, 문제를 이해하기가 좀 당황했었다. 

알고리즘
1. 수를 입력받는다. 
2. 기억하는 숫자(1부터 n까지) ~ 입력 받은 수까지 반복한다. (어차피 원하는 수까지 push를 해야하기 때문)
   2-1) 스택에 저장한다. 
   2-1) +출력한다.
3. stack의 꼭대기의 수가 입력받은 수라면
   3-1) pop을 해준다. 
4. stack의 꼭대기의 수가 입력받은 수가 아니라면,
   4-1) 이것은 수열을 만들 수 없기 때문에 NO를 출력하고 break해준다. 

소스 코드

#include <stdio.h>
#include<stdbool.h>
int main() {
	int remember_number = 1;
	int testcase;
	int top = -1;
	int stack[100001];
	int number; 
	char answer[200000];
	int answer_count = 0;
	bool answer_check = true;


	scanf("%d", &testcase);

	for(int T = 0; T<testcase; T++){
		scanf("%d", &number);
		for (; remember_number <= number; remember_number++) {
			stack[++top] = remember_number;
			answer[answer_count++]= '+';
		}

			if (stack[top] == number) {
				--top;
				answer[answer_count++] = '-';
			}
			else {
				printf("NO");
				answer_check = false;
				break;
			}
	}
	if (answer_check) {
		for (int i = 0; i < answer_count; i++) {
			printf("%c\n", answer[i]);
		}
	}
	return 0;
}

https://www.acmicpc.net/problem/9012

처음 시도했을때는 숫자를 세어, 맞는지 틀린지 확인을 했는데,

괄호를 생각해보니깐 

여는 괄호가 없는데 닫는 괄호가 나오면 안되는 것이였다. 

그래서 다시 알고리즘 생각해보았다. 

알고리즘

1. 괄호를 입력 받는다. 
2. 괄호의 수 만큼 반복문을 돌린다. (여기에서 top는 0보다 크거나 같아야함.)
    (top가 0보다 작다는 말은 닫는 괄호가 여는 괄호보다 먼저 나왔다는 말이기 때문에 반복문 종료)
   2-1) 만약 해당 문자가 '('라면 top++
   2-2) 만약 해당 문자가 ')'라면 top--
3. 만약 top가 0이라면 (제대로 된 것) YES출력
4. top가 0이 아니라면(여는 괄호가 많거나, 닫는 괄호가 많거나, 닫히지 않았는데 열렸거나, 열리지 않았는데 닫힌 경우) NO

#include <stdio.h>
#include <string.h>
int main() {

	int testcase;
	char input[51];
	int top = 0;
	scanf("%d", &testcase);
	while (testcase--) {
		top = 0;
		scanf("%s", &input);
		for (int i = 0;top >= 0 && i<strlen(input); i++) {
			if (input[i] == '(')
				top++;
			else if (input[i] == ')')
				top--;
		}
		if (top == 0)
			printf("YES\n");
		else 
			printf("NO\n");

	}
	return 0;
}

https://www.acmicpc.net/problem/9093

간단한 단어 뒤집기다. 

뛰어쓰기가 나오면, 각 나온 단어를 뒤집는 것이다. 

예를 들어

 hi, my id is iridescent.

ih, ym di si tnecsediri.

이렇게 바꾸는 것이다.

알고리즘 생각은 매우 간단했다. 

알고리즘

1. 먼저, 테스트 케이스를 받고

2. 입력 버퍼를 지운다.

    2-1) i-1의 자리가 \n일때 까지 돌린다. (왜냐하면 \n를 만나는 것과 " "만나는 것을 한꺼번에 처리하기 위해서다)

    2-2) 현재 자리가 빈칸이거나 \n자리이면

        a) 현재자리 -1 부터 (현재자리가 개행문자이기 때문) top까지(top은 출력했던 자리 표시) 출력한다.

        b) top의 자리는 현재자리로 새로 갱신해준다.     

#include<stdio.h>

int main() {
	char input[1001];
	int top = -1;
	int testcase;

	scanf("%d", &testcase);
	getchar();
	while (testcase--) {
		fgets(input, 1001, stdin);
		for (int i = 0; input[i-1]!='\n' ; i++) {
			if (input[i] == ' ' || input[i] == '\n') {
				for (int j = i-1; j > top; j--) {
					printf("%c", input[j]);
				}
				top = i;
				printf(" ");
			}
		}
		printf("\n");
		top = -1;
	}
	return 0;
}

https://www.acmicpc.net/problem/4948

이 문제는 소수를 일일이 구한다면 제한된 시간내에 어렵다고 보면 된다.

그래서 

'에라토스테네스의 체' 알고리즘이란,
2부터 소수를 구하고자 구간의 모든 수에서

2 * 2 , 2 * 3, 2 * 4 ,,,,
2부터 2곱한 수, 3곱한수를 지운다.
3도 마찬가지로, 3 * 2, 3 * 3, 3 * 4,,,


일정 구간까지 곱한 수의 배수를 지운다. 

위 과정을 반복한다면 소수가 남는다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

1. 수를 받는다
2. 2부터 그 수의 제곱근까지
   • 2부터 ~ 배수가 <= 2 * 그 수까지  (문제에서 2N수까지 소수를 구하라고 해서
   • 배열[그 수의 배수] 자리에 -1를 넣는다.
3. 받은 수부터 2N까지 -1이 아닌 수가 나오면 sum++

※ 이게 배열에 -1넣는 것의 중복을 피하기 위해,

이전 값이 어디까지 곱했는지 기억하고, 그 안의 수를 알고 싶을 땐 안 한 값만 하고싶었는데

틀렸다,, 근데 구현을 한다면 할 수 있을 것 같다.

소스코드↓

#include<stdio.h>
#include<math.h>



int main() {
	int num;
	
	int sum = 0;
	int check[246913] = { -1,-1,1 };
	
		
	while (1) {

		scanf("%d", &num);
		if (num == 0)
			return 0;
		
		for (int end_num = 2; end_num <= sqrt(2 * num); end_num++) {
			for (int j = 2; end_num * j <= 2 * num; j++) {
				check[end_num * j] =-1;
 			}
		}
		sum = 0;
		for (int i = num+1; i <= 2 * num; i++) {
			if (check[i] >-1)
				sum++;
		}
		printf("%d\n", sum);
		if(befor_num < num * 2)
			befor_num = num * 2;
	}

}