12871번: 무한 문자열
첫째 줄에 s, 둘째 줄에 t가 주어진다. 두 문자열 s와 t의 길이는 50보다 작거나 같은 자연수이고, 알파벳 소문자로만 이루어져 있다.
www.acmicpc.net
<풀이>
알고리즘 단톡에서 정말 새로운 접근법을 알게 되어서 기록하고자 풀어보았다.
f(s)를 무한정 붙여서 f(t)를 만들 때, f(s)와 f(t)가 같은 문자열인지 확인하는 문제이다.
아마 새로운 접근법을 모르는 상태라면 주어진 f(t)의 길이만큼 for문을 돌며
f(s)의 사이즈 만큼 인덱스를 이동시켜서 일치하는지 하나하나 체크하는 방식으로 구현했을 거 같다.
(문자열 길이가 50이라 충분히 가능했을듯)
새롭게 알게된 방법은 최소공배수를 구하는 GCD를 이용하는 것이었다.
문자열 길이를 기준으로 gcd를 사용한다..
즉, 둘 중 긴 문자열을 짧은 문자열의 길이가 같도록 계속 쪼개주며 이 것이 같은지 무한 반복해주면 된다.
만약 같다면 가장 짧은 길이의 문자열 을 출력할 것이고, 아니라면 그냥 공백을 리턴 한다.
+진짜 이런 방법은 생각도 못했음... 똑똑한 사람 개많네 진짜..
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
using namespace std;
string stringGCD(string s1, string s2){
while(1){
if(s1+s2 != s2+s1){
return "";
}
if(s1 == s2){
return s1;
}
if(s1.size()>s2.size()){
s1 = s1.substr(s2.size());
}
if(s2.size()>s1.size()){
s2 = s2.substr(s1.size());
}
}
return "";
}
int main(void){
string str1,str2;
cin>>str1>>str2;
if( stringGCD(str1,str2) =="") {
cout<<0<<"\n";
}
else cout<<1<<"\n";
}
1525번: 퍼즐
세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.
www.acmicpc.net
<풀이>
BFS를 활용한 문제이다. 처음엔 맨날 풀었던 2차원 배열로 0을 기준으로 모른 경우의수를 다 판단하고, 0의 자리를 바꿔주는 걸로 구현하려 했지만,,, 좌표 값 자체를 매번 변경해야해서.. 코드가 꼬였다.
검색을 통해 다들 어떤식으로 접근하나 봤더니... 이것도 신세계 ^^,,, 바로 2차원 배열이 아니라 이미 3*3으로 크기가 고정 되어 있기 때문에 string 형식으로 변환해서 탐색을 하더라....
string형식으로 큐에 넣어서 탐색하며 목표 값인 123456780 이라면 그때 까지의 연산횟수를 출력 (=BFS)... 진짜 나빼고 다 천재냐,,?
정리하자면 풀이는 다음과 같다.
일단, 탐색을 위한 큐와 이미 방문했는지 체크하기 위한 set함수를 사용했따. ( 예전에 배열의 크기 제한이 없을 때 방문 체크했던 기억을 살리며,,)
1. 초기 배열 값을 string형태로 입력받음
2. 초기 배열 값을 방문 체크 하기 위해 set에 넣고, 탐색을 위해 큐에 넣어줌
3. 초기 string에서 0의 위치를 반환받는다.
3.1 string 상 0의 위치에서 2차원 배열일때의 0의 위치를 구한다.
ex) 102345678 이라면 3에서 리턴될 0의 idx = 1
2차원 배열이라면 1 0 2 즉, int x = idx/3 = 0 | int y = idx%3 =1 => 0이 2차원 배열에서의 좌표는 (0,1)이다.
3 4 5
6 7 8
4. 0의 좌표를 기준으로 상하좌우 탐색을 한다.
4.1 만약 탐색이 가능하다면 swap함수를 통해 0이 해당 좌표의 값과 자리를 바꾼 string을 구함
4.2 바꾼 새로운 문자열이 방문하지 않았다면 ( st상에 개수가 0개라면) 새로 방문 표시 + 큐에 넣고 탐색
진짜 새로운 접근법이라.. 검색에 많이 의존했지만 ,, 새롭네,,,아직도,,, 일단 블로그에 업로드 하고 다시 싹 지우고 재 접근해봐야겠다..
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
using namespace std;
string check = "123456780";
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int main(void){
string map ="";
set<string> st;
queue<pair<string, int> > que;
int ans = 0;
char s;
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
cin>>s;
map+=s;
}
}
st.insert(map);
que.push(make_pair(map,0));
while(!que.empty()){
string str = que.front().first;
int cnt = que.front().second;
que.pop();
if(str == check){
cout<<cnt<<"\n";
return 0;
}
int idx = str.find('0');
int x = idx/3;
int y = idx%3;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || nx>=3 || ny<0 || ny>=3) continue;
string nxt = str;
swap(nxt[x*3+y], nxt[nx*3+ny]);
if(st.count(nxt)==0){
st.insert(nxt);
que.push(make_pair(nxt,cnt+1));
}
}
}
if(ans ==0) cout<<-1<<"\n";
else cout<< ans<<"\n";
}'Algorithm > BOJ' 카테고리의 다른 글
| [ 백준 ] 27일차 + 삼성기출 (0) | 2021.09.17 |
|---|---|
| [ 백준 ] 26일차 (0) | 2021.09.15 |
| [ 백준 ] 24일차 (1) | 2021.09.13 |
| [ 백준 ] 23일차 (0) | 2021.09.12 |
| [ 백준 ] 22일차 (0) | 2021.09.10 |