0과 1의 이진 시퀀스가 주어집니다. 또한 사람이 current_pos에 저장된 위치 또는 지점에 앉아 있다고 가정합니다. 이제 current_pos에서 시작하여 이진 시퀀스가 0이면 왼쪽으로 한 단계 이동합니다( current_pos - 1). 1이면 오른쪽으로 한 단계 이동합니다( current_pos + 1). 목표는 전체 바이너리 시퀀스가 완료된 후 그가 방문한 별개의 위치 또는 지점을 찾는 것입니다.
우리는 포인트를 방문한 횟수를 사용하여 이것을 해결할 것입니다. 빈도가 0이 아닌 경우 고유한 포인트의 수를 늘립니다.
입력
Path[]= “001100” current_pos=3
출력
Distinct points visited on number line: 3
설명 - 경로[0] 및 위치 3에서 시작합니다.
Path[0]: 0 → move left ...currpos=2 Path[1]: 0 → move left ...currpos=1 Path[2]: 1 → move right ...currpos=2 Path[3]: 1 → move left ...currpos=3 Path[4]: 0 → move left ...currpos=2 Path[5]: 0 → move left ...currpos=1
총 고유 위치는 3이며 1,2,3
입력
Path[]= “010101” current_pos=5
출력
Distinct points visited on number line: 2
설명 - 경로[0] 및 위치 5에서 시작합니다.
Path[0]: 0 → move left ...currpos=4 Path[1]: 1 → move right ...currpos=5 Path[2]: 0 → move left ...currpos=4 Path[3]: 1 → move right ...currpos=5 Path[4]: 0 → move left ...currpos=4 Path[5]: 1 → move right ...currpos=5
총 고유 위치는 2이며 4와 5입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
0과 1의 문자열이 경로에 저장됩니다.
-
Current_pos는 시작점을 저장합니다.
-
함수 getDistinctPoints(int current_pos, string path)는 현재 위치와 경로를 입력으로 받아 고유한 위치/포인트 수를 반환합니다.
-
변수 len은 경로의 길이를 저장합니다.
-
배열 빈도[21]는 지점을 방문한 횟수에 대한 빈도를 저장하는 데 사용됩니다. 인덱스는 포인트를 나타냅니다. 총 0-20.
-
경로 문자열 탐색을 시작합니다.
-
현재 값이 0이면 왼쪽으로 이동합니다( current_pos -1 ). 이 pointfrequency[current_pos]++의 업데이트 빈도.
-
그렇지 않으면 현재 값이 1이면 오른쪽으로 이동합니다( current_pos +1 ). 이 pointfrequency[current_pos]++의 업데이트 빈도.
-
이제 주파수 배열과 0이 아닌 값 각각에 대해 탐색합니다. 수를 늘립니다.
-
개수에 고유한 방문 지점이 있습니다.
- 원하는 결과로 카운트를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
//distict points visited between 0 to 20
int getDistinctPoints(int current_pos, string path){
// Length of path
int len = path.length();
int count=0;
// Array to store number of times a point is visited
int frequency[21]={0};
// For all the directions in path
for (int i = 0; i < len; i++) {
//for left direction
if (path[i] == '0') {
current_pos--;
frequency[current_pos]++; //increase visit count
}
// If the direction is right
else {
current_pos++;
frequency[current_pos]++; //increase visit count
}
}
for(int i=0;i<21;i++)
if(frequency[i]!=0) // if visted then frequency[i] is non zero
count++;
return count;
}
int main(){
int current_pos = 3;
string path = "011101100";
cout << "Count of distinct points visited on the number line:<<(getDistinctPoints(current_pos, path));
return 0;
} 출력
Count of distinct points visited on the number line :5