11328: Strfry

• 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";
  }
}