프로그래머스 서울에서 김서방 찾기 두 풀이

배열에서 원소 하나의 위치를 찾는 문제는 직접 순회로도 풀리고 표준 알고리즘으로도 풀린다. 둘 다 O(n)이라 성능 차이는 없지만, std::find는 위치가 아니라 이터레이터를 돌려주기 때문에 한 단계가 더 붙는다. 이 글에서는 그 두 풀이를 나란히 놓고, 이터레이터를 인덱스로 되돌리는 부분을 이야기하려 한다. 별도의 트러블슈팅 없이 구현 비교만 다루는 짧은 글이다.

서울에서 김서방 찾기 (Lv.1)

문제: https://school.programmers.co.kr/learn/courses/30/lessons/12919

vector<string> seoul에서 "Kim"의 인덱스 x를 찾아 "김서방은 x에 있다" 형식의 문자열을 반환하는 문제다. seoul의 길이는 1~1000, 원소 길이는 1~20이고, "Kim"은 반드시 한 번만 존재한다.

seoul	return
[“Jane”, “Kim”]	“김서방은 1에 있다”

문제 자체는 선형 탐색 한 번이면 끝난다(두 풀이 모두 O(n)). 정리하면서 남은 건 두 가지였다 — C++의 string은 Java의 .equals()와 달리 == 연산자로 바로 값을 비교할 수 있다는 점, 그리고 std::find()가 반환하는 이터레이터를 정수 인덱스로 바꾸는 과정.

코드 풀이

풀이 1 — for 루프 (작성한 코드)

vector를 앞에서부터 순회하며 seoul[i] == "Kim"으로 비교하고, 찾으면 break. to_string(i)으로 숫자를 문자열로 바꾼 뒤 + 연산으로 연결한다. 길이 확인은 length가 아니라 size()다.

#include <string>
#include <vector>
using namespace std;

string solution(vector<string> seoul) {
    int idx = 0;
    for (int i = 0; i < seoul.size(); i++) {
        if (seoul[i] == "Kim") {
            idx = i;
            break;
        }
    }
    return "김서방은 " + to_string(idx) + "에 있다";
}

풀이 2 — find + 포인터 연산

std::find(first, last, value)는 범위에서 값을 찾아 이터레이터를 반환한다(없으면 last 반환). 이걸 쓰면 한 줄로 줄어든다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(vector<string> seoul) {
    int idx = find(seoul.begin(), seoul.end(), "Kim") - seoul.begin();
    return "김서방은 " + to_string(idx) + "에 있다";
}

풀이 2 설명 — 이터레이터 → 정수 인덱스 변환

find()는 찾은 위치의 이터레이터(메모리 주소를 담은 객체) 를 반환하기 때문에, to_string()에 바로 넣을 수 없다.

정수 인덱스로 변환하려면 - seoul.begin() 을 통해 두 이터레이터 사이의 거리(칸 수) 를 계산해야 한다. it - v.begin() 대신 distance(v.begin(), it)을 써도 된다.

// 실제 메모리 구조 (예시)
주소 0x100: "Park"
주소 0x120: "Lee"
주소 0x140: "Kim"

seoul.begin() → 0x100  (항상 인덱스 0 위치)
find("Kim")   → 0x140  (Kim의 주소)

find("Kim") - seoul.begin()
= 0x140 - 0x100
= 2칸 차이 → 인덱스 2

// 시각적으로
인덱스:   0       1       2      (3)
        "Park" "Lee"  "Kim"    end()
           ↑              ↑
        begin()       find() 반환값

거리 = 2칸 = 인덱스 2

표현	타입	설명
find(...)	iterator	메모리 주소 (숫자 아님)
seoul.begin()	iterator	인덱스 0의 메모리 주소
find(...) - begin()	int	두 주소 사이 칸 수 = 인덱스

결과 정리

for 루프가 가장 직관적이고, find + 포인터 연산은 STL을 활용해 코드가 짧다. 가독성은 둘 다 나쁘지 않아서 어느 쪽을 써도 무방한 문제였다.

복기

• C++의 string은 == 으로 값 비교 가능
• std::find() 는 이터레이터를 반환하므로 .begin() 을 빼서 인덱스로 변환
• to_string() 으로 숫자를 문자열로 변환 후 + 연산으로 연결

핵심 요약 — find()는 정수가 아니라 이터레이터를 반환한다. begin()을 빼면 두 위치 사이의 칸 수가 나오고, 그게 곧 인덱스다.