코딩테스트/이코테

[CH4 구현] 아이디어를 코드를 바꾸는 구현 2

의정부핵꿀밤 2021. 12. 6. 11:37
728x90

예제 4-1) 상하좌우

  • 여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다
  • 이 공간은 1 X 1 크기의 정사각형으로 나누어져 잇다
  • 가장 왼쪽 위 좌표는 (1,1)이며 가장 오른쪽 아래 좌표는 (N, N)에 해당한다
  • 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다
  • 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 잇다
  • 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D중 하나의 문자가 반복적으로 적혀있다
  • 각 문자의 의미는 다음과 같다
    • L : 왼쪽으로 한 칸 이동
    • R : 오른쪽으로 한 칸 이동
    • U : 위로 한 칸 이동
    • D : 아래로 한 칸 이동
  • 이 때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다
    • ex) (1, 1)에서 L 혹은 U를 만나면 무시된다

 

[입력 조건]

  • 첫째 줄에 공간의 크기를 나타내는 N이 주어진다 (1<=N<=100)
  • 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다 (1<=이동 횟수<=100)

 

[출력 조건]

  • 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다

 

 

[입력 예시]

5

R R R U D D

 

[출력 예시]

3 4

 

 

[풀이]

  • 이 문제의 연산 횟수는 이동 횟수에 비례하게 된다
  • 만약 이동 횟수가 N번이면 시간 복잡도는 O(N)이다
  • 이러한 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류되며, 구현이 중요한 대표적인 문제 유형이다
  • 코테나 알고리즘 대회에서 가장 난이도가 낮은 1~2번 문제는 대부분 그리디 또는 구현 문제이다
  • 그만큼 쉬우면서 중요한 문제이기도 하다

 

C++ 코드)

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

int main()
{
    int n;
    char temp;
    int x=1, y=1;
    int nx=0, ny=0;
    string plan;
    
    cin>>n;
    cin.ignore();
    getline(cin,plan);
    for(int i=0;i<plan.length();i++)
    {
        switch (plan[i]) {
            case 'L':
                ny = y-1;
                break;
            case 'R':
                ny = y+1;
                break;
            case 'U':
                nx = x-1;
                break;
            case 'D':
                nx = x+1;
                break;
        }
        if(nx>=1 && nx<=n) {
            x=nx;
        }
        if(ny>=1 && ny<=n) {
            y=ny;
        }
        nx=0;
        ny=0;
    }
    printf("%d %d",x,y);
    return 0;
}

아니... 이게 하나도 안어려운건데 이상한데서 시간을 너무 많이 썼다,,

  1. n은 plan의 길이가 아닌데 계속 반복문 기준을 n으로 함
  2. char 형으로 받아야 되는데 int형으로 받음 (근데 이것도 아니었음)
  3. 배열이나 벡터로 받자니 plan의 길이를 모름
  4. string으로 입력 받는데 cin으로 받아서 공백에서 잘림 -> cin 버퍼 비우고 getline으로 받아서 해결

이정도였나

하.. 정신차려라... 암튼 일단 성공...ㅠㅠ

 

728x90