[C++] 프로그래머스 조이스틱 탐욕법

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

struct APos
{
	int count;
	int pos;
};

int solution(string name) 
{
	int answer = 0;
	APos curr = { 0, 0 };
	APos prev = { 0, 0 };
	for (int i = 0; i < name.size(); i++)
	{
		if (name[i] == 'A')
		{
			//첫 지점 지정
			if (curr.count == 0)
				curr.pos = i;
			curr.count++;
		}
		else
		{
			//현재 a의 길이가 이전 a의 길이보다 길거나 같다면 교체
			if (prev.count < curr.count)
			{
				prev.count = curr.count;
				prev.pos = curr.pos;
			}
			curr.count = 0;
			curr.pos = 0;
		}
	}
    
    //A가 쭉 가버려서 prev에 저장 안 됐을때
    if (prev.count < curr.count)
	{
	    prev.count = curr.count;
	    prev.pos = curr.pos;
	}
    
    
	//좌우 거리 판단
	if (curr.count == 0 && prev.count == 0) //A가 없다.
		answer += name.size() - 1;
	else if (curr.count > 0 && prev.count == 0) //한 지점부터 끝까지가 A이므로 이 지점까지만 이동하면 됨
		answer += curr.pos - 1;
	else //가장 긴 구간을 피해서 왼쪽으로 다시 되돌아간다.
	{
		//돌아가는 계산
		int turn = 0;
		//처음부터 돌아가지 않을 때만
		if (prev.pos != 0)
			turn = (prev.pos - 1) * 2;
        
		turn += name.size() - (prev.pos + prev.count);
		answer += min(turn, (int)(name.size() - 1));
	}
    
	//상하 거리 판단
	for (int i = 0; i < name.size(); i++)
	{
		if (name[i] != 'A')
			answer += min(name[i] - 'A', 'Z' - name[i] + 1);
	}
    
	return answer;
}

풀이

1. 좌우 거리와 상하 거리를 판단해서 개수에 추가하여 준다.

2. 좌우 거리는 A의 최대길이를 구해주어 그 기준 좌우에 대한 길이를 파악하고 돌아갈 것인지 구별한다.

3. 상하 거리는 a~n이나 z~n + 1개이다. z부터일경우 a에서 시작했기때문에 + 1을 해준다.

4. 마지막으로 좌우거리와 상하거리를 합 해주면 된다.

 

 

#include <string>
#include <vector>

using namespace std;

struct APos
{
    int count;
    int pos;
};

int solution(string name) {
    int answer = 0;
    APos curr = { 0, 0 };
    APos prev = { 0, 0 };

    for (int i = 0; i < name.size(); i++)
    {
        if (name[i] == 'A')
        {
            //첫 지점 지정
            if (curr.count == 0)
                curr.pos = i;

            curr.count++;
        }
        else
        {
            //현재 a의 길이가 이전 a의 길이보다 길거나 같다면 교체
            if (prev.count <= curr.count)
            {
                prev.count = curr.count;
                prev.pos = curr.pos;
            }
            
            curr.count = 0;
            curr.pos = 0;
        }
    }

    //좌우 거리 판단
    if (curr.count == 0 && prev.count == 0)  //A가 없다.
        answer += name.size() - 1;
    else if (curr.count > 0 && prev.count == 0) //한 지점부터 끝까지가 A이므로 이 지점까지만 이동하면 됨
        answer += curr.pos - 1;
    else    //가장 긴 구간을 피해서 왼쪽으로 다시 되돌아간다.
    {
        //돌아가는 계산
        int turn = 0;

        //처음부터 돌아가지 않을 때만
        if (prev.pos != 0)
            turn = (prev.pos - 1) * 2;

        turn += name.size() - (prev.pos + prev.count);
        answer += min(turn, (int)(name.size() - 1));
    }

    //상하 거리 판단
    for (int i = 0; i < name.size(); i++)
    {
        if (name[i] != 'A')
            answer += min(name[i] - 'A', 'Z' - name[i] + 1);
    }

    return answer;
}

도무지 풀리지 않던 4, 7번 케이스의 1차이

 

 

https://programmers.co.kr/learn/courses/30/lessons/42860#

코딩테스트 연습 - 조이스틱