[백준 BOJ] 1181번 단어 정렬 (C++/cpp)

문제 설명

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

1181번: 단어 정렬

 

접근 방법 - 정렬의 응용문제

백준의 1181번 문제는 정렬에 대하여 다소 심화된 내용을 다루고 있는 문제이다.

해당 문제는, 아래와 같은 규칙으로 입력받은 단어들을 정렬하여 출력해야 하는 문제이다.

(예시를 보면, 아래의 규칙을 이해하는 것이 보다 더 수월할 것이다.)

- 길이 순으로 오름차순 정렬
- 길이가 같다면, 사전 순으로 오름차순 정렬

필자의 경우엔, 위 규칙처럼 정렬을 완료한 다음 이 결과값을 출력하는 것과는 다른 방법을 사용하였다.

정렬 함수를 사용하여 우선 사전 순으로 정렬을 한 뒤에, 길이에 따라 출력의 순서만 달리 한 방법을 사용한 것이다.

이때 문제에선 중복된 단어는 한번만 출력하라고 명시되어있기 때문에 이 점을 유의하며 코드를 작성하였다.

이 문제의 해결에 있어 어려움을 겪고 있다면, 아래 필자의 코드와 설명을 한번 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 단어들을 입력받을 배열(arr)을 전역변수로 선언해둔다.

 

2) 단어의 수(n)를 입력받고, 이에 따라 arr의 값들을 입력받는다.

이때, 단어 중 길이가 최대인 값도 함께 구한다. 이는 길이 순으로 오름차순 출력할 때 사용된다.

 

3) string 타입 변수 st를 null값으로 선언해둔다. 이는, 중복된 단어가 있는지에 대한 여부를 판별하는 데에 사용된다.

 

4) sort 함수로 arr 배열의 단어들을 사전 순으로 정렬한다.

 

5) 이중 반복문을 실행하여, 아래의 연산을 취한다.

(제어 변수 i로 길이가 짧은 것부터 찾아서 출력을 수행하도록 한다.)

(제어 변수 j로 arr의 배열값들을 순차적으로 탐색한다.)

- 현재 탐색 중인 문자열의 길이가 i와 동일하다면 출력을 수행하도록 한다.

다만 중복된 단어가 있다고 판단되면 출력을 수행하지 않고 바로 다음 순서의 반복문을 수행하도록 한다.

 

6) 출력이 완료되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <string>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 1181번 코드
string arr[20000];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	
	int max = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (max < arr[i].length()) {
			max = arr[i].length();
		}
	}

	string st="";
	sort(arr, arr + n);
	for (int i = 1; i <= max; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[j].length() == i) {
				if (j != 0 && arr[j] == st) { continue; }
				cout << arr[j] << endl;
				st = arr[j];
			}
		}
	}
}

 

제출 결과

(2022.06.10 백준 1181번 문제 제출 결과)