[프로그래머스] 서울에서 김서방 찾기

1. 문제 설명

String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다.  

 

- 제한 사항

• seoul은 길이 1 이상, 1000 이하인 배열입니다.
• seoul의 원소는 길이 1 이상, 20 이하인 문자열입니다.
• "Kim"은 반드시 seoul 안에 포함되어 있습니다.

 

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(vector<string> seoul) {
	string answer = "김서방은 ";

	for (int i = 0; i < seoul.size(); i++) {
		if (seoul[i] == "Kim") {
			answer += to_string(i) ;
			break;
		}

	}
    
	return answer+="에 있다";
}

 

3. 정리

for문을 이용하여 배열을 순회하여 "Kim" 문자열이 있는 인덱스를 찾아낸다.

 

전체 시간 복잡도를 단계별로 분석하면

단계	시간복잡도
for 루프 (탐색)	O(n)
to_string(i) 변환	O(1)
문자열 연결	O(1)

 

최종적으로 O(n) 이다.

 

 

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12919