2022-08-25-strfry-11328

• toc {:toc}

문제

C 언어 프로그래밍에서 문자열 (string) 은 native 한 자료형이 아니다. 사실, 문자열은 그저, 문자열의 끝을 표시하기 위한 말단의 NULL 이 사용된, 문자들로 이루어진 문자열일 뿐이다. 하지만 프로그래밍 언어에서 문자열을 다루는 것은 매우 중요하기 때문에, C 표준 라이브러리는 문자열을 다루는 데에 매우 유용한 함수들을 제공하고 있다 : 그들 중에는 strcpy, strcmp, strtol, strtok, strlen, strcat 가 있다.

하지만, 잘 알려져 있지 않으며, 잘 사용되지도 않는 함수가 하나 있다 : strfry 함수다. strfry 함수는 입력된 문자열을 무작위로 재배열하여 새로운 문자열을 만들어낸다. (역자 주 : 여기에서 입력된 문자열과 새로 재배열된 문자열이 다를 필요는 없다.)

두 개의 문자열에 대해, 2 번째 문자열이 1 번째 문자열에 strfry 함수를 적용하여 얻어질 수 있는지 판단하라.

입력

입력의 첫 번째 줄은 테스트 케이스의 수 0 < N < 1001 이다.

각각의 테스트 케이스는 하나의 줄에 영어 소문자들로만 이루어진 두 개의 문자열이 한 개의 공백으로 구분되어 주어진다. 각각의 문자열의 길이는 최대 1000 이다.

출력

각각의 테스트 케이스에 대해, 2 번째 문자열이 1 번째 문자열에 strfry 함수를 적용하여 얻어질 수 있는지의 여부를 “Impossible”(불가능) 또는 “Possible”(가능) 으로 나타내시오. (따옴표는 제외하고 출력한다.)

출처:https://www.acmicpc.net/problem/11328

풀이

range-based for 문을 통해 문자열의 문자를 받아내 배열에 저장.

changed(무작위로 변경된 문자열) 도 for 문으로 받아내 배열에 있는지 없는지 확인.

⇒ 알파벳 개수에 따라 불가능한 것도 있기에 배열에 추가 빼기 방식으로 적용한다.

이때까지의 코드는 changed 가 불필요한 알파벳까지 사용한 경우이다.

때문에 changed 가 필요한 알파벳을 일부만 사용한 경우를 처리해준다.

추가로, arr 배열 초기화까지 진행한다.

!!! 풀이할 때 조건, 경우의 수를 먼저 생각하고 저지르자 !!!

#include <bits/stdc++.h>
using namespace std;
 
int arr[30];
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N, res=1;
	string origin, changed;
	cin >> N;
	
	for(int i=0; i<N; ++i){
		res = 1;
		cin >> origin >> changed;
		// 알파벳 순서로 카운팅 => 알파벳 개수에 따라 1이 아닌 2, 3, ... 가능
		for(int elem : origin){
			arr[elem-'a']++;
		}
		
		for(int elem : changed){
			if(arr[elem-'a']==0){
				res = 0;
			}
			// origin이 ae인데 changed가 aa인 경우 확인하기 어렵기에 빼가면서 카운팅
			else{
				arr[elem-'a']--;
			}
		}
		// 필요한 알파벳 중 일부만 사용한 경우 처리 + 배열 초기화
		for(int i=0; i<30; i++){
			if(arr[i]!=0){
				res=0;
				arr[i]=0;
			} 
		}
		if(res==1) cout << "Possible\n";
		else cout << "Impossible\n";
	}
	
	
	return 0;
}

정답 풀이

결국 사고 방식은 같지만 명확한 방식 설정으로 훨씬 간결해진 코드.

어차피 마지막에 확인하기에 이전 과정은 모두 생략해도 된다.

// Authored by : OceanShape
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/a3d03c0124b544759d306668e55bbf4b
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  int N;
  cin >> N;
  while (N--) {
    int a[26] = {}; // 각 문자의 개수를 저장하는 배열
    string s1, s2;
    cin >> s1 >> s2;
 
    for (auto c : s1) a[c-'a']++; // 첫 번째 문자열의 각 문자는 개수+1
    for (auto c : s2) a[c-'a']--; // 두 번째 문자열의 각 문자는 개수-1
 
    // 0이 아닌 배열의 요소가 있을 경우, 개수가 다른 문자가 존재하므로 false
    bool isPossible = true;
    // 중괄호가 없어도 문제는 없으나 가독성을 위해 삽입
    for (int i : a){
      if (i != 0) isPossible = false;
    }
 
    if(isPossible) cout << "Possible\n";
    else cout << "Impossible\n";
  }
}