글 읽기 - 생각대로 푼 알고리즘이 제출 시에 틀렸다고 나옵니다.

muscj7 5년 전 1

입력 개미를 왼쪽부터 순차 탐색하면서 ->방향의 개미(인덱스)를 스택에 담고 <-를 발견하면 스택의 개미의 방향과 거리를 수정해주는 알고리즘을 구현했습니다.

그런데 14%에서 틀렸다고 나오네요. 어느 부분을 놓친 것인지 모르겠습니다.

#include<stdio.h>
#include<vector>
#include<set>
using namespace std;

#define DIRECTION_RIGHT 1
#define DIRECTION_LEFT -1
#define DIRECTION_REVERSE -1

struct ant
{
	int distance; // 서있는 방향으로 떨어지기 위해 이동해야하는 거리(>=0)
	int id;
	int dir; // to r:1, to l:-1
};

vector<ant> ants;
vector<int> right_index;
set<pair<int, int>> s;

/*
 reverse : <-를 발견했을 대 호출하며, 
 담긴 ->데이터 <-로 바꾼다. 그리고 발견했던 <-를 ->바꾸고 스택에 추가한다.
*/
void reverse(int left_idx, int length) {	
	// 이전 데이터 중 ->데이터의 distance와 dir변경 및 pop
	int idx, len = right_index.size();
	while (len--) {
		idx = right_index[len];
		ants[len].dir *= DIRECTION_REVERSE;
		ants[len].distance = length - ants[len].distance;
		right_index.pop_back();
	}

	// <-의 distance와 dir 변경 및 push
	ants[left_idx].dir *= DIRECTION_REVERSE;
	ants[left_idx].distance = length - ants[left_idx].distance;
	right_index.push_back(left_idx);
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int N, L, K;

		// 입력
        // 각 개미 데이터는 떨어지기 위해 이동해야하는 거리(distance), id(id), 방향(dir)을 가진다.
		scanf("%d %d %d", &N, &L, &K);
		while (N--) {
			int p, a;
			scanf("%d %d", &p, &a);
			a > 0 ? ants.push_back({ L - p, a, 1 }) : ants.push_back({ p, a, -1 });
		}

		// 연산 : 순차 탐색 + 
        // -> 방향의 개미는 right_index에 인덱스를 저장
        // <- 방향의 개미를 발견했을 때, 왼쪽에 ->방향의 개미가 존재하면 reverse를 이용해 데이터 변경.
		int len = ants.size();
		for (int i = 0; i < len; i++) {
			if (ants[i].dir == DIRECTION_RIGHT)
				right_index.push_back(i);
			else if (!right_index.empty())
				reverse(i, L);
		}

        // set에 삽입 (순서 자동 세팅)
		for (int i = 0; i < len; i++) {
			s.insert({ ants[i].distance, ants[i].id });
		}
        
        // 찾을 위치로(K)
		set<pair<int, int>>::iterator itr = s.begin();
		while ((K--) != 1) {
			itr++;
		}
        
        // 출력
		printf("%d\n", itr->second);
        
        // 다음 케이스를 위한 초기화
		ants.clear();
		right_index.clear();
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

생각대로 푼 알고리즘이 제출 시에 틀렸다고 나옵니다.

muscj7 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말