백준 알고리즘 1181(단어 정렬) - python, c++

백준 알고리즘 1181(단어 정렬) - python, c++

> https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

길이가 짧은 것부터, 길이가 같으면 사전 순으로 정렬하는 문제

---

python만 하다보니 c++을 너무 까먹어서 다시 같이 해야겠다....

 

[문제 해결 - python]

1. set를 통해 중복을 제거한다.

2. 사전 순으로 먼저 sort

3. lambda를 이용하여 길이가 짧은 순으로 재정렬 후 출력

python 쏘-이지!

 

import sys
N = int(sys.stdin.readline())
# set로 중복 제거
words = list(set([sys.stdin.readline().rstrip() for _ in range(N)]))
# 사전 순 먼저 정렬
words.sort()
# 길이가 짧은 순으로 정렬
words.sort(key=lambda x: len(x))
for i in words:
    print(i)

 

 

[문제 해결 - c++]

오랜만에 여러가지 구조를 기억도 해볼 겸, 유사하지만 다른 두 가지로 풀어내봤다.

[1] string을 감싼 vector로 unique 함수를 활용한 방식

[2] string의 배열로 접근하여 중복일 경우 출력만 하지 않는 방식

 

sort하는 함수(lambda라고 명명)는 동일하게 적용했다.

1. 길이가 다르면 짧은 순으로 return

2. 길이가 같으면 오름차순으로 return

 

문제 풀이 [1] - vector<string> + unique

1. vector<string>으로 push_back하며 입력을 스택

2. lambda를 이용하여 sort

3. unique와 erase 함수를 이용하여 중복 제거

    - unique는 중복 제거되지 않고 밀린 첫 index 주소를 return 해준다.

    - 예를 들어, [1, 1, 2, 2, 3, 4]가 있으면 [1, 2, 3, 4, 1, 2]이 되며 1의 위치를 return 해준다.

    - erase를 이용하여 1의 위치 ~ end까지를 제거하면 중복 제거가 완료된다.

 

문제 풀이 [2] - string[ ] + 중복 스킵

1. string의 배열 size를 20000으로 설정하여 입력을 받는다. (N이 20000이하)

2. lambda를 이용하여 sort

3. 출력 시에 이전 index와 비교하여 같은 같이면 출력하지 않는다. (중복 제거)

 

코드는 한 번에 #define과 #ifdef로 swich 되도록 작성했다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int N;

// VECTOR 방식 또는 STRING 방식 선택
#define VECTOR
//#define STRING


// vector, string의 배열 모두 활용 가능
bool lambda(string word1, string word2) {
	// 길이가 (다르면) 짧은 순으로
	if (word1.length() != word2.length())
		return word1.length() < word2.length();
	// 길이가 같으면 오름차순
	else
		// string의 비교는 사전 순
		return word1 < word2;
}

int main() {
	cin >> N;
	#ifdef VECTOR  // vector로 푸는 경우
		vector<string> words;
		for (int i = 0; i < N; i++) {
			string word;
			cin >> word;
			words.push_back(word);
		}
		sort(words.begin(), words.end(), lambda);
		// python의 set과 유사하지만 제거는 안되는 unique
		// unique는 중복 제거되지 않고 밀린 첫 index 주소를 return한다.
		words.erase(unique(words.begin(), words.end()), words.end());
		for (int i = 0; i < words.size(); i++) cout << words[i] << endl;

	#endif

	#ifdef STRING  // string으로 푸는 경우
		string words[20000];
		for (int i = 0; i < N; i++) cin >> words[i];
		sort(words, words + N, lambda);
		for (int i = 0; i < N; i++) {
			// 중복일 경우 스킵
			if (i > 0 && words[i] == words[i - 1])
				continue;
			cout << words[i] << endl;
		}
	#endif
	return 0;
}