[백준] 2750번, 1181번, 1431번

2750번

C를 이용한 풀이:

N(1 ≤ N ≤ 1,000)의 숫자가 주어진다. 제한 시간은 1초이고 1초 동안 약 1억개의 연산을 할 수 있으므로, 이렇게 수가 적은 경우에는 시간복잡도가 높은 알고리즘을 사용해도 풀 수 있다. 그래서 가장 기본적인 선택 알고리즘을 사용해본다.

#include <stdio.h>

int arr[1001];

int main(void){
	int num, i, j, temp, min, index;
	
	scanf("%d", &num);
	for(i=0; i<num; i++){
		scanf("%d", &arr[i]);
		
			}
	for(i=0; i<num; i++){
		min = 1001; // 주어지는 n 의 최대가 1000이므로 
		for(j=i; j<num; j++){
			if(min>arr[j]){
				min = arr[j];
				index = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
	}
	
	for(i=0; i<num; i++){
		printf("%d\n", arr[i]);
	}
	return 0;
}

1181번

문제)

알파벳 소문자로 이루어진 n개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터

2. 길이가 같으면 사전 순으로

 

입력)

첫째 줄에 단어의 개수 n이 주어진다. (1<=n<=20000) 둘때 줄부터 n개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 지 안는다.

 

출력)

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

 

답안)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool p_compare(pair<string, int> a, pair<string, int> b){
	if(a.second == b.second){
		return a.first < b.first; //사전 순 정렬 
	}else{
		return a.second < b.second; //짧은 게 먼 
	}
}


int main(void){
	
	string str;
	int num;
	
	cin >> num;
	vector<pair<string, int> > v;

	
	for(int i = 0; i<num; i++){
	
		cin >> str;
		v.push_back(pair<string, int>(str, str.length()));
		
	}
	
	sort(v.begin(), v.end(), p_compare);
	
	for(int i = 0; i<num; i++){
		if(i>0 && v[i-1] == v[i]){
			continue;
		}
		cout << v[i].first << '\n';
	}
	
	return 0;
}

 

반성점:

1) 일단 string 에 length()라는 함수 있으니까 바로 불러내면 되고, 따로 pair정의해서 공간 차지할 필요가 없음.

2) compare함수 구성에 주의하자!

3) string 간에 != 는 안먹나보다..

4) && 을 이용해서 조건확인문을 간단하게 만들자!

 

1431번

* string => char => int

- 내림차순으로 >, < 연산 가능

- strcpy 는 cstring 네임스페이스에 있음 (iostream만으로도 가능하다는 얘기도)

- 스트링 -> char[]로 변환:

	strcpy(strarr, a.c_str());

- char[] 중에 숫자만 뽑은 후, int 로 변환해서 더하기:

if(strarr[i]<='9'){
			cout << strarr[i];
			int temp = strarr[i]-'0';
			sum += temp;
		}

답안)

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int n;
string arr[1000];

int sum_sn(string a){
	int sum = 0;
	char strarr[50];
	strcpy(strarr, a.c_str());
	for(int i = 0; i<a.length(); i++){
		if(strarr[i]<='9'){
			int temp = strarr[i]-'0';
			sum += temp;
		}
	}
	return sum;
	
}
bool compare(pair<string, int> a, pair<string, int> b){
	if(a.first.length()==b.first.length()){
		if(a.second == b.second){
			return a.first < b.first;
		}else {
			return a.second < b.second;
		}
	}else{
		return a.first.length()<b.first.length();
	}		
}

int main(void){
	
	string temp;
	cin >> n;
	vector<pair<string, int> > v;

	for(int i = 0; i<n; i++){
		cin >> temp;
		v.push_back(pair<string, int>(temp, sum_sn(temp)));
	}
	
	sort(v.begin(), v.end(), compare);
	
	for(int i=0; i<n; i++){
		cout << v[i].first << '\n';
	}
	return 0;
	
	
}

 

 

반성할 것:

나는 string 이 바로 배열로 사용이 안되는 줄 알고 char[]에 옮겨주었는데 필요 없는 일이었으며...

굳이 char을 또 int 로 바꿔줄 필요 없이 그냥 arr[i]-'0'을 해주면 됐다. 고로 내 코드는 쓸데 없는 부분이 매우 많다!

여기서도 전 문제와 같이 굳이 vector나 pair를 쓸 필요가 없다. 그냥 string으로 하면 됨....

ㅠㅠ

 

 

참고한 자료:

char형 데이터 int형으로 변환하기 https://eblee-repo.tistory.com/45

strcpy https://kldp.org/node/120480