[백준 BOJ] 1755번 숫자놀이 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 정렬을 활용한 문자열 연산 응용문제

백준의 1755번 문제는 정렬을 활용하여 해결할 수 있는 문자열 연산 문제이다.

해당 문제는, 입력으로 주어지는 범위 내의 숫자들에 대하여 각 자릿수의 숫자를 영어 단어로 읽어 이를 사전 순으로 정렬하여 출력하는 문제이다.

예를 들어, "40"은 위 방식대로 읽는다면 "four zero"가 되며 "39"는 "three nine"이 된다.

본래 39가 40보다 앞에 있는 숫자이긴 하나, 위 방식대로 읽은 결과를 사전 순으로 나열할 때에는 40이 39를 앞선다고 볼 수 있다.

 

제한 시간도 2초로 넉넉하게 있기 때문에, 필자는 지문에 있는 설명을 그대로 코드에 반영하면서 문제 해결을 시도하였다.

각 숫자들에 대하여 위 규칙대로 읽었을 때의 문자열을 각각 생성하고 만들어진 문자열에 대해 오름차순 정렬을 수행한다면, 문제의 정답을 어렵지 않게 구할 수 있을 것이다.

다만 실제 정답을 출력할 때에는 숫자를 써야 하기 때문에, 문자열과 본래 숫자를 하나의 데이터 쌍으로 묶어서 연산을 진행하였다.

보다 자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

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

 

코드의 실행 순서

1) 숫자의 범위(n, m)를 입력받는다.

 

2) 데이터를 저장할 때에 활용할 벡터 dic을 미리 선언해 둔다.

이때, 정렬에 활용할 문자열 값과 실제 출력에 활용할 숫자 값을 한 쌍으로 묶어 저장할 수 있도록 벡터의 자료형을 <string, int>로 설정하였다.

 

3) n부터 m까지 하여, 반복문을 수행하여 아래의 연산을 취한다.

- 탐색하는 숫자의 각 자릿수에 보다 편리하게 접근하기 위해, 현재 숫자를 string형으로 변환한 결과를 임의의 변수 snum에 저장한다.

- 숫자의 각 자릿수를 단어로 읽었을 때의 문자열을 저장할 변수 read를 공백으로 초기화하여 선언해 둔다.

- 다른 반복문을 활용하여, snum의 각 문자값에 접근하도록 한다. 

각 문자값은 모두 '0' ~ '9' 범위 안의 값이므로, 각 숫자에 알맞은 단어를 read의 뒷부분에 삽입한다.

- read 문자열 값 설정이 완료되었다면, 본래 숫자값과 함께 묶어 dic의 요소로 추가한다.

 

4) 3)에서 dic의 데이터 삽입이 모두 완료되었다면, 이를 토대로 sort()를 활용하여 정렬을 수행한다.

(sort()를 수행할 때, 자동으로 dic 데이터 쌍의 첫 번째 값인 string형 값을 기준으로 오름차순 정렬을 진행한다.)

 

5) dic의 크기만큼, 반복문을 수행하여 정렬 완료된 dic의 각 데이터 요소에 순차적으로 접근한다.

각 데이터 쌍의 두 번째 값인 실제 숫자값을 불러와 순차적으로 출력을 수행한다.

(이때, 문제 지문의 출력 설명에 한 줄에 값을 10개씩 출력하라는 지시가 있기 때문에, 이를 반영하면서 출력을 수행하도록 한다.)

 

6) 모든 연산이 완료되었다면, 실행을 종료한다.

반응형

 

성공한 코드

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

//백준 1755번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	vector<pair<string, int>> dic;
	for (int i = n; i <= m; i++) {
		string snum = to_string(i);
		
		string read = "";
		for (int j = 0; j < snum.size(); j++) {
			switch (snum[j]) {
			case '0':	read += "zero";		break;
			case '1':	read += "one";		break;
			case '2':	read += "two";		break;
			case '3':	read += "three";	break;
			case '4':	read += "four";		break;
			case '5':	read += "five";		break;
			case '6':	read += "six";		break;
			case '7':	read += "seven";	break;
			case '8':	read += "eight";	break;
			case '9':	read += "nine";		break;
			}
		}

		dic.push_back({read, i});
	}

	sort(dic.begin(), dic.end());
	for (int i = 0; i < dic.size(); i++) {
		cout << dic[i].second << " ";
		if ((i + 1) % 10 == 0) { cout << endl; }
	}
}

 

제출 결과

(2024.10.16 백준 1755번 문제 제출 결과)