[C++] 백준 1181번 단어 정렬

오늘도 블로그로 출근~~

할 수 있다~~!!

 

이렇게 블로그에서 일기 쓰듯이 하니까 좀 재밌는 것 같기도 하다 ㅎㅎ(나를 여기로 이끌어준 지인에게 감사)

 

음...오늘은 어떤 문제를 풀지 찾아보다가

나는 숫자나오는 문제를 좋아하고 문자 나오는 문제를 싫어해서 문자 나오는 문제는 이런 저런 핑계로 안 풀었던 것이 기억이 났다. 어쩌다보니 저번에는 string을 사용하기는 했는데, 그것은...숫자였으니까 이번에는 진짜로 문자가 입력되는 문제를 풀어보도록 하겠다!!

문제

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

1181번: 단어 정렬

 

일단 N개의 단어들을 벡터에 넣어줘야겠다. 그리고 sort함수로....

음... sort 함수로 문자열을 정렬해주면 a, b, c, d, ... 순으로 정렬해주는데...(어쩌지)

 

이럴 땐.. 검색...

C++에서는 string이 클래스 형태로 제공되기 때문에 유용한 함수를 많이 사용할 수 있다고 한다.

https://chanhuiseok.github.io/posts/algo-37/

- 문자열의 사전 순서 비교: 부등호로 비교 가능(사전 앞에 있는 것이 더 작음)

- swap(str1, str2): str1, str2 문자열을 서로 바꿔줌

- 문자열을 비교할 때는 compare() 함수(값이 서로 같으면 0을 리턴하고 다르면 -1를 리턴)

- length() 함수: 문자열 길이 => 괄호 쓰는 거 잊지 말기!!!(안 쓰고 삽질..)

- erase() 함수: 벡터에서 i번째 원소를 삭제(벡터의 시작 주소는 벡터이름.begin()

따라서 i번째 인덱스에 있는 원소를 삭제할 때는 벡터이름.erase(벡터이름.begin()+i))

 

그러면 일단 벡터 안에 있는 문자열의 길이를 length()로 비교해주고 앞에 있는 원소가 더 크면 swap으로 위치를 바꿔줘야겠다. 그리고 만약 문자열의 길이가 같다면 중복되는지 compare()로 확인 후, 같으면 erase()로 지워주고 다르면 부등호로 사전 순으로 재배열 하면 될 것 같다.

 

좋았어!! 다시 코드를 작성해봐야겠다.

//시간 초과된 코드

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

vector<string> A;

int main() {
	int N;
	cin >> N;
	string a;
	for (int i = 0; i < N; i++) {
		cin >> a;
		A.push_back(a);
	}
	for (int i = 0; i < A.size()-1; i++) {
		for (int j = i+1; j < A.size(); j++) {
			//문자열의 길이를 비교해서 더 길면 뒤로
			if (A[i].length()>A[j].length()) {
				swap(A[i], A[j]);
			}
			else if (A[i].length() == A[j].length()) {
				if (A[i].compare(A[j]) == 0) {//같으면
					A.erase(A.begin() + j);
				}
				else {
					//길이가 같고 중복이 아니니 사전 순으로
					if (A[i] > A[j]) {
						swap(A[i], A[j]);
					}
				}
			}
		}
	}

	for (int i = 0; i < A.size(); i++) {
		cout << A[i] << endl;
	}
	
	return 0;
}

중간에 erase()로 지워주면 당연히 벡터의 크기는 줄어드는 건데 내가 N개만큼 그대로 반복문을 돌려주었다.(바보 ㅎㅎ)

이것때문에 어디서 잘못됐나 주석처리하고 출력해보느라 시간 엄청 잡아먹었네 ㅎㅎ

 

좋았어!! 실행해보니까 예시 출력대로 나오는구만 ㅎㅎ

 

그런데....

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

??: 얘야, 인생이란 원래 자기 생각대로 되지 않는 법이란다

 

 

갑자기 이 장면이 생각나서 그려봤다.

 

 

(정신차리자...)

일단, 다른 풀이를 한번 찾아봐야겠다.

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

int cmp(string a, string b) {
	// 1. 길이가 같다면, 사전순으로
	if (a.length() == b.length()) {
		return a < b;
	}
	// 2. 길이가 다르다면, 짧은 순으로 
	else {
		return a.length() < b.length();
	}
}

// 범위가 크기때문에 전역변수로 설정
string word[20000];

int main() {
	int N;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> word[i];
	}

	sort(word, word + N, cmp);

	for (int i = 0; i < N; i++) {
		// 중복된 경우 한번만 출력
		if (word[i] == word[i - 1]) {
			continue;
		}
		cout << word[i] << "\n";
	}

	return 0;
}
출처: https://beginnerdeveloper-lit.tistory.com/94 [초보 개발자의 이야기, 릿허브:티스토리]

헉...!! 이 분은 C++의 내장함수인 sort함수를 이용해 길이순으로 정렬하되, sort(v.begin(), v.end(), compare)의 compare 부분을 이용해 단어의 길이가 같다면 사전 순으로 정렬하도록 구현하셨다.

난 다 비교해가면서 중복된 경우 바로 삭제시켜줬는데 이 코드는 모두 정렬한 후 출력 시 앞뒤 단어가 같다면 해당 부분을 건너뛰도록 구현하였다고 한다(O ㅁ O !!).

오호~~ 이렇게 구현할 수도 있구나!! 난 sort하면 a, b, c, d 순으로 정렬할 수 있다고만 생각했다...(반성하자.)

 

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

bool Comp(string a, string b) {
    if (a.length() != b.length()) {//2번째 인자의 길이가 더 길때, True 반환
        return a.length() < b.length();	//길이가 짧은 단어부터 긴 단어순으로 정렬
    }
    else {//길이가 같다면 사전순으로 정렬
        return a < b;	//b가 a보다 사전순으로 더 뒤쪽에 위치할 때, True 반환(사전순으로 정렬)
    }
}

int main()
{
    int n,tmp;
    cin >> n;
    string words[20001];
    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }
    sort(words, words + n, Comp);
    string before="";
    for (int i = 0; i < n; i++) {
        if (before == words[i]) continue;
        cout << words[i] << "\n";
        before = words[i];
    }
    return 0;
}

출처: https://foramonth.tistory.com/7

다른 분의 코드도 보니 sort에서 세번째 인자로 정렬 기준을 전달해 주셨다.

만약, 사전순으로 뒤에 위치한 단어를 앞에 위치하게 정렬하고 싶으면 return a>b를 사용하면 된다고 한다.

 

이번엔 맞은 줄 알았는데ㅠㅠ 너무 슬프다.

그래도 확실히 문자열을 많이 안 해봐서 그런지 c++에 있는 함수들을 많이 공부할 수 있어서 다행인 것 같다.오늘은 머리가 아프니 이정도만...

 

그럼 안녕...